递归与循环
对计算机感兴趣的同学递归这个概念肯定不陌生,看过《计算机的程序构造与解释》(SICP)这本书的同学对其中的各种用递归实现循环的例子应该是印象深刻,但是我们大部分是学着C语言课程入门了,一般来说,递归在我们眼中是低效的,遇到递归总是要想办法转换成循环迭代的。
递归之所以低效,很大一部分原因是因为这个过程会产生大量的函数调用,消耗相当大的栈空间,并且每次调用都需要把参数压入栈中,调用完成后还需要读取结果,相比之下循环的方式就要“环保”多了,除此之外,一些语言还限制了程序的最大递归调用深度,这就意味写用递归写的算法在一些语言上面已经不是性能的问题了,而是根本就无法运行。
我们先看一个例子
001: def repeat(n):
002: if n > 0:
003: # do something
004: return repeat(n-1)
我们尝试调用一下这个python函数repeat(1000)
很不幸,python解释器告诉我们
RuntimeError: maximum recursion depth exceeded
尾调用
递归在解决算法问题上的高效让人难以放弃,有些人选择了曲线救国,先写好递归版本再改成循环版本;另一些人则在思考,我们能不能通过优化编译器或者解释器来减少栈空间的使用呢,
通过观察我们发现,在第4行中,当前的repeat调用帧已经结束了,实际上返回的是下一个repeat函数的调用结果,具体的调用帧如下图左所示,这个时候完全可以复用帧frame1以及它的临时变量堆栈,而且这个过程可以推广到所有的尾调用(tail call),而不是仅仅是递归(当然,也不是所有的递归都能优化成尾调用),维基百科上的尾调用定义如下
在计算机科学里,尾调用是指一个函数里的最后一个动作是一个函数调用的情形:即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归,是递归的一种特殊情形。
我们来看一个通用的尾调用例子
def foo1():
return foo2()
def foo2(a,b,c):
d = a+b+c
return d
消除尾调用
通过观察,我们发现foo1方法在调用foo2方法的时候,它本身的栈空间已经不用了,这种情况可以循环利用起来,直接把foo1的栈空间给foo2使用,如下图所示。
用伪代码来表示递归调用的过程是
# 解释器可以简化成下面这个模型
# 对于尾调用,我们可以通过编译器分析出来,生成一个OP_TAILCALL的字节码,那么处理将会是
def execute_function(func, ctx):
locals = create_locals()
frame_init:
reset_locals(locals)
reset_regs(func, ctx) # 设置pc等寄存器
set_args(func, ctx) # 设置调用参数
op = get_op(ctx)
switch (op):
case "OP_CALL": # 普通调用过程
new_func = get_func(ctx)
return execute_function(new_func, ctx)
case "OP_TAILCALL": # 尾调用过程
func = get_func(ctx)
goto frame_init # 跳转回frame初始化过程重复利用frame
...
参考资料
- https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
- https://github.com/xupingmao/minipy