Efficient Factorial Calculation in Python: Recursive vs. Iterative Methods

[Whovian]

I tried the following code:

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

def ncr(n,r):
    return ((factorial(n))/(factorial(r)*factorial(n-r)))

number = 0

for n in range(100):
    for r in range(100):
        print ncr(n,r)

Basically, for all n and r from 1 to 100, it's supposed to print $\binom{n}{r}$

Unfortunately, running from the command line, I get:

Traceback (most recent call last):
  File "Pythontest.py", line 14, in <module>
    print ncr(n,r)
  File "Pythontest.py", line 8, in ncr
    return ((factorial(n))/(factorial(r)*factorial(n-r)))
  File "Pythontest.py", line 5, in factorial
    return n*factorial(n-1)
  File "Pythontest.py", line 5, in factorial
    return n*factorial(n-1)
  File "Pythontest.py", line 5, in factorial
    return n*factorial(n-1)

 

[Dickfore]

you have to have $0 \le r \le n$. your definition of factorial goes into an infinite callback if $n < 0$.

 

[gsal]

Also, for general purposes...factorial is not defined for negative numbers, so, you should enhance your 'def factorial' and guard (validate) against negative numbers and possibly raise an exception, etc...you know, for when you use this def in a more complex program.

 

[Whovian]

you have to have $0 \le r \le n$. your definition of factorial goes into an infinite callback if $n < 0$.

Oh. Oops.

Also, for general purposes...factorial is not defined for negative numbers, so, you should enhance your 'def factorial' and guard (validate) against negative numbers and possibly raise an exception, etc...you know, for when you use this def in a more complex program.

Also sound advice.

 

[rorix_bw]

May I ask why you are doing it recursively? It's not particularly efficient in Python when done that way.

def rfac (x):
    return x * rfac (x-1) if x > 0 else 1
    
def ifac (x):
    f = 1
    for i in range (1, x+1):
        f *= i
    return f

from timeit import Timer
print (Timer ("rfac(20)", "from __main__ import rfac")).timeit()
print (Timer ("ifac(20)", "from __main__ import ifac")).timeit()

$ python fac.py
10.4178638458
5.76771497726

There are much faster ways to compute it, if you search the web.

Edit: I am not sure I would check or throw for negative input. There's defensive programming, and there's paranoia. It should not happen in practice. I admit this is personal style. I understand there cases where it might (web app), but seriously ... use a precomputed lookup table of N! if it's a web app.