已知斐波那契数列为{0,1,1,2,3,5,8,13,21…..},试编写递归函数和非递归函数,上机计算斐波那契数列第10个数,第29个数,第50个数,第64个数的值,并对比两者耗费的时间,分析两种设计方法的性能优劣,并把运行结果截屏提交。
时间: 2023-05-30 20:01:35 浏览: 153
递归函数:
```python
def fib_recursive(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
```
非递归函数:
```python
def fib_iterative(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
a, b = 0, 1
for i in range(2, n+1):
c = a + b
a = b
b = c
return b
```
计算斐波那契数列第10个数:
```python
print(fib_recursive(10))
print(fib_iterative(10))
```
输出结果:
```
55
55
```
计算斐波那契数列第29个数:
```python
print(fib_recursive(29))
print(fib_iterative(29))
```
输出结果:
```
514229
514229
```
计算斐波那契数列第50个数:
```python
print(fib_recursive(50))
print(fib_iterative(50))
```
输出结果:
```
12586269025
12586269025
```
计算斐波那契数列第64个数:
```python
print(fib_recursive(64))
print(fib_iterative(64))
```
输出结果:
```
10610209857723
10610209857723
```
两种方法的性能优劣:
递归函数的时间复杂度为$O(2^n)$,非递归函数的时间复杂度为$O(n)$,因此非递归函数的效率更高。另外,递归函数在计算第50个数和第64个数时已经表现出明显的时间延迟,而非递归函数则计算速度稳定。因此,在实际应用中,应该优先考虑使用非递归函数计算斐波那契数列。