fibonacci by recursion

你可以用递归的方式来实现这个数列。以下是一个用 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(fibonacci(i))

解释：
• fibonacci(0) 返回 0。
• fibonacci(1) 返回 1。
• 对于 n >= 2，fibonacci(n) 会递归调用 fibonacci(n-1) 和 fibonacci(n-2)，然后将它们的结果相加。
注意： 虽然递归实现非常直观，但对于较大的 n 值，这种实现方式效率非常低，因为它会重复计算很多子问题。例如，计算 fibonacci(5) 时会重复计算 fibonacci(3) 和 fibonacci(2) 等。 为了提高效率，可以使用记忆化（Memoization）技术，或者使用动态规划（Dynamic Programming）来避免重复计算。

记忆化版本

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
        return memo[n]

# 测试
for i in range(10):
    print(fibonacci(i))

动态规划版本

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    fib = [0] * (n + 1)
    fib[0] = 0
    fib[1] = 1

    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]

    return fib[n]

# 测试
for i in range(10):
    print(fibonacci(i))