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 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:
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:
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, 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.
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 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:
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:
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.
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
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 ]
← September 2016 →
S | M | T | W | T | F | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 |
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
1 user(s) viewing
1 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)