Why does my recursive function print in descending order and then in ascending order?

Question

I have a simple recursive c++ program and I am trying to understand exactly how it works. I understand why the program prints out 3 2 1, but then I don't understand why it goes the other way and prints 1 2 3. I used a hand-simulation and walked through the program step-by-step but still don't understand how the 1 2 3 comes about. I found this article from GeeksForGeeks but am still having difficulty grasping the concept. Any explanation would be awesome.

#include <iostream>

using namespace std;

void test(int n)
{
  if (n > 0)
  {
    cout << n << " ";
    test(n - 1);
    cout << n << " ";
  }
}

int main()
{
  test(3);
  return 0;
} 

Answer 1

The thing is that all the answers don't help you because even if someone got it explained to you, you will stuck in the next algorithm.

I am offering a fundamental approach that helped me a lot with understanding some search algorithms, linked lists, binary trees and much more because I am a simple mind.

What you have to do is figuring out ways to represent the data in the most creative ways you can come up with. Because programming is just flipping data in lots of ways. A few examples I came up with is using plastic cans and post its or grapes and plates, I've seen some indian video guys that draw the data flow on charts or just with circles on a sheet of paper with different colors if you want and that works as follows:

1. put the data on the post its, one for each round. You got a simple algorithm and I would write a "3" because it is passed through the function.
2. The jars, represent the function calls, I would take a jar for every call.
3. Simulate the algorithm bit by bit. Like taping the 3 on the jar -> first cout "3" -> test get called "n - 1" so "2" goes in a new jar (writing 2 on the post it) -> second cout "2" -> test get called "n - 1" so 1 goes again in a new jar. (writing 1 on the post it) ->third cout "1" -> test get called "n - 1" so 0 goes in a new jar. (writing 0 on the post it) - but wait! 0 is not bigger as 0! So that jar won't pass the if command! so the test doesn't gets called again - function over. Now look at your place! you got still 4 jars and the second cout in the function is not even called once - now its time because every jar represents one function call that is not finished and still open. what number is in the jar you put in last? Right, a 1! So "1" get to the cout. Crumple the post it, put the jar back. What is in the next jar? a "2"? bingo - that is printed through the second cout. The last cup has a 3 in it? - right, print it with cout than crumple the post it up. No cups anymore? No data to print out? you done! Thats how the program works! Congrats, because I am sure you grasped it now! :)

Btw. if you come to a point where you don't know where the data flows, every good IDE has a debugger that let you run exactly the steps the program does and it stops after every step. It is really good explained how to use a debugger in alex allain "jump to c++" and he has a whole chapter on how to read and write a program, also a whole chapter about recursion and i think 6 for pointers alone. He gave the tip to find ways to represent data and I hope that helps you as much as it helped me :)

Cheers

Answer 2

To make it clear rewrite the function

void test( unsigned int n )
{
    if ( n )
    {
        std::cout << n << " ";
        test( n - 1 );
        std::cout << n << " ";
    }
}

the following way

void test( unsigned int n )
{
    if ( n )
    {
        std::cout << n << " ";
        std::cout << n << " ";
        test( n - 1 );
    }
}

That is move the second statement

std::cout << n << " ";

above the statement

test( n - 1 );

For the call test( 3 ); of the modified function you will get the following output

3 3 2 2 1 1 

So each recursive call of the function two times outputs the passed value n. I hope it is clear because the function explicitly contains the same statement two times

std::cout << n << " ";
std::cout << n << " ";

Now returning to the original function definition we see that between the two outputs of the same value n the function calls itself with the value n - 1.

So each function call outputs the same value two times but between the outputs the function calls itself recursively.

Now the output can look like

3         3
     |
call itself for 2 

... and so on.

Answer 3

Change your program to

#include <iostream>

using namespace std;

void test(int n)
{
  if (n > 0)
  {
    cout << "enter" << n << " ";  // <- add "enter" here
    test(n - 1);
    cout << "exit" << n << " ";   // <- add "exit" here
  }
}

int main()
{
  test(3);
  return 0;
} 

and you will see next output

enter3 enter2 enter1 exit1 exit2 exit3

You can think about recursive calls as operations with a stack. There are two operations: push and pop. What your program does is

push test 3
push test 2
push test 1
pop test 1
pop test 2
pop test 3

On every push and pop you do cout and thus see the output 3 2 1 1 2 3.

Here you can find more about recursion.

Answer 4

It's because you have the cout statement after calling the "test" method in your if-statement. After it walks down all the method calls and hits the base case, it then returns out of each of those method calls moving on to the next line (the cout statement) in the reverse order the methods got called in.

Answer 5

The order of function calls in your recursion looks something like this:

test(3)
-- cout << 3 << " ";
-- test(2)
-- -- cout << 2 << " ";
-- -- test(1)
-- -- -- cout << 1 << " ";
-- -- -- test(0)
-- -- -- cout << 1 << " ";
-- -- cout << 2 << " ";
-- cout << 3 << " ";