递归次数的计算斐波那契数列Fn定义如下：F0=0,F1=1,Fn=Fn-1+Fn-2,n=2,3,…请就此斐波那契数列,回答下列问题：①（7分）在递归计算Fn的时候,需要对较小的Fn－1,Fn－2,…,F1,F0精确计算多少次?（清

Question

递归次数的计算
斐波那契数列Fn定义如下：F0=0,F1=1,Fn= Fn-1 + Fn-2,n=2,3,… 请就此斐波那契数列,回答下列问题：①（7分）在递归计算Fn的时候,需要对较小的Fn－1,Fn－2,…,F1,F0精确计算多少次?（清华大学2000年研究生入学试题)

Answer 1

C(n) 表示计算次数 则C(0) = 1; C(1) = 1; C(n) = C(n-1) + C(n-2) + 1; n>=2; 所以: C(2) = 1+1+1 =3 C(4) = 3+1+1 =5; C(5) = 5+3+1 =9