Answer is 8 but how?

Question

How does the following code work?

#include <stdio.h>
#include <conio.h>
void main () {
    int n = 6, d;
    int func (int n) {
        int x, y;
        if (n <= 1)
            return n;
        x = func (n - 1);
        y = func (n - 2);
        return (x + y);
    }
    d = func (6);
    printf ("%d", d);
}

The answer is 8 but don't know why? please explain step wise step.

Answer 1

Recursive functions often work in ways that are obscured to new users of recursive functions. One of the best ways to learn the logic of a recursive function is to look at what is actually taking place. This is why you often hear that 'recursive functions are less readable than ordinary functions' Take a look at the actual flow:

//how the code is working?
#include <stdio.h>
//#include <conio.h>
int main () {
    int n = 6, d;
    int func (int n) {
        printf (" entering func (%d)\n", n);
        int x, y;
        if (n <= 1)
            return n;
        x = func (n - 1);
        printf ("  x = %d\n", x);
        y = func (n - 2);
        printf ("  y = %d\n", y);
        printf ("    returning (%d + %d) = %d\n", x, y, x + y);
        return (x + y);
    }
    d = func (n);
    printf ("%d", d);
    return 0;
}

output:

$ ./bin/fun6
 entering func (6)
 entering func (5)
 entering func (4)
 entering func (3)
 entering func (2)
 entering func (1)
  x = 1
 entering func (0)
  y = 0
    returning (1 + 0) = 1
  x = 1
 entering func (1)
  y = 1
    returning (1 + 1) = 2
  x = 2
 entering func (2)
 entering func (1)
  x = 1
 entering func (0)
  y = 0
    returning (1 + 0) = 1
  y = 1
    returning (2 + 1) = 3
  x = 3
 entering func (3)
 entering func (2)
 entering func (1)
  x = 1
 entering func (0)
  y = 0
    returning (1 + 0) = 1
  x = 1
 entering func (1)
  y = 1
    returning (1 + 1) = 2
  y = 2
    returning (3 + 2) = 5
  x = 5
 entering func (4)
 entering func (3)
 entering func (2)
 entering func (1)
  x = 1
 entering func (0)
  y = 0
    returning (1 + 0) = 1
  x = 1
 entering func (1)
  y = 1
    returning (1 + 1) = 2
  x = 2
 entering func (2)
 entering func (1)
  x = 1
 entering func (0)
  y = 0
    returning (1 + 0) = 1
  y = 1
    returning (2 + 1) = 3
  y = 3
    returning (5 + 3) = 8

Answer 2

Let's build an execution tree for func(n). If it's called with n <= 1, it returns n. Otherwise, it returns func(n-1)+func(n-2).

So,

func(6)=
func(5)+func(4)=
func(4)+func(3)+func(3)+func(2)=
func(3)+func(2)+func(2)+func(1)+func(2)+func(1)+func(1)+func(0)=
func(2)+func(1)+func(1)+func(0)+func(1)+func(0)+func(1)+func(1)+func(0)+func(1)+func(1)+func(0)=
func(1)+func(0)+func(1)+func(1)+func(0)+func(1)+func(0)+func(1)+func(1)+func(0)+func(1)+func(1)+func(0)=
1+0+1+1+0+1+0+1+1+0+1+1+0=
8