_posts/2016-01-11-tail-recursion.md

   1 ---
   2 layout: post
   3 date: 'Mon 2016-01-11 12:58:56 +0800'
   4 slug: "tail-recursion"
   5 title: "Tail Recursion"
   6 description: ""
   7 category:
   8 tags: [ZT]
   9 ---
  10 {% include JB/setup %}
  11
  12 Galaxy前日在推上看到有人发啥[御用 C++ 构建之编译规范](http://tech.acgtyrant.com/%E5%BE%A1%E7%94%A8-C-%E6%9E%84%E5%BB%BA%E4%B9%8B%E7%BC%96%E8%AF%91%E8%A7%84%E8%8C%83/)，跑去看，瞅见评论那有人提“尾递归”，额，应该是推特的评论吧？刚才去看有没了，毕竟过去快一周了，可能记混了。
  13
  14 总之，后来Galaxy搜了下“尾递归”，搜到这个可以看的。
  15 以上。
  16
  17 https://gist.github.com/jasonlvhit/841e3ffb4431a2ff18c2
  18
  19 这两天过了遍Lua，Lua的一个语言特性是支持尾递归，这是我接触的第一个支持尾递归的语言（尾递归优化）
  20
  21 ### 什么是尾递归
  22
  23 尾递归，是尾调用的一种类型，后者更加准确，因为实际的正确尾递归（Proper Tail Recursion）是不涉及递归的。尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置为尾位置。若这个函数在尾位置调用本身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归，是递归的一种特殊情形。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。
  24
  25 我们直接的来看一下Lua中尾调用：
  26
  27 ``` lua
  28 function f(x)
  29     return g(x)
  30 end
  31 ```
  32
  33 上述例子中，函数 f 调用函数 g 之后，不会执行任何多余的操作，在这种情况下，当被调用的函数
  34 g 运行结束时不需要返回到调用者函数 f。因此，执行尾调用时不需要在栈中保留有关调用者的任何信息。
  35 某些语言的实现，比如 Lua 解释器，充分利用了这种特性，在处理尾调用时不使用额外的栈空间，通常
  36 我们称这种语言的实现支持了正确的尾调用。也正由于尾调用的栈空间不会成线性增长，所以我们可以用尾调用实现无穷递归和嵌套函数。
  37
  38 同样需要注意的是，尾递归，尾调用的条件也是非常苛刻的，**函数 f 调用函数 g 之后，不会执行任何多余的操作**，这一点很重要，例如下面的这些表达式，均不是尾调用：
  39
  40 ``` lua
  41 return (g(x))
  42 return g(x) + 1
  43 return x or g(x)
  44 ```
  45
  46 ### Python，尾递归
  47
  48 如果你熟悉Python，你可能会碰到过一个maximum recursion depth exceeded的错误，无论你有没有遇到过，让我们执行下下面的函数：
  49
  50 ``` python
  51 >>> def f():
  52 ...  return f()
  53 ...
  54 >>> f()
  55 ...
  56 ...
  57 Runtime Error: maximum recursion depth exceeded
  58
  59 ```
  60 按照定义，上面定义的函数f，是一个标准的尾递归，如果Python能够正确的解释尾递归的话，这不会引起堆栈溢出，但是不幸的是，它真的溢出了。
  61
  62 让我们修改上面的函数，来观察一下函数执行中的堆栈状态：
  63
  64 ``` python
  65 import sys
  66
  67 def f():
  68   print(sys._current_frames())
  69   return f()
  70 ```
  71
  72 函数```_current_frames```会打印出当前的栈帧地址，如果我们执行上面的函数f，会得到类似下面的结果：
  73 ```
  74 {6984: <frame object at 0x00000000029CABE0>}
  75 {6984: <frame object at 0x00000000029CAA38>}
  76 {6984: <frame object at 0x00000000029CA890>}
  77 {6984: <frame object at 0x00000000029CA6E8>}
  78 {6984: <frame object at 0x00000000029CA540>}
  79 {6984: <frame object at 0x00000000029CA398>}
  80 ```
  81 观察最后的栈帧地址，会发现，栈帧不断的上升，也就是说Python的解释器并没有实现标准意义上的尾递归。
  82
  83 同样，**Java**也不支持。
  84
  85 我们也可以用lua实现同样的函数：
  86
  87 ``` lua
  88 > function f(x)
  89 >>  return f(x)
  90 >> end
  91 >f(3)
  92 ...
  93 ```
  94
  95 这个函数会运行到。。。。海枯石烂。。
  96
  97 ### C，编译器的尾递归优化
  98
  99 对很多C中的递归函数，函数调用中的返回地址、函数参数、寄存器值的压栈是没有必要的，例如阶乘：
 100 ``` c
 101 int factorial(int n)
 102 {
 103     return n == 0 ? 1 : n * factorial(n - 1);
 104 }
 105 ```
 106 现在的C编译器大多会对这样的函数进行尾递归优化，例如在gcc中，我们执行O2优化：
 107 ``` batch
 108 $ gcc fact.c -O2 fact
 109 ```
 110 编译器会把原来的函数调用```call```指令，优化为```jump```，也就是类似于循环，而不是执行函数调用。
 111
 112 考虑Wiki中给出的例子：
 113
 114 ```
 115 function foo(data1, data2)
 116    a(data1)
 117    return b(data2)
 118 ```
 119 其中 data1、data2 是参数。编译器会把这个代码翻译成以下汇编：
 120 ```
 121 foo:
 122   mov  reg,[sp+data1] ; 透过栈指针（sp）取得 data1 并放到暂用暂存器。
 123   push reg            ; 将 data1 放到栈上以便 a 使用。
 124   call a              ; a 使用 data1。
 125   pop                 ; 把 data1 從栈上拿掉。
 126   mov  reg,[sp+data2] ; 透过栈指針（sp）取得 data2 並放到暂用暂存器。
 127   push reg            ; 将 data2 放到栈上以便 b 使用。
 128   call b              ; b 使用 data2。
 129   pop                 ; 把 data2 從栈上拿掉。
 130   ret
 131 ```
 132 尾部调用优化会将代码变成：
 133 ```
 134 foo:
 135   mov  reg,[sp+data1] ; 透过栈指针（sp）取得 data1 并放到暂用暂存器。
 136   push reg            ; 将 data1 放到栈上以便 a 使用。
 137   call a              ; a 使用 data1。
 138   pop                 ; 把 data1 從栈上拿掉。
 139   mov  reg,[sp+data2] ; 透过栈指針（sp）取得 data2 並放到暂用暂存器。
 140   mov  [sp+data1],reg ; 把 data2 放到 b 预期的位置。
 141   jmp  b              ; b 使用 data2 並返回到调用 foo 的函数。
 142 ```
 143
 144 ### 参考
 145
 146 * [What is the tail recursion? -- Stack Overflow](http://stackoverflow.com/questions/33923/what-is-tail-recursion)
 147 * [Programming in Lua](http://www.lua.org/pil/)
 148 * [尾调用 -- Wiki](http://zh.wikipedia.org/zh/%E5%B0%BE%E8%B0%83%E7%94%A8)
 149 * [什么是尾递归 -- 知乎](http://www.zhihu.com/question/20761771)
 150 * [CSAPP第5章有关于程序优化的更详细内容](http://book.douban.com/subject/1230413/)