Tail Recursion
11 Jan 2016Galaxy前日在推上看到有人发啥御用 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
Comments are closed