7
\$\begingroup\$
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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Nov 5, 2014 at 15:41
  • 1
    \$\begingroup\$ Especially in Python where recursion is not really optimised. \$\endgroup\$
    – SylvainD
    Nov 5, 2014 at 15:44
  • \$\begingroup\$ how about a simple decrementing for loop? \$\endgroup\$
    – Malachi
    Nov 5, 2014 at 16:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Nov 6, 2014 at 1:33

3 Answers 3

7
\$\begingroup\$

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.)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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³⁰⁶. \$\endgroup\$
    – Doug Gale
    Nov 5, 2014 at 17:10
  • \$\begingroup\$ @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). \$\endgroup\$
    – jonrsharpe
    Nov 5, 2014 at 17:13
  • \$\begingroup\$ jon, thanks for introducing the caching 'trick' to me, it looks super useful. \$\endgroup\$
    – kalin
    Nov 5, 2014 at 23:15
8
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$ Nov 5, 2014 at 23:56
  • \$\begingroup\$ @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! \$\endgroup\$
    – flakes
    Nov 6, 2014 at 0:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.