Why recursion change result?

Question

I was checking out doctest and copied the factorial example to my editor. Since using recursion felt more functional programming, I felt like changing the example like this;

def factorial(n):
    # ... omitted
    if n+1 == n:  # catch a value like 1e300
        raise OverflowError("n too large")

    if n == 0:
        return 1
    else:
        return factorial(n  - 1) * n

After this change, one of the tests failed;

Failed example:
    factorial(30.0)
Expected:
    265252859812191058636308480000000L
Got:
    2.6525285981219103e+32

What is the reason of this difference?

Answer 1

Try running with factorial(30) instead of factorial(30.0). floating point addition isn't exact like integer addition, so you'll start seeing errors after a while.

Consider:

>>> 1e20 + 1 == 1e20 #True

This is because you don't have enough precision (bits) to store both of those numbers uniquely. (a typical python float has 64 bits meaning you have 2**64 unique combinations -- somewhere around 1.84e19 options. However, the maximum size for a python float is sys.float_info.max which is about 1.8e308 on most systems, so there is no way to store each integral value uniquely -- especially when you consider that floats can hold a lot more than just integer values)

Personally, I would just cast the value of n to an integer inside your factorial function since factorial is only defined for integers -- possibly checking to make sure that abs(int(n) - n) < 1e-5 or something to that effect.

Answer 2

The number you're entering is a float. Since you're not converting it to an int you'll get a float in the output.