-1

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.

Uttam
  • 718
  • 6
  • 19
  • 2
    The confusing part is the combining of recursion and iteration at the same time. – drescherjm Nov 12 '21 at 14:58
  • You haven't included the full output for `fun(5)`. The full output does not fit in a comment – Caleth Nov 12 '21 at 15:01
  • `fun(5)` call outputs five identical sections. Each starts with `5` and then the output of `fun(4)` call. In turn, `fun(4)` call outputs five identical sections - each starts with `4` and then the output of `fun(3)` call. And so on. – Igor Tandetnik Nov 12 '21 at 15:02
  • 1
    [This](https://coliru.stacked-crooked.com/a/66169f068714754c) produces the output you claim. Your code produces different output – Caleth Nov 12 '21 at 15:03
  • 2
    The output you cite is not produced by the code shown. `fun(2)` call should produce five `1`s in a row, not two. – Igor Tandetnik Nov 12 '21 at 15:04
  • I'd consider "playing computer" with pencil and paper: write down each step and value. Alternatively, step through the code with a debugger, but I think playing computer is more effective in the long run. – Dave Newton Nov 12 '21 at 15:04
  • 1
    @Caleth Your code is different. Your loop runs `n` times, the OP's loop runs exactly 5 times. – Igor Tandetnik Nov 12 '21 at 15:05
  • @IgorTandetnik yes, and produces the output the OP claims is the output of his code – Caleth Nov 12 '21 at 15:05
  • Here is the output of the code that is currently in the question (which differs from the question output): [https://ideone.com/ZvLGih](https://ideone.com/ZvLGih) – drescherjm Nov 12 '21 at 15:07
  • I think your copy-and paste is broken, and it should have said `i < n`, not `i < 5`. – molbdnilo Nov 12 '21 at 15:12
  • One of the best ways to understand recursion is to run your program line by line in a [debugger](https://stackoverflow.com/q/25385173/12149471), while monitoring the values of all variables. – Andreas Wenzel Nov 12 '21 at 16:37
  • @Caleth yup perhaps the output has broken while coping it. – Uttam Nov 12 '21 at 16:58
  • It's really hard to understand :( after seeing the answers I'm still not understanding it. I think debuger will help @DaveNewton – Uttam Nov 12 '21 at 17:00

2 Answers2

3

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 << " ";
                    }    
                }    
            }    
        }
    }    
}
molbdnilo
  • 64,751
  • 3
  • 43
  • 82
  • I'm unable to understand the logic but you had done really handwork to make me understand :) thankyou so mch – Uttam Nov 12 '21 at 17:02
0

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

thelaw
  • 1
  • 3