递归·单选训练1

第 1 题（单选）

设有递归函数 f(n) = f(n-1) + f(n-2) 且 f(0)=f(1)=1，计算 f(5) 的过程中，f(2) 被调用了多少次？

{{ select(1) }}

• 2
• 3
• 4
• 5

第 2 题（单选）

下列关于递归算法的说法，错误的是（）。

{{ select(2) }}

• 递归必须有终止条件
• 递归算法都可以用循环实现
• 递归算法一定比循环效率高
• 递归调用会消耗系统栈空间

第 3 题（单选）

下面哪个是计算斐波那契数列第n项的递归式？

{{ select(3) }}

• F(n)=n*F(n-1)
• F(n)=F(n-1)+F(n-2)
• F(n)=F(n-1)+1
• F(n)=2*F(n/2)

第 4 题（单选）

已知一个递归函数 def f(n): return 1 if n<=1 else f(n-1)+n，则f(5)的值为（）。

{{ select(4) }}

• 10
• 15
• 16
• 1

第 5 题（单选）

对于递归式T(n)=T(n-1)+O(1)，其时间复杂度为（）。

{{ select(5) }}

• O(n)
• O(log n)
• O(n^2)
• O(2^n)