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

Factorial :wikipedia

This is an example of a

Recursion :wikipedia

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

So what is factorial(2) ?

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

So what is factorial(1) ?

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

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,

This value 1 is the value returned by factorial(1), which is fed back to:

This value (2 * 1 = 2) is the value returned by factorial(2), which is fed back to:

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

The value returned by factorial(3) is:

0 is the

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:

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

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

wiki said:

In mathematics, the

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

**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 ]

### Tags

### My Blog Links

### Recent Entries

### Recent Comments

### Search My Blog

### 10 user(s) viewing

**10**Guests

**0**member(s)

**0**anonymous member(s)