斐波那契数列是一个非常经典的数列，定义如下：

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2) (N>=2)

下面介绍三种常见的实现方式：

1. 递归实现

递归实现简单直观，代码如下：

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

但是递归实现有一个致命问题，就是当n较大时会发生栈溢出，效率比较低。

2. 递推实现

通过递推方式，避免了递归带来的空间和时间上的浪费，代码如下：

def Fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

3. 优化的递推实现

通过观察递归公式，会发现每次只使用了前两个数，因此不必使用一个整体数组进行存储，只需在计算时不断地更新前面两个数即可，这样就可以空间复杂度为O(1)，代码如下：

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

这种方法不需要使用额外的空间，是最优秀的解决方案。