Python基础知识举例:以斐波那契数列为例
时间: 2024-09-06 12:03:20 浏览: 20
斐波那契数列是一个著名的数列,它的每一项都是前两项的和,通常以0和1开始。斐波那契数列的前几项是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
在Python中,斐波那契数列可以通过多种方式实现,以下是一些基础知识例子:
1. 递归方式:
```python
def fibonacci_recursive(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
```
这种方式非常直观,但效率较低,因为它包含大量的重复计算。
2. 迭代方式:
```python
def fibonacci_iterative(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
```
这种方式更加高效,因为它避免了重复计算,时间复杂度为O(n)。
3. 列表存储方式:
```python
def fibonacci_list(n):
fib_list = [0, 1]
for i in range(2, n+1):
fib_list.append(fib_list[-1] + fib_list[-2])
return fib_list[:n]
```
这种方式会存储整个数列,空间复杂度为O(n)。
4. 动态规划(记忆化递归):
```python
def fibonacci_memoization(n, memo={}):
if n <= 0:
return 0
elif n == 1:
return 1
elif n not in memo:
memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
return memo[n]
```
这种方式结合了递归和迭代的优点,通过记忆化减少了重复计算,提高了效率。