Can someone help me understanding this recursion code-CodePudding

I am currently having hard time to understand this code because I'm not pro in recursion. So, I wanna someone to explain the logic behind this.

#include <iostream>

using namespace std;

void fun(int n){
    if(n==0){
        return;
    }
    for (int i = 0; i < 5; i  ) {
        cout<<n<<" ";
        fun(n-1);
    }
}
int main()
{
    fun(5);
    return 0;
}

Output- https://ideone.com/ZvLGih

I understood the output up to 5 4 3 2 1 then when the base condition hits then after I'm not able to understand the logic.

CodePudding user response：

Assuming that i < 5 is a typo and should have been i < n, it works exactly like this completely non-recursive program:

void fun0()
{
    return;
}

void fun1()
{
    for (int i = 0; i < 1; i  ) {
        cout << 1 << " ";
        fun0();
    }    
}

void fun2()
{
    for (int i = 0; i < 2; i  ) {
        cout << 2 << " ";
        fun1();
    }    
}

void fun3()
{
    for (int i = 0; i < 3; i  ) {
        cout << 3 << " ";
        fun2();
    }    
}

void fun4()
{
    for (int i = 0; i < 4; i  ) {
        cout << 4 << " ";
        fun3();
    }
}

void fun5()
{
    for (int i = 0; i < 5; i  ) {
        cout << 5 << " ";
        fun4();
    }    
}

int main()
{
    fun5();
}

or this program that only has a main:

int main()
{
    for (int i = 0; i < 5; i  ) {
        cout << 5 << " ";
        for (int i = 0; i < 4; i  ) {
            cout << 4 << " ";
            for (int i = 0; i < 3; i  ) {
                cout << 3 << " ";
                for (int i = 0; i < 2; i  ) {
                    cout << 2 << " ";
                    for (int i = 0; i < 1; i  ) {
                        cout << 1 << " ";
                    }    
                }    
            }    
        }
    }    
}

CodePudding user response：

Understanding recursion is difficult to do when you get to more than two levels of recursion. It's impossible to keep all of the recursive calls in your mind at one time, so the best way to understand it would be to work through the base cases. Look for patterns between calling fun(1), fun(2), and fun(3).

fun(1): 1 1 1 1 1

fun(2): 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1

fun(3): long string of numbers you can view in your compiler

It looks like it just prints a number n, followed by 5 iterations of the number n-1, along with all of the iterations of n-k down to k=n. So for fun(3) it would begin: 3 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 3