Python 3.6 [PY36 Env]

Python Recursion - Factorial Example

Code on this page is to illustrate the basics of recursion. Code was tested in Python 3.6 but should work in Python 2.7 as well. The Factorial example is presented a few ways including condensing the code to a single line.

Factorial Example

If we had to roll our own factorial in Python, this example is how we would do it.



In [1]:

    
# some may find this code more readable ... single line solutions to the function are provided immediately below it.
import sys
n = int(input())
def factorial(n):
    if n <= 1:
        return n
    else:
        return n*factorial(n-1)
factorial(n)



In [2]:

    
# this cell explores creating a function that solves the problem with only one real line of working code  
import sys
n = int(input())
def factorial(n):
    return n if n <= 1 else n*factorial(n-1)  # this says:  "return n if ... else return <value after else>"
        
factorial(n)  # this cell prompts for input into the function to test it



In [3]:

    
# using lambda, a single line solution could be done like this:
import sys
n = int(input())
factorial_lambda = lambda n : 1 if n<=1 else n*factorial(n-1)
factorial_lambda(n)



In [4]:

    
# without recursion ... a loop could be created like this
import sys
def factorial_loop(n):
    f = n
    while n > 1:
        f = f*(n-1)
        if f <= 1: return 1
        n -= 1
    return f
print("factorial of 7:")

factorial_loop(7)









    



factorial of 7:






    Out[4]:





5040

Performance testing

These tests show performance comparisons. They also prove that we should use the math library instead of our own function.



In [5]:

    
%%timeit   # %% magic only works in a iPython cells. Use import timeit and timeit() in .py code
factorial(800)









    



100 loops, best of 3: 1.05 ms per loop



In [6]:

    
%%timeit
factorial_lambda(800)









    



1000 loops, best of 3: 1.09 ms per loop



In [7]:

    
%%timeit
factorial_loop(800)









    



1000 loops, best of 3: 1.24 ms per loop



In [8]:

    
import math



In [9]:

    
%%timeit
math.factorial(800)









    



1000 loops, best of 3: 90.4 µs per loop

To understand the above, a full table of metric measures used by timeit is provided here on wikipedia.

ms = millisecond ( 0.001 ) 10^-3
us = microsecond ( 0.000001 ) 10^-6
ns = nanosecond ( 0.000000001 ) 10^-9
click here for more

math.factorial() is much faster than a home grown solution but in this instance, we can also see a performance boost for recursion over the loop solution. Note that there are other concerns to using recursion though. Recursion literally creates another instance of the whole function with each iteration. This can lead to memory issues when the iterations get quite large. Depending on the exact nature of the code, you may also be surpirsed to discover it is not always the fastest solution. Specific combinations of code can produce unexpected results but usually, the expectation is that recursion will be faster and permit some problems that defy conventional solutions to be cracked more simply and succinctly.

Reference

For another really good example of the use of recursion, see "TMWP_TMWP_PY27_OO_Towers_of_Hanoi.ipnyb." The opening to this notebook buries the recursion in object code designed to solve many related things, but the research section includes some very tight and succinct examples illustrating a seemingly complex problem made simple by recursion.



In [ ]: