计算斐波那契数列第n项的函数定义如下： int fib(int n){ if(n==0) return 1; else if(n==1) return 2; else return fib(n-1)+fib(n-2); } 若执行函数调用表达式fib(10),函数fib被调用的次数是： 117 137 157 177
int fib(int n){ if(n==0) return 1; else if(n==1) return 2; else return fib(n-1)+fib(n-2); }
这题相当于再求一次费波那奇数列。定义g(n)函数表示计算fib(n)而调用的fib函数的次数
则
g(10) = g(9) + g(8) + 1(1是调用fib(10)需要执行一次fib函数)
。。。。
g(2) = g(1) + g(0) + 1
g(1) = 1
g(0) = 1
可以求得g(10) = 177
