什么是递归算法？
-- 函数自己调用自己本身
-- 本质上return返回的时候，总是把一个参数传入到自己函数本身，让函数反复调用下去
递归有何特点？
-- 必有一个结束条件
没有结束条件，递归就没有任何意义，python中默认只能999层递归
递归过多栈溢出，报错
-- 效率不高
相对而言，对于正向递归，递归次数和循环次数一致，没有区别
对于逆向递归，要递归到最后才能得到确定的值，然后从最底层返回
一次是递归到结束值，一次从结束值返回到初始值
--
如何正向递归实现斐波那契数列？
#!/usr/bin/python3 __author__ = 'beimenchuixue'
__blog__ = 'http://www.cnblogs.com/2bjiujiu/' list_fab = [1, 1] # 定义接收值的列表 def fab(u, n_1, n_2): # u表示获取几个fab值
n_3 = n_1 + n_2 # n_3 每次都等于前面两个数之和
print(n_1, n_2, n_3) # 打印每次递归这3个值
list_fab.append(n_3) # 把每次递归得到的n_3值添加列表中
if u == 1: # 设置结束条件，把列表返回回去,本质上也是递归深度
return n_3 # 返回最后一个值
return fab(u-1, n_2, n_3) # 本质上还是实现了往后移一位，递归深度为u if __name__ == '__main__':
result = fab(10, 1, 1) # 传入初始值
print(result) # 本质上就包含初始值1,1 ，list_fab中有u+2个值，但是添加进去只有u个值
print(list_fab) # 打印结果
如何逆向递归实现斐波那契数列？
#!/usr/bin/python3 __author__ = 'beimenchuixue'
__blog__ = 'http://www.cnblogs.com/2bjiujiu/' list_fab = [] # 定义接收值的列表 def fab(n_3, n_2):
n_1 = n_3 - n_2 # n_1 每次都等于 n_3 - n_2
print(n_1, n_2, n_3) # 打印每次递归这3个值
list_fab.insert(0, n_1) # 把每次递归得到的n_1值添加列表中最前面
if n_1 == 1: # 设置递归结束返回条件
return 1 # 返回最后一个值
return fab(n_2, n_1) # 本质上实现了 n_2 = n_3 , n_1 = n_2,逆向移动了一位 if __name__ == '__main__':
result = fab(144, 89) # 传入初始值
print(result) # 打印递归最后返回的参数
print(list_fab)