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

120

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

120

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.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.