The Fibonacci sequence is a classic mathematical sequence that is widely used in computer science and algorithm design; this article will introduce four methods of implementing the Fibonacci sequence using the Python programming language.

## 1. Recursive method

The recursive algorithm is the simplest way to implement the Fibonacci sequence. The code is as follows:

```
import time
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
n = 40
start = time.time()
value = fibonacci_recursive(n)
print(f"第 {n} 项为 {value}\n耗时: {time.time() - start}")
```

Program running results

第 40 项为 102334155 耗时: 26.679578065872192

Although the recursive algorithm is simple and easy to understand, its time complexity is relatively high `O(2`

, which is suitable for understanding the basic structure of the Fibonacci sequence. ^{n})

## 2. Iterative method

The iterative method is more efficient and suitable for calculating the Fibonacci sequence in a larger range. The code is as follows:

```
import time
def fibonacci_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
n = 40
start = time.time()
value = fibonacci_iterative(n)
print(f"第 {n} 项为 {value}\n耗时: {time.time() - start}")
```

Program running results

第 40 项为 102334155 耗时: 0.0

This method is implemented through a loop, with a time complexity of `O(n)`

, which is more efficient than the recursive method.

## 3. Dynamic programming method

The dynamic programming method improves efficiency by storing the results of sub-problems, which is very suitable for calculating very large Fibonacci series. The code is as follows:

```
import time
def fibonacci_dynamic(n):
fib = [0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
n = 40
start = time.time()
value = fibonacci_dynamic(n)
print(f"第 {n} 项为 {value}\n耗时: {time.time() - start}")
```

Program running results

第 40 项为 102334155 耗时: 0.0

This method also has a time complexity of `O(n)`

, but a space complexity of `O(n)`

, making it suitable for scenarios that require fast calculation results.

## 4. Use the general formula

The general formula for the Fibonacci sequence is:

Use Python to implement as follows:

```
import time
import math
def fibonacci_form(n):
sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
psi = (1 - sqrt5) / 2
return int((phi**n - psi**n) / sqrt5 + 0.5)
n = 40
start = time.time()
value = fibonacci_form(n)
print(f"第 {n} 项为 {value}\n耗时: {time.time() - start}")
```

The time complexity using the general formula is `O(1)`

.