- 斐波那契数列：Fn=Fn-1+Fn-2
- 使用递归的算法，代码如下：
def fibnacci(n):
if n==1 or n==2:
return 1
else:
return fibnacci(n-1)+fibnacci(n-2)
if __name__=="__main__":
print(fibnacci(10))
执行结果如下：
55
- 使用非递归算法实现，代码如下：
def fibnacci_no_recurision(n):
rs=[0,1,1]
for i in range(n-2):
num=rs[-1]+rs[-2]
rs.append(num)
return rs
if __name__=="__main__":
print(fibnacci_no_recurision(10))
执行结果如下：
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
-
上述两种算法，当n比较大时，使用递归算法的方式会很慢，因为上述递归算法存在一个问题就是存在大量的重复计算
-
非递归的算法就可以理解为动态规划算法
-
动态规划的核心思想就是递归式+重复子问题
即通过分析得出一种递归的关系，然后在这个递归的关系中存在许许多多的子问题，通过将这些子问题的状态或结果存起来，这样就可以避免想递归中的那些反复的重复计算，这就是动态规划
