Simplifying this factorial function

def factorial(t,n):
if n == 1 : return t

else: x = (t * (n-1))

n = n-1

return factorial(x,n)

print factorial(6,6)


I can't seem to figure out a way to just stick to requiring one parameter input while keeping the program small. I also want the function to remain recursive (trying to work on my recursive thinking).

If you have any other cooler simplifications or other fancy methods, please show it off.

• Probably the easiest/best thing to do is not write this as a recursive function but as a loop. Recognising when not to write recursion is an important concept. Nov 5, 2014 at 15:41
• Especially in Python where recursion is not really optimised. Nov 5, 2014 at 15:44
• how about a simple decrementing for loop?
– Malachi
Nov 5, 2014 at 16:30
• Use an internal function inside factorial to do the real work, and use the wrapper function to pass in what you need. This is what I do in Haskell if I need to pretty-up explicit recursion. Nov 6, 2014 at 1:33

If you're going to do it recursively, you can do it dynamically:

from functools import wraps

def memo(f):
"""Memoizing decorator for dynamic programming."""
@wraps(f)
def func(*args):
if args not in func.cache:
func.cache[args] = f(*args)
return func.cache[args]
func.cache = {}
return func

@memo
def factorial(num):
"""Recursively calculate num!."""
if num < 0:
raise ValueError("Negative numbers have no factorial.")
elif num == 0:
return 1
return num * factorial(num-1)


(@wraps, also a decorator, is just there to keep the docstring from the wrapped function in the wrapping function.)

This will store previous results (trading space for speed) and use them in future calculations:

>>> factorial(4)
24
>>> factorial.cache
{(2,): 2, (0,): 1, (3,): 6, (1,): 1, (4,): 24}


Now if you call factorial(5), it will look up factorial(4) from the cache rather than repeating the calculation. You can see this process in the traceback for a negative argument:

>>> factorial(-1)

Traceback (most recent call last):
File "<pyshell#18>", line 1, in <module>
factorial(-1) # call to factorial
File "<pyshell#3>", line 6, in func # actually calls wrapping function
func.cache[args] = f(*args) # not in cache, so ...
File "<pyshell#17>", line 5, in factorial # ... wrapped function gets called
raise ValueError("Negative numbers have no factorial.") # error raised from wrapped function
ValueError: Negative numbers have no factorial.


(Note that the exception interrupts the assignment to func.cache, so this won't get cached!)

Bonus code golf-y iterative version:

from operator import mul

def factorial(num):
"""Iteratively calculate num!."""
return reduce(mul, xrange(1, num+1)) if num else 1


(This will TypeError on negative inputs.)

• Glad someone mentioned caching. It drastically accelerates it once it warms up. The highest factorial that can fit in a double is 170!, which results in 7.257415615×10³⁰⁶. Nov 5, 2014 at 17:10
• @DougGale note that these functions will return a long for inputs above 12, which has unlimited precision, not a float (according to sys.float_info, the largest float on my installation is 1.7976931348623157e+308). Nov 5, 2014 at 17:13
• jon, thanks for introducing the caching 'trick' to me, it looks super useful. Nov 5, 2014 at 23:15

First, if n == 1the method returns, so there is no need for the else.

Let us see what 6! would result in: 6 * 5! which is just 6 * 5 * 4! and so on.

Now we see a patter: n! = n * (n-1)!

Keeping this in mind we can refactor the given method to only take one parameter and to be recursive.

def factorial(n):
if n < 0 :
raise ValueError("Negative values are not allowed.")
if n == 0 : return 1

return n * factorial(n-1)

print factorial(6)


As James Snell stated correctly in his comment, we can replace the n == 1 check with a n <= 2 check if we assume n >= 1.

As jonrsharpe stated correctly in his comment, 0! should return 1 and also negative numbers don't have a factorial.

As Simon André Forsberg stated correctly in his comment, rasing an error for a negative parameter should be done.

This is probably better suited as a loop instead of recursion.

Also your function isn't truly an n-factorial function, it is a scalar multiplied by an n-factorial!

Here is a while loop version

def factorial(n):
t = 1
while not n == 1:
t *= n
n -= 1
return t

print factorial(6)


You could also do this with a for loop as well:

def factorial(t):
for n in range(1,t):
t *= n
return t
# note that the range is computed only once, so changing t is okay
# also note that range(1,t) is not t inclusive,
# however the logic still includes t when finding the answer
print factorial(6)

• The factorial function is commonly presented as a canonical example of exactly what kind of problems recursion can solve; so much so that many CS students learn it as their first recursive function declaration. As such, what leads you to state that this problem isn't well suited for recursion? Nov 5, 2014 at 23:56
• @Andrew Coonce Mainly due to the recursion limit. If I don't know the common input, I preferably to go with the method least likely to crash. Imagine the user writes factorial(1500)- this will crash on many systems for a recursive version, but work with a looping version! Nov 6, 2014 at 0:13