(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次
