下面是一个使用递归方法编写斐波那契函数的示例代码:
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# 测试斐波那契函数
num = 10
print("斐波那契数列前", num, "个数为:")
for i in range(1, num+1):
print(fibonacci(i), end=" ")
运行以上代码,将输出斐波那契数列的前10个数:0 1 1 2 3 5 8 13 21 34。
该函数使用递归的方式计算斐波那契数列。当n为1时返回0,当n为2时返回1,否则返回前两个斐波那契数的和。该函数的时间复杂度为O(2^n),因为在计算fibonacci(n)时需要计算fibonacci(n-1)和fibonacci(n-2),而每个函数又会继续递归调用。因此,使用递归方法计算较大的斐波那契数会很慢。
为了提高效率,可以使用迭代方法计算斐波那契数列。以下是一个使用迭代方法编写斐波那契函数的示例代码:
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
prev_prev = 0
prev = 1
current = 0
for i in range(3, n+1):
current = prev_prev + prev
prev_prev = prev
prev = current
return current
# 测试斐波那契函数
num = 10
print("斐波那契数列前", num, "个数为:")
for i in range(1, num+1):
print(fibonacci(i), end=" ")
运行以上代码,将输出斐波那契数列的前10个数:0 1 1 2 3 5 8 13 21 34。
该函数使用迭代的方式计算斐波那契数列。通过使用三个变量prev_prev、prev和current来记录前两个斐波那契数和当前斐波那契数。在每次循环中,计算current,并更新prev_prev和prev的值。该函数的时间复杂度为O(n),计算过程中只进行了一次循环。因此,使用迭代方法计算斐波那契数会更快。