[Solved] Can anyone explain how this recursion code works exactly and what happens in the programs stack or in memory step by step? [closed]

Question

It will be much easier to understand what is happening if you start with what happens closer to the base case of the recursion. Suppose you have fun(0) in your main. inside the body of fun this happens:

void fun(int n)
{
    if(n > 0) //this is false, so function does nothing
    {
        fun(n-1);
        printf("%d ", n);
        fun(n-1);
    }
}

now what if you have foo(1) in your main ?

void fun(int n)
{
    if(n > 0) //this is true, lets execute the block
    {
        fun(n-1); //call fun(0), this does nothing
        printf("%d ", n); //print value 1
        fun(n-1);//call fun(0) again, does nothing
    }
}

so you can see that fun(1) will print value 1, how about fun(2)?

void fun(int n)
{
    if(n > 0) 
    {
        fun(n-1);        //call fun(1), prints 1
        printf("%d ", n);//print value 2
        fun(n-1);        //call fun(1), prints 1
    }
}

so as you can see foo(2) will print “1 2 1”, similarly foo(3) will print 1 2 1 3 1 2 1

how the stack builds up and unwinds is very interesting and you should sit down with pen and paper and figure that out.

This is called pure structural recursion, you get closer to base case every step of the recursion.

Accepted Answer