C++ Recursion Issue

I feel a little dumb asking this, but here we go...

When trying to follow the Recursion example at the following website http://www.cplusplus.com/doc/tutorial/functions2/, I ran into a road b开发者_如何学Cump that has me perplexed.

I altered the code slightly just to get my head around the code in the recursion example and I pretty much have my head around it, but I can't figure out why the variable 'n' increments in 'Pass B' when I have not told the program to increment 'n'.

Could you please help explain this?

#include <stdlib.h>
#include <iostream>

using namespace std;

long factorial (long n)
{
  if (n > 1)
{
   long r(0);
   cout << "Pass A" << endl;
   cout << "n = " << n << endl;
   cout << "r = " << r << endl;

   r = n * factorial (n-1);

   cout << "Pass B" << endl;  
   cout << "n = " << n << endl;
   cout << "r = " << r << endl;
   return (r);
}
  else
   return (1);
}

int main ()
{
  long number;
  cout << "Please type a number: ";
  cin >> number;
  cout << number << "! = " << factorial (number) << endl;
  system ("pause");
  return 0;
}

---

That's because you are unrolling the recursion.

You are not really incrementing n you are just returning to previous function call where n was n+1 before you called factorial(n-1) ...

When you start you go up to

   r = n * factorial (n-1);

which will cause another function call to the factorial.

You keep doing that (start from beginning of your function and go up to the call to factorial with n decremented by 1) until you eventually end up in a function call to factorial where n<=1.

In which case you return 1, but you return to previous call of factorial where n was 2, you do the multiplication (n * whatever was returned by factorial) and you finish the B path of that call and return r.

But you again return to the previous function call where you do the multiplication part and finish the B path and so on ...

factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1)
        return 1
      return r
    return r
  return r
return r

---

You see all "Pass A"-s in order and then all "Pass B"-s in reverse order which gives the impression that n increments eventhough you only see the originally passed n's.

---

It seems to me that your program works correctly and should output something like this for number=3 (Line breaks removed for readability):

Pass A n=3 r=0 [1]

Pass A n=2 r=0 [2]

Pass B n=2 r=2 [3]

Pass B n=3 r=6 [4]

So I think I can see how you would conclude that the n is incrementing in pass B but this in fact not the case. You need to keep in mind that n is a function local variable so in this case the n printed in [3] is a DIFFERENT instance of the local variable to the n in [4].

The values of n printed in [1] and [4] are from the top call of the function (where n=3), the values printed in [2] and [3] are the call in the top version of factor (i.e n-1).

---

If you notice, Pass B is not really passing through the function the second time, it only print the results of the recursion.

So A print 4, 3, 2, etc, while backwords B prints 4 3 2 1 (ie 2 3 4)

Please type a number: 4
Pass A
n = 4
r = 0
Pass A
n = 3
r = 0
Pass A
n = 2
r = 0
Pass B
n = 2
r = 2
Pass B
n = 3
r = 6
Pass B
n = 4
r = 24
4! = 24
Press any key to continue . . .

Try replacing the second r prints as

   cout << "Pass B" << endl;  
   cout << "n = " << n << endl;
   cout << "r = " << r << " --- NOTICE RESULT ACCUMULATING AS WE UNNEST THE RECURSION" <<endl;

PS C:\temp> .\r.exe 4
Please type a number: 4
Pass A
n = 4
r = 0
Pass A
n = 3
r = 0
Pass A
n = 2
r = 0
Pass B
n = 2
r = 2 --- NOTICE RESULT ACCUMULATING
Pass B
n = 3
r = 6 --- NOTICE RESULT ACCUMULATING
Pass B
n = 4
r = 24 --- NOTICE RESULT ACCUMULATING
4! = 24
Press any key to continue . . .

---

Pass B is printed when it is "unwinding" the recursion. It recursed until it hit the "else return (1);" part and then started backing out. Because it called itself with one less for n each time on the way in, it appears to be incrementing as it backs out.

---

The value of n in pass A and pass B will always be the same as you are not changing it anywhere in between. You pass n-1 to a recursive call but that does not change the value of n.

The reason why you might be confused is that you don't see pass A and pass B for a given n (n>2) next to each other.

When n=2, you'll see:
pass A for n=2
pass B for n=2

When n=3, you'll see:
pass A for n=3
pass A for n=2 // cuz of recursive call.
pass B for n=2
pass B for n=3 // looks like n has increment here..but this 'pass B' pairs with first pass A

---

Because that's when the recursion rewinds.

Maybe it would be easier to think about the case when n is 2. In that case you enter the conditional block and recurse after "Pass A". When you recurse n is 1, and so you return through the else block. When you return you are back at the previous frame of the recursion, where n is 2. r gets updated according to the result of the recursion call, 2*1, but n remains 2 as in the previous frame.

factorial(2)
  factorial(1)
factorial(2)

If n would be initially any larger value then you'd keep rewinding, and n would restore its value to each value it had prior to each recursion.

factorial(3)
  factorial(2)
    factorial(1)  // returns 1
  factorial(2)    // r=2*1
factorial(3)      // r=3*2

---

Some of the answers use indentation to make it easier to understand what's happening - you case use the same effect to make your own debug output more comprehensible: Try and change your function to something like this:

long factorial (long n, std::string prefix= "") // default parameter
  ...
   cout prefix << "Pass A" << endl;
   cout prefix << "n = " << n << endl;
   cout prefix << "r = " << r << endl;

   r = n * factorial (n-1, prefix+ "  "); // increase indentation
   ...etc...

My use of std::string may be a bit flaky, but you'll get the idea. Your output should now look like this.

Please type a number: 4

Pass A
n = 4
r = 0
  Pass A
  n = 3
  r = 0
    Pass A
    n = 2
    r = 0
    Pass B
    n = 2
    r = 2
  Pass B
  n = 3
  r = 6
Pass B
n = 4
r = 24

4! = 24