Funny Febo !

$1,1,2,3,5,8,13,21\dots$ The sequence given above is the Fibonacci sequence which can be generalize as:

$F_0=1$ , $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ where $n \ge 2$ .

1
2
3
4
5
6
7
8

int F(int n){
    if (n==0 || n==1){
        return 1;
    }
    else{
        return F(n-1)+F(n-2);
    }
}

For exapmle: When we want to find $F_{2}$ we call the recursive function $F_{2}$ which then calls $F_{0}$ and $F_{1}$ . Hence we say the function is called thrice.

Here is a list which gives the Fibonacci sequence in the first column and the number of function calls to get it:

• 0 $\rightarrow$ 1

• 1 $\rightarrow$ 1

• 2 $\rightarrow$ 3

• 3 $\rightarrow$ 5

• 4 $\rightarrow$ 9

• 5 $\rightarrow$ 15

• 6 $\rightarrow$ 25

• 7 $\rightarrow$ $\boxed{41}$

.

.

.

Since we know that to find $n^{th}$ term we have to find $(n-1)^{th}$ and $(n-2)^{th}$ terms. Hence the first call of function is F(n) then the remaining calls for F(n-1) and F(n-2). Therefore N(F(n))=1+N(F(n-1))+N(F(n-2)).

The image below is a tree that shows the total number of function calls to find $6^{th}$ term:

• The $recursive \, function$ in C++ that can do the task of finding the $total \, number \, of \, function \, calls$ is:

1
2
3
4
5
6
7
8

int Nf(int n){
    if (n==0 || n==1){
        return 1;
    }
    else{
        return Nf(n-1)+Nf(n-2)+1;
    }
}

I hope that might help you understand the logic behind that function more clearly.

Here is my implementatio :

cnt = 0
def fibo(n) :
         global cnt
         cnt += 1
         if n < 2 : return 1
         else :
              return fibo(n-1)+fibo(n-2) 

 print cnt