Recursion with functions in C++

Question

I have problem understanding this code:

#include <iostream>
using namespace std;

void Print_numm(int numm){
    cout<<numm;
    if (numm<=4) {
        Print_numm(numm+1);
    }
    cout<<numm;
}


int main() {
    Print_numm(1);
    return 0;
}

The output is 1234554321. I understand the recursion up until it prints 123455. But why the compiler prints the rest of of numbers down to 1? Does the compiler do the second "cout" every time? And if so how it keeps the numbers until they are printed up to 5 and then prints the rest downward?

Answer 1

Since the condition numm<=4 become false at numm=5. Therefore numm stops incrementing and rest of the code of the previously calling functions executed.

Answer 2

The execution would be easier to visualize if you added some extra diagnostics to your code. Consider this change:

#include <iostream>
using namespace std;

void Print_numm(int numm){
    cout << "enter: " << numm << endl;
    if (numm<=4) {
        Print_numm(numm+1);
    }
    cout << "exit: " << numm << endl;
}


int main() {
    Print_numm(1);
    return 0;
}

Which produces:

enter: 1
enter: 2
enter: 3
enter: 4
enter: 5
exit: 5
exit: 4
exit: 3
exit: 2
exit: 1

You can also use a debugger to step through to help you understand this better.

One important code understanding principle. Adding good diagnostics greatly decreases the amount of mental effort and aptitude required to understand what is happening.

Answer 3

Are you familiar with a stack?

The function calls itself,and prints every number upwards,then it returns from the final recursive call,going downwards through the numbers,as it return from recursion repeatedly.It just executes the rest of the code that it contains after the recursive call.

A simple representation of this is:

    print_numm(1):
    cout << 1
    print_numm(1+1):
        cout << 2
        print_numm(2+1):
            cout << 3
            print_numm(3+1):
                cout << 4
                print_numm(4+1):
                    cout << 5
//now the number is bigger than 4 so the function
//will return from recursion
                    cout << 5
//now the function is done,but the function that called print_numm(5) is waiting to finish
//so it executes the rest of the code printing 4,same with all waiting for print_numm(4) and so on
                cout << 4
            cout << 3
        cout << 2
    cout << 1

Answer 4

You can see that it would do this (assuming it returns).

cout<<1;
Print_numm(2);
cout<<1;

which can be expanded to:

cout<<1;
cout<<2;
Print_numm(3);
cout<<2;
cout<<1;

and then eventually output "1234554321".

Answer 5

Here's how the code get's executed, you can easily tell this way why you get the output in discussion:

Print_numm(1)->
    cout<<1
    Print_numm(2)->
        cout<<2
        Print_numm(3)->
            cout<<3
                Print_numm(4)->
                cout<<4
                    Print_num(5)->
                        cout<<5
                        cout<<5
                cout<<4
            cout<<3
        cout<<2
    cout<<1

The second cout is placed after the recursive call, this means that it will get executed after all the inner calls return.

Answer 6

The function recurses from 1 to 5, and these numbers are output in the first call to cout << numm (the first line of the Print_numm function. Once the if statement evaluates to false the recursion starts to unwind, and as the calls to Print_numm return they encounter the final cout << numm line on the last line of the function and print from 5 to 1.

Answer 7

If you visualize the execution of the call it will be easier to understand:

Print_numm(1)
-> cout 1
-> Print_numm(2)
--> cout 2
-->Print_numm(3)
---> cout 3
---> Print_numm(4)
----> cout 4
----> Print_numm(5)
-----> cout 5
-----> cout 5
----> cout 4
---> cout 3
--> cout 2
-> cout 1