Subscribe to andrewsw's Blog        RSS Feed
-----

Factorial Walkthrough (Recursion)

Icon Leave Comment
Doing what it says on the tin! Walking through recursive function calls.

The programming language is not important, as long as you understand functions (function arguments and return statements).

wiki said:

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5! = 5 x 4 x 3 x 2 x 1 = 120

Factorial :wikipedia

long factorial(int n) {
    if (n == 0)
        return 1; 
    else
        return n * factorial(n-1);
}


This is an example of a recursive function. Simply, a function that calls itself.

Recursion :wikipedia

What is factorial(3) ?

Within the function n is 3, which is not 0, so the FINAL RETURN RESULT will be:

return n * factorial(n-1);    // which is,
return 3 * factorial(2);


Remember, this will be the final result returned by the function.

So what is factorial(2) ?
Well, n is now 2, which still isnít 0, so factorial(2) will be whatever is returned by:

return 2 * factorial(1);


So what is factorial(1) ?
Well, n is now 1, which still isnít 0, so factorial(1) will be whatever is returned by:

return 1 * factorial(0);


So what is factorial(0) ? IT IS 1 !! Because if (n == 0) is true, the function returns 1.
Think about it. There is no debate: The result of the function call factorial(0) is 1.

It is time to back-track. Remember, nothing has yet been returned from the function. All the above intermediate results are still sitting in the computer's memory, in an area called the stack or call stack.

return 1 * factorial(0);    // is the same as..
return 1 * 1;    // because we know that factorial(0) is 1


This value 1 is the value returned by factorial(1), which is fed back to:
return 2 * factorial(1);    // is the same as..
return 2 * 1;


This value (2 * 1 = 2) is the value returned by factorial(2), which is fed back to:
return 3 * factorial(2);    // is the same as..
return 3 * 2;    // 6


This is the VERY FIRST return statement that we encountered when we began our journey, and the one that gives us our final return result (6). There is nothing else in the pipeline; that is, nothing else waiting to be calculated. So the function completes (returns) and we have our result that factorial(3) is 6.

In Brief

The value returned by factorial(3) is:
3 * factorial(2)    // which is
3 * (2 * factorial(1))    // which is
3 * (2 * (1 * factorial(0)))
3 * (2 * (1 * 1))
3 * (2 * 1)
3 * 2
6





0 is the base case for our recursive function. That is, an input for which the return result is trivial - doesn't require a recursive call. The other inputs (1,2,3, etc.) are recursive cases. There must be a base case otherwise the recursion will never end.




Recursion is a tricky subject and most people struggle to get their head around it. The secret is not to try and understand it all in one go, but to break it down into steps. This may help:

  • Get a pencil and paper
  • Draw a line down the middle
  • On the left, write down the steps as you progress through the function calls
  • Then, on the right, back-track up through the intermediate results, until the final value is returned

If it still isn't clear, start at the top-right and go backwards through your steps. Don't be afraid to tear-up the paper and start over.

Find other examples as well to explore. The specific example is not as important as understanding the recursive process itself.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

December 2014

S M T W T F S
 123456
78910111213
14151617181920
21 22 2324252627
28293031   

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    2 user(s) viewing

    2 Guests
    0 member(s)
    0 anonymous member(s)

    Categories