Tail Recursion Optimization
Table of Contents
1. 尾递归简介
最近解决了生产系统中一个 Common Lisp 程序占用了过多内存，从而导致程序 Crash 的问题。调试后发现问题根源在于有一个函数递归地调用自己，且调用的深度非常大，导致内存不够用。解决办法很简单，就是改造函数使其变为尾递归，Common Lisp 编译器会自动对尾递归进行优化。
本文简单地介绍一下“尾递归”相关知识。
In computer science, a tail call is a subroutine call performed as the final action of a procedure.
由于尾递归的最后一条语句是递归函数本身，所有没有必要保存函数的局部变量了，这样编译器可以对尾递归进行优化：递归调用时不用增加一个新的 stack frame，直接覆盖当前的 stack frame，这样当递归层次很深时也不会有栈溢出的风险了。
2. 非尾递归修改为尾递归
把一般的递归函数修改为尾递归的思路很简单： 通过增加参数来传递中间状态信息！
实例 1：求阶乘
// 求阶乘，递归实现（不是尾递归）
long factorial(long n) {
return (n <= 1) ? 1 : n * factorial(n - 1);
}
可以改造为下面尾递归形式：
// 求阶乘，递归实现（尾递归）
long factorial_helper (long n, long a) {
return (n == 1) ? a : factorial_helper (n - 1, a * n);
}
long factorial (long n) {
return (n == 0) ? 1 : factorial_helper (n, 1);
}
实例 2：求单链表长度（可以用迭代实现，没有必要用递归实现，这里仅是拿它做例子）
// 求单链表长度，递归实现（不是尾递归）
int get_length(Node head){
if (head == null) return 0;
return get_length(head.Next) + 1;
}
可以改造为下面尾递归形式：
// 求单链表长度，递归实现（尾递归）
// 增加一个参数a用来保存中间状态信息。
int get_length_helper (Node head, int a){
if (head == null) return a;
return get_length_helper (head.Next, a + 1);
}
int get_length (Node head) {
get_length_helper (head, 0); //a传个初值0
}
3. 各种编译器对尾递归优化的支持
3.1. Scheme（语言规范要求支持）
Scheme 的语言规范要求编译器支持尾递归优化。
3.2. Common Lisp（支持）
Common Lisp 实现一般也支持尾递归优化。
Lispworks 5.1 的尾递归优化测试：
.> (defun fun3 () (+ 1 2) (fun3) )
FUN3
.> (disassemble 'fun3)
4010002434:
0: 4883F900 cmpq rcx, 0
4: 750C jne L1
6: 4C8B4BD4 moveq r9, [rbx-2C] ; FUN3
10: 498B590F moveq rbx, [r9+F]
14: 31C9 xor ecx, ecx
16: FFE3 jmp rbx
L1: 18: 41FFA6E7020000 jmp [r14+2E7] ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
25: 0000 addb [rax], al
NIL
.> (defun fun4 () (fun4) (+ 1 2) )
FUN4
.> (disassemble 'fun4)
40100024B4:
0: 4883F900 cmpq rcx, 0
4: 752C jne L1
6: 49396667 cmpq [r14+67], rsp
10: 7726 ja L1
12: 4157 push r15
14: 55 push rbp
15: 4889E5 moveq rbp, rsp
18: 4989DF moveq r15, rbx
21: 4D8B4FD4 moveq r9, [r15-2C] ; FUN4
25: 498B590F moveq rbx, [r9+F]
29: 31C9 xor ecx, ecx
31: FFD3 call rbx
33: BF18000000 move edi, 18
38: B901000000 move ecx, 1
43: 4889EC moveq rsp, rbp
46: 5D pop rbp
47: 415F pop r15
49: C3 ret
L1: 50: 41FFA6E7020000 jmp [r14+2E7] ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
57: 0000 addb [rax], al
NIL
fun3 是尾递归，fun4 只是普通递归，不是尾递归。
可以看到 fun3 的汇编代码中没有 call 指令（编译器优化成了 jmp 指令），而 fun4 的汇编代码中有 call 指令。
注：call 指令在实现转移之前, 要将返回地址存入堆栈的, 以便子程可以通过 ret 指令返回到 call 指令下面的指令接着运行；而 jmp 指令就没用这些事儿，直接跳转到目标地址。
3.3. C（支持）
Gcc 支持尾递归优化。
-foptimize-sibling-calls
optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
参考：
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/CUJ/2004/0402/0402bauer/0402bauer.htm
gcc 比较强大，不仅支持尾递归优化，也支持 Sibling calls 的优化。
前面例子中求单链表长度的普通递归函数，不是尾递归，gcc 在-O2 级别的优化下也可以对其进行优化！
3.4. C#（目前没有支持）
C# compiler does not give you any guarantees about tail-call optimizations because C# programs usually use loops and so they do not rely on the tail-call optimizations.
参考：http://stackoverflow.com/questions/15864670/generate-tail-call-opcode
3.5. Python（目前没有支持）
Python - Does not require tail call elimination. Language inventor Guido van Rossum contends that stack traces are altered by tail call elimination making debugging harder, and prefers that programmers use explicit iteration instead.
参考：http://neopythonic.blogspot.jp/2009/04/tail-recursion-elimination.html