一、函数执行流程
http://pythontutor.com/visualize.html#mode=edit
示例.png
- 全局帧中生成
foo1、foo2、foo3、main函数对象 main函数调用main中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶main中全局查找函数foo1压栈，将常量 100、101 压栈，调用函数foo1，创建栈帧。print函数压栈，字符串和变量b、b1压栈，调用函数，弹出栈顶，返回值main中全局查找函数foo2压栈，将常量 200 压栈，调用函数foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3，创建栈帧。foo3完成print函数调用后返回。foo2恢复调用，执行print后，返回值。main中foo2调用结束弹出栈顶。main继续执行print函数调用，弹出栈顶。main函数返回
示例.png
示例.png
二、递归 Recursion
- 函数直接或见着调用自身就是 递归
- 递归需要有边界条件、递归前进段、递归返回段
- 递归一定要有 边界条件
- 当边界条件不满足的时候，递归前进
- 当边界条件满足的时候，递归返回
示例.png
2.1 斐波那契数列 Fibonacci number：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....
- 若
F(n)为该数列第 n 项（n∈N*），那么这句话可写成：F(n)=F(n-1)+F(n-2) F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
a = 0 b = 1 n = 10 # 55 # 循环实现 for i in range(n -1): a, b = b, a + b else: print(b) # 递归实现 def fib(n): return 1 if n < 3 else fib(n-1) + fib(n-2)
fib(5)解析fib(4) + fib(3)fib(4)调用fib(3)、fib(2)fib(3)调用fib(2)、fib(1)fib(2)、fib(1)是边界return 1，所有函数调用逐层返回
2.2 递归要求
- 递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用
- 递归调用的深度不宜过深
- Python 对递归调用的深度做了限制，以保护解释器
- 超过递归深度限制，抛出
RecursionError: maxinum recursion depth exceeded超出最大深度 sys.getrecursionlimit()
2.3 递归性能 fib(35) 比较
- for 循环
示例.png - 递归
示例.png
2.4 递归的性能
- 循环稍微复杂一些，但是只要不是死循环，可多次迭代直至算出结果
fib函数代码极简易懂，但是只能获取到最外层函数调用，内部递归结果都是中间结果。而且给定一个n都要进行近2n次递归，深度越深，效率越低。为了获取斐波那契数列需要外面再套一个n次循环，效率就更低了- 递归还有深度限制，若递归复杂，函数反复压栈，栈内存很快就溢出了
- 斐波那契数列改进
def fib(n, a=0, b=1): a, b = b, a+b if n == 1: return a return fib(n-1, a, b) print(fib(4))
- 改进后的函数和循环的思想类似
- 参数
n是边界条件，用n来计数 - 上次的计算结果直接作为函数的实参
- 效率高
- 和循环比较，性能相近。所以并不是说递归一定效率低下，但递归有深度限制
2.5 间接递归
def foo1(): foo2() def foo2(): foo1() foo1()
间接递归，是通过别的函数调用了函数自身
拖构成了循环递归调用是非常危险的，但往往这种情况在代码复杂情况下，很可能发生这种调用，要用代码的规范来避免递归调用的发生
三、递归总结
- 递归是一种很自然的表达，符合逻辑思维
- 递归相对运行效率低，每一次调用函数都要开辟栈帧
- 递归有深度限制，若递归层次太深，函数反复压栈，栈内存很快就溢出了
- 若是有限次数的递归，可使用递归调用，或使用循环代替，循环代码稍复杂一些，但只要不是死循环，可多次迭代直至算出结果
- 绝大多数递归，都可使用循环实现
- 即使递归代码很简洁，但 能不用则不用 递归
四、递归练习
4.1 求 n 的阶乘
- 按公式
def fac(n): if n == 1: return 1 return n * fac(n-1) def fac(n): return 1 if n < 2 else n * fac(n-1)
- 按循环
n = 6 fac = 1 for i in range(n, 0, -1): # 计数器 n 次 fac = fac * i print(fac) def fac1(n, fac=1): fac = fac * n if n == 1: return fac return fac1(n-1, fac)
4.2 将一个数逆序放入列表中，例如 1234 => [4, 3, 2, 1]
- 传入字符串
target = [] def revert(data): target.append(data[-1]) if len(data) == 1: return target return revert(data[:-1]) revert('1234') def revert(data, target=None): if target is None: target = list() target.append(data[-1]) if len(data) == 1: return target return revert(data[:-1], target) revert('1234') def revert(data): if data == '': return [] return [data[-1]] + revert(data[:-1]) revert('1234')
- 传入数字
def revert(data, target=None): if target is None: target = list() if not isinstance(target, list): return x, y = divmod(data, 10) target.append(y) if x: return revert(x, target) return target revert(120340)
4.3 解决猴子吃桃问题
- 按题意
def peach(days=1): if days == 10: return 1 return 2 * (peach(days+1) +1) def peach(days=10): if days == 1: return 1 return 2 * (peach(days-1) + 1)
- 按循环
peach = 1 for i in range(9): peach = 2 * (peach + 1) print(peach) def fn(days=9, peach=1): peach = 2 * (peach + 1) if days == 1: return peach return fn(days-1, peach) fn()
