c - Answer is 8 but how? -

how 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 8 don't know why? please explain step wise step.

let's build execution tree func(n). if it's called n <= 1, returns n. otherwise, 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