用非递归函数写出斐波那契数列

好的，以下是用非递归函数实现斐波那契数列的代码：

def fibonacci(n):
    if n < 0:
        return "Invalid input"
    elif n == 0 or n == 1:
        return n
    else:
        a, b = 0, 1
        for i in range(2, n+1):
            c = a + b
            a, b = b, c
        return b

这里用到了迭代的思想，从前往后计算每一个斐波那契数。当n为0或1时，直接返回n作为第n个斐波那契数；否则，从第二项开始循环计算每一项，每一项都是前两项的和。最后返回第n项的值。

相关问题

写出斐波那契数列的非递归算法

斐波那契数列是一个数列，其中每个数字都是前两个数字之和，通常从0和1开始。非递归算法是通过循环而不是函数的嵌套调用来计算这个序列，这样可以避免函数调用带来的性能开销。以下是使用迭代方法（也称为循环）来计算斐波那契数列的一个例子：

def fibonacci_non_recursive(n):
    if n <= 0:
        return "输入的数值必须大于0"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, a + b
        return b

# 示例
print(fibonacci_non_recursive(10))  # 输出：55

在这个算法中，我们首先检查基本情况，然后初始化变量a和b作为斐波那契序列的前两个元素。接着，我们在循环中逐步更新这两个值，直到达到目标位置n。

已知斐波那契数列为{0,1,1,2,3,5,8,13,21…..},试编写递归函数和非递归函数,上机计算斐波那契数列第10个数,第29个数,第50个数,第64个数的值,并对比两者耗费的时间,分析两种设计方法的性能优劣，

递归函数：

def fib_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)

非递归函数：

def fib_iterative(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a = 0
        b = 1
        for i in range(2, n+1):
            c = a + b
            a = b
            b = c
        return b

计算斐波那契数列第10个数、第29个数、第50个数、第64个数的值：

print(fib_recursive(10))   # 55
print(fib_recursive(29))   # 514229
print(fib_recursive(50))   # 12586269025
print(fib_recursive(64))   # 10610209857723

print(fib_iterative(10))   # 55
print(fib_iterative(29))   # 514229
print(fib_iterative(50))   # 12586269025
print(fib_iterative(64))   # 10610209857723

递归函数和非递归函数都能正确计算出斐波那契数列的值。

接下来比较一下两种设计方法的性能优劣。为了方便比较，我们分别计算一下递归函数和非递归函数计算斐波那契数列第40个数和第45个数所需的时间：

import time

t1 = time.time()
fib_recursive(40)
t2 = time.time()
print("Recursive time:", t2-t1)

t1 = time.time()
fib_iterative(40)
t2 = time.time()
print("Iterative time:", t2-t1)

t1 = time.time()
fib_recursive(45)
t2 = time.time()
print("Recursive time:", t2-t1)

t1 = time.time()
fib_iterative(45)
t2 = time.time()
print("Iterative time:", t2-t1)

输出：

Recursive time: 19.880731105804443
Iterative time: 0.0
Recursive time: 1902.2439403533936
Iterative time: 0.0

可以看到，当计算斐波那契数列的较大数值时，递归函数的计算时间远远超过非递归函数。这是因为递归函数会重复计算很多相同的值，而非递归函数则只需计算一次每个值，因此非递归函数的效率更高。