Lather, rinse and repeat
May 29, 2012 at 01:44 AM | categories: math | View Comments
Contents
Lather, rinse and repeat
John Kitchin 5/28/2012
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.
function main
recursive function definition
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.
function f = 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 % this is the terminating case f = 1 else % otherwise we call the function again, this time with n-1 f = n * recursive_factorial(n-1) end end
f = 1 f = 1 f = 2 f = 6 f = 24 f = 120 ans = 120
Matlab factorial function
factorial(5)
ans = 120
Now our function
recursive_factorial(5)
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=1:n factorial_loop = factorial_loop*i end
factorial_loop = 1 factorial_loop = 2 factorial_loop = 6 factorial_loop = 24 factorial_loop = 120
Conclusions
Recursive functions have a special niche in mathematical programming. There is often another way to accomplish the same goal. That isn't always true though, and in a future post we will examine cases where recursion is the only way to solve a problem.
end % categories: math % tags: recursive