Confused about C++ recursion

Question

I don't understand how recursion works too well.

void f(int n)
{
  if (n == 1)cout<<1<<" ";
  else
  {
    f(n - 1);
    cout<<n<<" ";
    f(n - 1);
  }

If i let n = 4, this will output 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1. Why is that? First, n gets smaller and smaller until it gets to 1, and after that, what happens? I can't really understand what these 2 calls do, and why even the second one is there, since the first one gets called first.

Answer 1

Here below a recursive explanation of what is happening.

When n gets down to n=1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the third line of the else statement and returns.

On return, we are brought back to the previous iteration of n, n = 3, that now moves out of the first line of the else statement down to the second, which prints 3, then on the third which is another recursive call that restarts the function with n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 4, that now moves out of the first line of the else statement down to the second, which prints 4, then on the third which is another recursive call that restarts the function with n = n - 1 = 3.

So we go through the first statement of else again, we get n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 3, that now moves out of the first line of the else statement down to the second, which prints 3, then on the third which is another recursive call that restarts the function with n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 2.

So we go through the first statement of else again, we get n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

On return, we are brought back to the previous iteration of n, n = 2, that now moves out of the first line of the else statement down to the second, which prints 2, then on the third which is another recursive call that restarts the function with n = n - 1 = 1.

When n gets down to n = 1 the if part kicks in, prints 1, then returns.

Answer 2

Recursive functions work exactly like non-recursive functions.
In particular, when one returns it returns to its immediate caller.
That is, the call that had n == 1 will return to a call that had n == 2, which will return to a call that had n == 3, and so on, and the calling function keeps going in the regular way.

Your example works like these non-recursive functions, whose flow you can probably figure out:

void f_1()
{
    cout << 1 << " ";
}

void f_2()
{
    f_1();
    cout << 2 << " ";
    f_1();
}

void f_3()
{
    f_2();
    cout << 3 << " ";
    f_2();
}

void f_4()
{
    f_3();
    cout << 4 << " ";
    f_3();
}

Answer 3

The algorithm is, when reaches the end of recursion:

• Print n
• Return and print the n + 1 who called n
• Print the first n again

Here, the n when the recursion ends is 1. That's why every other number in your sequence is 1 (corresponds to the 1st and 3rd points)

If you remove the 1's, your sequence is:

2 3 2 4 2 3 2

Now, the n when the recursion "ends" is 2 (obviosuly it ended on 1 but now we're going one level above), so we repeat the algorithm.

If you remove the 2s...

3 4 3

Again, 3 is the n... and your highest level is the remaining 4.

You see a symmetric sequence due to your symmetric algorithm:

    f(n - 1);
    cout<<n<<" ";
    f(n - 1);