** Lather, rinse and repeat
:PROPERTIES:
:categories: math, recursive
:date: 2013/02/02 09:00:00
:updated: 2013/02/27 14:45:06
:END:
[[http://matlab.cheme.cmu.edu/2012/05/28/lather-rinse-and-repeat/][Matlab post]]
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.
#+BEGIN_SRC python
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)
#+END_SRC
#+RESULTS:
: 120
#+BEGIN_SRC python
from scipy.misc import factorial
print factorial(5)
#+END_SRC
#+RESULTS:
: 120.0
**** 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.
#+BEGIN_SRC python
n = 5
factorial_loop = 1
for i in range(1, n + 1):
factorial_loop *= i
print factorial_loop
#+END_SRC
#+RESULTS:
: 120
There are some significant differences in this example than in Matlab.
1. the syntax of the for loop is quite different with the use of the =in= operator.
2. python has the nice *= operator to replace a = a * i
3. We have to loop from 1 to n+1 because the last number in the range is not returned.
*** 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.