递归求fabonacci数列 pta.docx
需积分: 0 90 浏览量
2024-05-12
09:33:47
上传
评论
收藏 16KB DOCX 举报
斐波那契数列（Fibonacci sequence）是一个经典的数列，它由以下递归关系定
义：
[ F(n) = F(n-1) + F(n-2) ]
其中，( F(0) = 0 ) 和 ( F(1) = 1 )。
在编程中，递归是一种实现斐波那契数列的直观方法。以下是使用递归求斐波那
契数列的 Python 代码示例：
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
#
测试递归函数
for i in range(10):
print(f"Fibonacci({i}) = {fibonacci(i)}")
这段代码定义了一个名为 fibonacci 的函数，它接受一个整数 n 作为参数，并返
回斐波那契数列的第 n 个数。递归的基本情况是当 n 为 0 或 1 时，直接返回 n。
对于更大的 n，函数会递归地计算 F(n-1)和 F(n-2)，然后将它们相加以得到
F(n)。
注意事项
虽然递归方法简单直观，但它并不是计算斐波那契数列的最高效方法。递归方法
在每次函数调用时都会重复计算相同的值，导致时间复杂度为 O(2^n)，这在 n
较大时会导致性能问题。
为了提高效率，可以考虑以下替代方法：
资源评论
