Quote:
Originally Posted by 357mag
All I see is a succession of function calls, over and over. What I don't see is where the actual calculations are carried out. The return statement does not say return 4 * 3, or return 3 * 2, or return 2 * 1, or whatever. It actually says return 4 * factorial(3). Then the function calls itself again, and it says return 3 * factorial(2). Then the function calls itself again, and it says return 2 * factorial(1). I realize that somehow it ends up as 4 * 3 * 2 * 1, but the code doesn't really look like that to me. How are the actual calculations carried out? All I see is just the function calling itself until we get down to where the value in number is 1, meaning the function terminates.
|
I think I see where you're misunderstanding it -- I had that same problem.
I'm going to try to explain.
Say you have the following code:
#include <iostream>
int square( int n ) {
std::cout << "Hello! The program is in square()" << std::endl;
return n * n;
}
int cube( int n ) {
std::cout << "Hello! The program is in cube()" << std::endl;
int s = square( n );
std::cout << "Hello! The program has returned to cube()" << std::endl;
return s * n;
}
int main() {
std::cout << cube( 3 ) << std::endl;
}
And if you were to run it:
Hello! The program is in cube()
Hello! The program is in square()
Hello! The program has returned to cube()
27
As you can see, in order to figure out the cube of a number, first the square must be found. The cube() function won't be able to return a result until the square() function is complete because the result of square() is needed. When the square function finishes and returns its result, we are returned to the scope of the cube() function which then processes the result and returns its own. Makes sense?
Recursion is exactly the same, except that instead of calling another function, the same function is called again.
For example, consider that
n is equal to 2.
return n * factorial( n - 1);
In this example, the factorial function is called with an argument of 1. That call results in a 1 (1! = 1), and is multiplied by 2 to produce 2.
Recursion is just a chain of calls. The chain only ends when the last call completes. At that point, the calculated value trickles upward and is returned as a final result.
For example, here is the evaluation of factorial(4):
4 * factorial( 3 )
4 * 3 * factorial( 2 )
4 * 3 * 2 * factorial( 1 )
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24
I hope that helped.
