Lather, rinse and repeat

Posted February 02, 2013 at 09:00 AM | categories: recursive, math | tags:

Updated February 27, 2013 at 02:45 PM

Recursive functions are functions that call themselves repeatedly until some exit condition is met. Today we look at a classic example of recursive function for computing a factorial. The factorial of a non-negative integer n is denoted n!, and is defined as the product of all positive integers less than or equal to n.

The key ideas in defining a recursive function is that there needs to be some logic to identify when to terminate the function. Then, you need logic that calls the function again, but with a smaller part of the problem. Here we recursively call the function with n-1 until it gets called with n=0. 0! is defined to be 1.

def recursive_factorial(n):
    '''compute the factorial recursively. Note if you put a negative
    number in, this function will never end. We also do not check if
    n is an integer.'''
    if n == 0:
        return 1
    else:
        return n * recursive_factorial(n - 1)

print recursive_factorial(5)

from scipy.misc import factorial
print factorial(5)

120.0

0.1 Compare to a loop solution

This example can also be solved by a loop. This loop is easier to read and understand than the recursive function. Note the recursive nature of defining the variable as itself times a number.

n = 5
factorial_loop = 1
for i in range(1, n + 1):
    factorial_loop *= i

print factorial_loop

There are some significant differences in this example than in Matlab.

the syntax of the for loop is quite different with the use of the in operator.
python has the nice *= operator to replace a = a * i
We have to loop from 1 to n+1 because the last number in the range is not returned.

1 Conclusions

Recursive functions have a special niche in mathematical programming. There is often another way to accomplish the same goal. That is not always true though, and in a future post we will examine cases where recursion is the only way to solve a problem.

org-mode source

The Kitchin Research Group

Chemical Engineering at Carnegie Mellon University