Lather, rinse and repeat

| categories: math | View Comments

recursive_functions

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
Read and Post Comments