Galaxy's World 银河雪尘

Tail Recursion

Galaxy前日在推上看到有人发啥御用 C++ 构建之编译规范,跑去看,瞅见评论那有人提“尾递归”,额,应该是推特的评论吧?刚才去看有没了,毕竟过去快一周了,可能记混了。

总之,后来Galaxy搜了下“尾递归”,搜到这个可以看的。
以上。

https://gist.github.com/jasonlvhit/841e3ffb4431a2ff18c2

这两天过了遍Lua,Lua的一个语言特性是支持尾递归,这是我接触的第一个支持尾递归的语言(尾递归优化)

什么是尾递归

尾递归,是尾调用的一种类型,后者更加准确,因为实际的正确尾递归(Proper Tail Recursion)是不涉及递归的。尾调用是指一个函数里的最后一个动作是一个函数调用的情形:即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归,是递归的一种特殊情形。尾调用不一定是递归调用,但是尾递归特别有用,也比较容易实现。

我们直接的来看一下Lua中尾调用:

function f(x)
    return g(x)
end

上述例子中,函数 f 调用函数 g 之后,不会执行任何多余的操作,在这种情况下,当被调用的函数 g 运行结束时不需要返回到调用者函数 f。因此,执行尾调用时不需要在栈中保留有关调用者的任何信息。 某些语言的实现,比如 Lua 解释器,充分利用了这种特性,在处理尾调用时不使用额外的栈空间,通常 我们称这种语言的实现支持了正确的尾调用。也正由于尾调用的栈空间不会成线性增长,所以我们可以用尾调用实现无穷递归和嵌套函数。

同样需要注意的是,尾递归,尾调用的条件也是非常苛刻的,函数 f 调用函数 g 之后,不会执行任何多余的操作,这一点很重要,例如下面的这些表达式,均不是尾调用:

return (g(x))
return g(x) + 1
return x or g(x)

Python,尾递归

如果你熟悉Python,你可能会碰到过一个maximum recursion depth exceeded的错误,无论你有没有遇到过,让我们执行下下面的函数:

>>> def f():
...  return f()
...
>>> f()
...
...
Runtime Error: maximum recursion depth exceeded

按照定义,上面定义的函数f,是一个标准的尾递归,如果Python能够正确的解释尾递归的话,这不会引起堆栈溢出,但是不幸的是,它真的溢出了。

让我们修改上面的函数,来观察一下函数执行中的堆栈状态:

import sys

def f():
  print(sys._current_frames())
  return f()

函数_current_frames会打印出当前的栈帧地址,如果我们执行上面的函数f,会得到类似下面的结果:

{6984: <frame object at 0x00000000029CABE0>}
{6984: <frame object at 0x00000000029CAA38>}
{6984: <frame object at 0x00000000029CA890>}
{6984: <frame object at 0x00000000029CA6E8>}
{6984: <frame object at 0x00000000029CA540>}
{6984: <frame object at 0x00000000029CA398>}

观察最后的栈帧地址,会发现,栈帧不断的上升,也就是说Python的解释器并没有实现标准意义上的尾递归。

同样,Java也不支持。

我们也可以用lua实现同样的函数:

> function f(x)
>>  return f(x)
>> end
>f(3)
...

这个函数会运行到。。。。海枯石烂。。

C,编译器的尾递归优化

对很多C中的递归函数,函数调用中的返回地址、函数参数、寄存器值的压栈是没有必要的,例如阶乘:

int factorial(int n)
{
    return n == 0 ? 1 : n * factorial(n - 1);
}

现在的C编译器大多会对这样的函数进行尾递归优化,例如在gcc中,我们执行O2优化:

$ gcc fact.c -O2 fact

编译器会把原来的函数调用call指令,优化为jump,也就是类似于循环,而不是执行函数调用。

考虑Wiki中给出的例子:

function foo(data1, data2)
   a(data1)
   return b(data2)

其中 data1、data2 是参数。编译器会把这个代码翻译成以下汇编:

foo:
  mov  reg,[sp+data1] ; 透过栈指针(sp)取得 data1 并放到暂用暂存器。
  push reg            ; 将 data1 放到栈上以便 a 使用。
  call a              ; a 使用 data1。
  pop                 ; 把 data1 從栈上拿掉。
  mov  reg,[sp+data2] ; 透过栈指針(sp)取得 data2 並放到暂用暂存器。 
  push reg            ; 将 data2 放到栈上以便 b 使用。 
  call b              ; b 使用 data2。
  pop                 ; 把 data2 從栈上拿掉。
  ret

尾部调用优化会将代码变成:

foo:
  mov  reg,[sp+data1] ; 透过栈指针(sp)取得 data1 并放到暂用暂存器。
  push reg            ; 将 data1 放到栈上以便 a 使用。
  call a              ; a 使用 data1。
  pop                 ; 把 data1 從栈上拿掉。
  mov  reg,[sp+data2] ; 透过栈指針(sp)取得 data2 並放到暂用暂存器。  
  mov  [sp+data1],reg ; 把 data2 放到 b 预期的位置。
  jmp  b              ; b 使用 data2 並返回到调用 foo 的函数。

参考

No comments

You today

Comments are closed