K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知标准斐波那契数列定义为：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3）
递归实现斐波那契数列的时间复杂度为O(n)
代码def fib(n): return n if n <= 1 else fib(n-1) + fib(n-2)可以正确实现递归求斐波那契第n项
def fib(n): return n if n <= 1 else fib(n-1) + fib(n-2)
递归实现斐波那契数列的空间复杂度比迭代实现更低
递归实现斐波那契数列的核心是将求解第n项的问题分解为求解第n-1项和第n-2项的小问题，符合递归的基本思想