C++ Recursion Issue

Question

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 bump 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;
}

Answer 1

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