Recursive Confusion

Question

Hello everyone I had a tough time understanding recursive function calls and just when I thought I have understood them, I saw a question which made me realized that I am wrong I am not able to understand the flow of the program

#include <stdio.h>
void fun(int n)
{   
    if(n>0)
    {   
        fun(--n);
        printf("%d\n",n);
        fun(--n);
    }
}   
int main(void) {
    int a;
    a=3;
    fun(a);
    return 0;
}

Answer 1

I believe the cause of confusion is your assumption that the same "n" is used by every call to the function fun(). In fact, that's not the case, since in the C language, argument are passed by value. That is, when fun(3) calls fun(2), a new n is created - specific to one instance of fun(2). Thus after the call to fun(3) within fun(2), the value of n is 2, not or -1.

You should therefore expect...

fun(1) to print 0
fun(2) to print 1
fun(3) to print 2
fun(1) (called from the second call to fun(2)) to print 0

and that's it.

Answer 2

Let's try to understand it with case n=2 and then you should be able to generalize.

fun (2):

What happens inside (flow):

1) n=2: if(n>0) is true and fun(--n) is called with n set to value 1 due to --; (see step below).

2) n=1: Now n=1: again if(n>0) is true and fun(--n) is called with n=0. See step below.

3) n=0: Now n=0; if(n>0) is false, so we return.

I think here is your confusion. From step 3 you are thrown back at step 2 (not step 1). You are thrown actually in step 2 after fun(--n) call - so printf is called with value of n=0, due to decrement. Then again in same place (after printf) fun(--n) is called with value n=-1 however, which will also exit - and eventually you will be thrown at the beginning.

Answer 3

This is the function call for your function when n = 3

f(3)
.f(2) [1]
..f(1) [1]
...f(0) [1]
...Print 0
...f(-1) [2]
..Print 1
..f(0) [2]
.Print 2
.f(1) [2]
..f(0) [1]
..Print 0
..f(-1)[2]

Where . represent the depth of stack and 1 and 2 specify whether its first recursive call from the loop or second.

Because

f(3)

becomes

f(2)
print 2
f(1)

which inturn becomes

f(1)
print 1
f(0)
print 2
f(0)
print 0
f(-1)

Which finally becomes

f(0)
print 0
f(-1)
print 1
f(0)
print 2
f(0)
print 0
f(-1)

Removing all the f(n) when n <= 0

print 0
print 1
print 2
print 0

Answer 4

Here is what happens (pseudocode):

   n = 3
   fun(3);
      n = 2
      fun(2); // first fun(--n)
         n = 1
         fun(1); // first fun(--n)
            n = 0
            fun(0); // first fun(--n)
               return;
            print 0
            n = -1
            fun(-1); // second fun(--n)
               return;
            return;
         print 1
         n = 0
         fun(0); // second fun(--n)
            return;
         return;
      print 2
      n = 1
      fun(1); // second fun(--n)
         n = 0
         fun(0); // first fun(--n)
            return;
         print 0
         n = -1
         fun(-1); // second fun(--n)
            return;
         return;
      return;
   return;

Answer 5

To understand the recursive flow you can instrument your code with few printfs like below. This will show the sequence of flow of function using indentation.

#include <stdio.h>

void printSpace(int num)
{
    while(num > 0)
    {
        printf(" ");
        num--;
    }
}

int NumSpace = 0;
void fun(int n)
{   
    printSpace(NumSpace);
    printf("fun(%d)\n", n);
    NumSpace += 4;
    if(n>0)
    {   
        fun(--n);
        printSpace(NumSpace);
        printf("%d\n",n);
        fun(--n);
    }
    NumSpace -= 4;
}   
int main(void) {
    int a;
    a=3;
    fun(a);
    return 0;
}


Result:
fun(3)
    fun(2)
        fun(1)
            fun(0)
            0
            fun(-1)
        1
        fun(0)
    2
    fun(1)
        fun(0)
        0
        fun(-1) 

Hope this helps.

Answer 6

I would draw a "call tree" to help visualize the program.

The function has those parts

decrement n, call, print, decrement n, call

now you can draw this:

                  0                 -1
            1->0,   print 0, 0->-1,                   0
      2->1,                            print 1, 1->0,                 1->0, .....
3->2,                                                   print 2, 2->1, .....

Start at the bottom left, and go up one line for each call. The program executes from left to right, and you can clearly see the order of the numbers printed.

Answer 7

The output of the program can be understood by iteratively expanding the function calls and removing the conditions; in a pseudocode-manner, this can be done as follows.

fun(3)

Can be expanded to the following.

if(3>0)
{   
    fun(2);
    printf("%d\n",2);
    fun(1);
}

In the follwing steps, the if condition is omitted if it will evaluate to false.

fun(1);
printf("%d\n",1);
fun(0);
printf("%d\n",2);
fun(0);
printf("%d\n",0);
fun(-1);

The calls to fun with non-positive arguments can be omitted as they will generate no output.

fun(1);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

Further expansion yields the following sequence.

fun(0);
printf("%d\n",0);
fun(-1);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

This can be again reduced to the following sequence.

printf("%d\n",0);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

So in total, the output will be as follows.

0
1
2
0

I hope this answers your question; however, it does not provide an intuitive way of describing the generated output.