Fibonacci Number (費氏數列)

(1) Write a recursive finction in C
(2) Fib (5) = ?
(3) Fib(5)求值過程中, 共呼叫幾次Fib Function?

Ans:

(1)

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

(2)
Fib(5) = Fib(4) + Fib(3)
= Fib(3) + Fib(2) + Fib(2) + Fib(1)
= Fib(2) + Fib(1) + Fib(1) + Fib(0) + Fib(1) + Fib(0) + 1
= Fib(1) + Fib(0) + 1 + 0 + 1 + 0 + 1
= 1+0+1+0+1+0+1
= 5

(3)
共15次