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)
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
- 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.
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.
Copyright (C) 2013 by John Kitchin. See the License for information about copying.