Regarding Recursive Functions in C++ (Beginner Level)

Question

So I've just started C++ programming, and am a little stuck on one particular program that was used to demonstrate how recursive functions work. I do know the premise of recursive functions, that being a function which calls itself until an exit condition has been met. I understood the concept using the program for factorials,

int factorial(int n)
{
   if (n==1)
      {
          return 1;
      }
   else
      {
          return n*factorial(n-1);
      }
}

the if statement being the exit condition in the above code.

However, the code that tripped me up was from this link: http://www.cprogramming.com/tutorial/lesson16.html

specifically this code:

#include <iostream>
using namespace std;

void printnum ( int begin )
{
  cout<< begin<<endl;
  if ( begin < 9 )         // The base case is when begin is greater than 9
  {                           //  for it will not recurse after the if-statement
      printnum ( begin + 1 ); 
  }
  cout<< begin<<endl;         // Outputs the second begin, after the program has
                               //  gone through and output
}
int main() 
{
    printnum(1);
    return 0;
}

OP:
1
2
3
4
5
6
7
8
9
9
8
7
6
5
4
3
2
1

In the immediately above code, I understand the output till the first 9. But after that, why does the cout statement following the if loop cause the begin variable to start counting backwards till it reaches the value it originally was when printvalue was first called? I suppose I don't really understand the exit condition here.

Not sure what I'm missing, and any help would be greatly appreciated.

Thanks.

Answer 1

why does the cout statement following the if loop cause the begin variable to start counting backwards till it reaches the value it originally was when printvalue was first called?

To start with, there is no loop. There is call stack which you need to understand. Recursive call stops when (begin < 9) becomes false i.e. when begin = 9. You are seeing the call stack unwinding.

First cout in the function is printing sequence [1..9], and second cout is printing the decreasing sequence [9..1].

Your code execution is like this:

cout<< 1 <<endl;  //enter1
  cout<< 2 <<endl;  //enter2
    cout<< 3 <<endl;  //enter3
      ...
         cout<< 8 <<endl;  //enter8
            cout<< 9 <<endl;  //enter9
            cout<< 9 <<endl;  //exit9
         cout<< 8 <<endl;  //exit8
      ...
    cout<< 3 <<endl;  //exit3
  cout<< 2 <<endl;  //exit2
cout<< 1 <<endl;  //exit1

Answer 2

Each begin is unique and belongs to the "current" active function – its value never changes.

Recursive functions work exactly like other functions; it doesn't matter to one what the parameter of another is named.

If you had these:

void f(int x);

void g(int x)
{
    cout << x << endl;
    f(x+1);
    cout << x << endl;
}

you would be very surprised (I hope) if g printed two different numbers.

Your recursion works exactly like this (much smaller) example that uses unique functions instead of recursion with a parameter:

void printnum_3()
{
    cout << 3 << endl;
    cout << 3 << endl;
}

void printnum_2()
{
    cout << 2 << endl;
    printnum_3();
    cout << 2 << endl;
}

void printnum_1()
{
    cout << 1 << endl;
    printnum_2();
    cout << 1 << endl;
}

int main()
{
    printnum_1();
}

Answer 3

So, lets see what happens when printnum(1) is called. begin equals 1, it is printed with cout and then printnum(2) is called. But what happens when the program leaves printnum(2) function? It continues to execute printnum(1) from the place, where printnum(2) was called. So, the next line to execute is cout << begin. begin still equals 1, because we are executing printnum(1) function. This is why 1 is printed once again at the end. The situation is totally the same with other function calls. For example, when printnum(9) is called, it prints 9, then the if check fails (begin is not less, than 9) and then 9 is printed once again.