斐波那契数的递归和迭代算法

斐波那契数列是指：0、1、1、2、3、5、8、13、21、34、……，即第一项为0，第二项为1，后面每一项都是前两项的和。

递归算法：

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

这个递归算法的思路是：当n为0或1时，直接返回n；否则，返回前两项的和，前两项的值通过递归调用求得。

但是递归算法的效率很低，因为它会重复计算已经计算过的项，时间复杂度为O(2^n)，所以在计算大量的斐波那契数列时，递归算法的效率不高。

迭代算法：

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

这个迭代算法的思路是：初始化前两项a和b为0和1，然后从第三项开始迭代计算每一项，每次计算都是前两项的和，最后返回第n项的值。这个算法不会重复计算已经计算过的项，时间复杂度为O(n)，所以效率比递归算法高很多。