递归有关的几个小问题
引子
在加密系列里突然出这么一个问题，确实有点怪。我犹豫了一下，还是先写了再说。
这个问题的提起，是公司老大kay提出一个问题。在反转链表的时候，如果有环怎么办。然后我们就现场写各种解环算法。这个问题本身不难，我们先看一下原始问题和解，还有带环反转。
Scheme反转链表
想了想，还是先写Scheme版本。这个版本实现简单概念清晰，个人觉得非常典型。而且对后面理解Python版本很有帮助。如果看不懂的话，可以直接去看Python版本。Python版本看不懂了再回本章来，去看Scheme入门教材。
Scheme的正解版本只有一个，就是带复制TCO版本。
(define (reverse-tco ll rslt)
(if (eq? ll '())
rslt
(reverse-tco (cdr ll) (cons (car ll) rslt))))
这个版本体现了Scheme的几个特点。
- 递归比迭代好使。
- 强制要求TCO。
- cons操作起来非常方便。
Python递归反转链表
def reverse_tco(ll, rslt):
if not ll:
return rslt
return reverse_tco(ll[1], [ll[0], rslt])
这是链表最简单的问题，也是递归论最基本的问题。注意这里采用list来模拟了lisp中的cons，不用tuple主要是后面还有环，需要修改数据。如果你不明白，可以先看Scheme版本的代码。
递归转迭代
写到这个水平，其实有一半的被面人就挂了(好水)。但是这个水平其实也就是入门水平。最低限度，也要知道上面这个递归是可转写为迭代的。更进一步的，要知道这个递归是个尾递归。下面我们把这个代码转写为迭代形态。
def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll = [ll[0], rslt], ll[1]
return rslt
或者非生成节点版本。
def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll[1], ll = ll, rslt, ll[1]
return rslt
这里的区别，其实是SICP第24页所说的“递归计算过程”和“递归过程”的区别。具体请直接参考原书，我就不打字摘抄了。
另外，尾递归的构成条件也很简单。最后一个函数调用的结果紧接着被return给上级函数，中间没有其他操作。满足上述条件的递归，我们称为尾递归。尾递归是可以优化的。更加广义的说，所有最后一步是调用其他函数并直接返回给上级的函数，都是可优化的。具体来说，这个调用的栈帧可以被抽取掉。当然，抽取栈帧的行为将导致调试信息不正确，从而导致调试困难。
Python非TCO版本
这个问题还有个解法是非TCO的。
def reverse_recursion(ll):
if not ll[1]:
return ll
rslt = reverse_recursion(ll[1])
ll[1][1], ll[1] = ll, None
return rslt
这个版本做不到尾递归，是因为返回后还有操作。
大家可以考虑一下，这个版本能转写为迭代么？如果迭代里不使用类似栈的结构的话。(或者用list/array来模拟stack操作)
带环问题
这个问题其实很简单，把上面的测试数据换一下就行。
t = [5, None]
ll = [1, [2, [3, [4, t]]]]
t[1] = ll[1][1]
在这里，尾部的None被换为了[3, …]。如果直接使用原始解法，三个解法都会出问题。TCO和非TCO版本的会爆栈，迭代版本则是变成了12354。
Python解带环反转
这个版本要用到一点小技巧——placeholder。主旨思想是在解除node的时候，将原本的cons中的cdr替换为placeholder。这样当遍历到环尾时，就可以识别出来了。之所以placeholder不能用None，是因为这样会在无环情况下和倒数第二个cons的情况搞混。
def reverse_loop_tco(ll, rslt):
if not ll or ll[1] == PLACEHOLDER:
return rslt
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return reverse_loop_tco(ll, rslt)
转写为迭代，也不算困难。
def reverse_loop_iterate(ll):
rslt = None
while ll and ll[1] != PLACEHOLDER:
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return rslt
注意这里没有非生成节点版本。因为如果复用旧节点的话，cdr就会被指向下一跳，不能填充placeholder进去。
非TCO版本，稍微改改就行。
def reverse_loop_recursion(ll):
if not ll[1] or ll[1][1] == PLACEHOLDER:
return ll
t, ll[1] = ll[1], PLACEHOLDER
rslt = reverse_loop_recursion(t)
t[1], ll[1] = ll, None
return rslt
争议
关键是在带环的Non-TCO版本上，我和kay产生了一点分歧。我认为，这个算法的空间消耗从N变成了2N(虽然同属O(n)级别)。kay认为，最优版本的解法是不增加空间消耗的。于是我要证明这个版本算法的最优情况下，空间消耗还是会增加。关键是，我能想到的都未必是最优版本。那咋办呢？
于是我就想出了个大杀器——gcc。结果一研究，发现一个更不得了的事情。
先从gcc开始说起吧。gcc内部有很多优化算法，会将代码优化到最优。而一个算法到底是推一个数到栈上去，还是两个，这是可以一眼看出来的。如果在gcc的优化下，代码依然增加推了一个对象上去。那么我就可以比较有信心的说，空间消耗有增加。
具体成果请看最后的“附录B: 用C解链表反向问题的六种解法源码”。这里不是要说这个代码转写为C的问题(因为这没有任何难度)。问题是，这个代码编译后的情况不大对头。为此我写了个最简代码，从头开始说起。
编译/反汇编/调试/参数调用的基础知识
- 要用O2编译，这个会启动优化。O1编译以下都不带这个优化。
- 使用-g输出调试符号，方便gdb调试。
- 不要strip，会干掉符号表，导致反汇编难度增大。
- 使用objdump -d反汇编。
- 使用gdb调试。
传统函数调用时，会设定参数，然后用call指令调用目标函数。call指令会把当前地址压到栈上去，然后将rip改为目标地址。目标函数接受参数，执行，再执行ret返回。ret会将stack顶元素pop出来设定到rip上。简单来说，这就是函数调用过程。
如果加入细节。首先函数调用前，调用者需要依次push参数。顺序是按照C里面声明的顺序，左到右(pascal式)或右到左(C式)。最后调用者使用call指令。接收者首先要push rbp，因为下面要使用这个寄存器，又不能破坏原始值。随后mov rsp, rbp; sub xxx, rsp;，前者是将rbp固定在当前位置，后者则是对stack留空一定字节。因为后续rsp还可能随着进一步的调用而增减，所以需要固定rbp。
在完成这步之后，rsp就可以随意增减了。rbp-xx是rsp预留出来的空间，一般是各种函数局部变量。rbp+xx则是rbp原本值，ret地址，然后是各种参数。缓冲区溢出攻击的核心就是直接使用rbp-xx的某个byte array，写入过多数据导致覆盖到了ret地址。
至于参数，如果是pascal式，rbp+3N(N是CPU字长)应当是右边第一个参数，rbp+4N是右边第二个。而C式，rbp+3N是左边第一个，rbp+4N是左边第二个。这就引申出一个区别。C语言的调用允许你在调用时，参数表右边写入原则上无限多个参数。如果是pascal式，你上来就接收了一个不明其意的参数，而且你也不知道会传入多少个。而如果是C式，你上来会接收左边第一个参数，这个参数里可以为你指明后续有多少个参数，意义分别是什么。例如printf中的第一个参数。因此C式调用允许动态传参，pascal则基本不行。
但是C式也是有缺陷的。C式由于被调用者很难知道自己被传入了多少个参数(其实可以从首参数中解析，但是清理是编译器工作，解析参数是业务逻辑，这个做法需要函数逻辑侵入编译器工作)，因此只能用ret返回，返回后由调用者来清理栈(调用者一定知道有多少个参数)。而pascal被调用者很清楚有多少个参数，因此可以由被调用者清理。关于这个问题的更进一步资料，可以看这里。
还有一点细节技巧要讲。汇编语言的参数传递，和我当年学的时候有很大区别。我建议大家直接看wiki上的资料:calling conventions。我们这是System V AMD64 ABI，所以参数依次是RDI, RSI, RDX, RCX, R8, R9, XMM0–7。
C代码，O2优化及反汇编
我们先从不是那么复杂的非带环版本开始说起。引用附录B里的代码。
struct node* reverse_tco(struct node *n, struct node *result)
{
struct node *t;
if (n == NULL) {
return result;
}
t = n->next;
n->next = result;
return reverse_tco(t, n);
}
我们先看O1反汇编
000000000000078b <reverse_tco>:
78b: 48 89 f0 mov %rsi,%rax
78e: 48 85 ff test %rdi,%rdi
791: 74 18 je 7ab <reverse_tco+0x20>
793: 48 83 ec 08 sub $0x8,%rsp
797: 48 89 fe mov %rdi,%rsi
79a: 48 8b 7f 08 mov 0x8(%rdi),%rdi
79e: 48 89 46 08 mov %rax,0x8(%rsi)
7a2: e8 e4 ff ff ff callq 78b <reverse_tco>
7a7: 48 83 c4 08 add $0x8,%rsp
7ab: f3 c3 repz retq
可以清晰的看出，这是一个递归代码。上来78b和78e乱序执行，将rsi(result)放到rax上去准备返回，再检测rdi(n)是否为NULL。是的话跳去7ab返回，否的话rsp留出8bytes空间，将n作为result，将n->next(rdi+8)作为n准备递归。最后79e执行n->next = result;，7a2递归。
总的来说，这是个翻译的很明白的汇编代码。
下面我们查看O2编译反汇编。
0000000000000850 <reverse_tco>:
850: 48 85 ff test %rdi,%rdi
853: 74 20 je 875 <reverse_tco+0x25>
855: 48 89 f8 mov %rdi,%rax
858: eb 09 jmp 863 <reverse_tco+0x13>
85a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
860: 48 89 d0 mov %rdx,%rax
863: 48 8b 50 08 mov 0x8(%rax),%rdx
867: 48 89 70 08 mov %rsi,0x8(%rax)
86b: 48 89 c6 mov %rax,%rsi
86e: 48 85 d2 test %rdx,%rdx
871: 75 ed jne 860 <reverse_tco+0x10>
873: f3 c3 repz retq
875: 48 89 f0 mov %rsi,%rax
878: c3 retq
879: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
这段也不难懂，上来判断rdi(n)是否为0，为0把rsi(result)设定为返回值并退出。不为0把n转移到eax(返回值)上，跳去863执行。863-86e里，n在eax上，t在rdx上，result始终在rsi上。最后一个t赋给n是跳去860做的。
关键是这段汇编说明了什么？这段代码根本不调用自身，所以根本不是递归代码。有趣的是，我们可以对比它的手工转迭代形态，reverse_iterate函数。
struct node* reverse_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL) {
t = n;
n = n->next;
t->next = result;
result = t;
}
return result;
}
废话不说，O2反汇编。
00000000000008c0 <reverse_iterate>:
8c0: 48 85 ff test %rdi,%rdi
8c3: 74 20 je 8e5 <reverse_iterate+0x25>
8c5: 31 c9 xor %ecx,%ecx
8c7: 48 89 f8 mov %rdi,%rax
8ca: eb 07 jmp 8d3 <reverse_iterate+0x13>
8cc: 0f 1f 40 00 nopl 0x0(%rax)
8d0: 48 89 d0 mov %rdx,%rax
8d3: 48 8b 50 08 mov 0x8(%rax),%rdx
8d7: 48 89 48 08 mov %rcx,0x8(%rax)
8db: 48 89 c1 mov %rax,%rcx
8de: 48 85 d2 test %rdx,%rdx
8e1: 75 ed jne 8d0 <reverse_iterate+0x10>
8e3: f3 c3 repz retq
8e5: 31 c0 xor %eax,%eax
8e7: c3 retq
8e8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
8ef: 00
代码结构极其类似。但是由于寄存器染色的问题，result放在了ecs而非rsi上。所以8c5多了一行xor初始化，8d7是mov rcx。除此以外代码一模一样。
gdb对O2的调试问题
当你用gdb去调试这种优化过的代码，会出现非常有趣的情况。例如调试reverse_loop_tco为例，代码会在几个位置跳来跳去，就是不正常递归。n和result全都不显示，显示就是。如果你用disassemble reverse_loop_tco和si来调试的话，会发现，这其实是在汇编流上正常执行，然后地址被映射回了C源码，行为就显得诡异了。总的来说，O2不是一个用来调试的好版本。
C反转链表，TCO版本，带环
C代码在这里。
struct node* reverse_loop_tco(struct node *n, struct node *result)
{
struct node *t;
struct node *n1;
if (n == NULL || n->next == &node_nil) {
return result;
}
n1 = (struct node*)malloc(sizeof (struct node));
n1->i = n->i;
n1->next = result;
t = n->next;
n->next = &node_nil;
return reverse_loop_tco(t, n1);
}
这里我们不需要反汇编，结论也是很明显的——应当转为了迭代。这个解法的核心是malloc。因为在Python版本里我们就说过了，如果复用旧节点的话，cdr就会被指向下一跳，不能填充placeholder进去。
所以，请大家考虑一个问题。这个例子里是用C写的，使用malloc分配内存，没有回收释放过。如果这个代码使用GC语言编写，同时young gc算法是引用计数法，释放到分配有缓存队列(Python就是这个情况)。这个算法的空间复杂度是什么量级。如果young gc使用copy算法(Java就是这个情况)，那么算法的空间复杂度又是什么情况？这个问题在文章的后面会分析。
C反转链表，非TCO版本
我们先看不带loop的版本，源码长这个样子。
struct node* reverse_recursion(struct node *n)
{
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL) {
return n;
}
/* result can be defined just in here */
result = reverse_recursion(n->next);
n->next->next = n;
n->next = NULL;
return result;
}
O2反汇编后这样子：
0000000000000880 <reverse_recursion>:
880: 48 85 ff test %rdi,%rdi
883: 74 2b je 8b0 <reverse_recursion+0x30>
885: 53 push %rbx
886: 48 89 fb mov %rdi,%rbx
889: 48 8b 7f 08 mov 0x8(%rdi),%rdi
88d: 48 89 d8 mov %rbx,%rax
890: 48 85 ff test %rdi,%rdi
893: 74 15 je 8aa <reverse_recursion+0x2a>
895: e8 e6 ff ff ff callq 880 <reverse_recursion>
89a: 48 8b 53 08 mov 0x8(%rbx),%rdx
89e: 48 89 5a 08 mov %rbx,0x8(%rdx)
8a2: 48 c7 43 08 00 00 00 movq $0x0,0x8(%rbx)
8a9: 00
8aa: 5b pop %rbx
8ab: c3 retq
8ac: 0f 1f 40 00 nopl 0x0(%rax)
8b0: 31 c0 xor %eax,%eax
8b2: c3 retq
8b3: 0f 1f 00 nopl (%rax)
8b6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
8bd: 00 00 00
同样，代码解读并不难。但是意义就很有趣。这段代码确实调用了callq，所以是真递归，不满足TCO优化条件(或gcc无法优化)。但是并没有sub rsp，所以在递归时并没有预留本地空间。栈上除了rbx和ret地址外，应该什么都没有。在这段代码里，rbx代表n。所以这个算法会在每个栈帧里留下n，这也符合我们的推测——这个算法的空间消耗是N(准确说是2N，还有ret地址开销)。
无法优化的原因很简单。指针改变的顺序是从尾向头走，将每一层的节点指针压栈，我们才方便追踪每次改变时的尾节点。否则这个算法的复杂度将达到O(n^2)。
下面带loop版本的代码。
struct node* reverse_loop_recursion(struct node *n)
{
struct node *t;
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL || n->next->next == &node_nil) {
return n;
}
/* we had to keep t in stack. */
t = n->next;
n->next = &node_nil;
result = reverse_loop_recursion(t);
t->next = n;
n->next = NULL;
return result;
}
这段代码和最上面相比，非常类似。但是这段代码是有额外开销的。我们看O2反汇编。
0000000000000970 <reverse_loop_recursion>:
970: 48 85 ff test %rdi,%rdi
973: 74 53 je 9c8 <reverse_loop_recursion+0x58>
975: 55 push %rbp
976: 53 push %rbx
977: 48 83 ec 08 sub $0x8,%rsp
97b: 48 8b 6f 08 mov 0x8(%rdi),%rbp
97f: 48 85 ed test %rbp,%rbp
982: 74 3c je 9c0 <reverse_loop_recursion+0x50>
984: 48 8d 15 b5 06 20 00 lea 0x2006b5(%rip),%rdx # 201040 <node_nil>
98b: 48 39 55 08 cmp %rdx,0x8(%rbp)
98f: 48 89 f8 mov %rdi,%rax
992: 74 1b je 9af <reverse_loop_recursion+0x3f>
994: 48 89 fb mov %rdi,%rbx
997: 48 89 57 08 mov %rdx,0x8(%rdi)
99b: 48 89 ef mov %rbp,%rdi
99e: e8 cd ff ff ff callq 970 <reverse_loop_recursion>
9a3: 48 89 5d 08 mov %rbx,0x8(%rbp)
9a7: 48 c7 43 08 00 00 00 movq $0x0,0x8(%rbx)
9ae: 00
9af: 48 83 c4 08 add $0x8,%rsp
9b3: 5b pop %rbx
9b4: 5d pop %rbp
9b5: c3 retq
9b6: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
9bd: 00 00 00
9c0: 48 89 f8 mov %rdi,%rax
9c3: eb ea jmp 9af <reverse_loop_recursion+0x3f>
9c5: 0f 1f 00 nopl (%rax)
9c8: 31 c0 xor %eax,%eax
9ca: c3 retq
9cb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
这段代码里面有两个特征，975/976两行push，977行出现了sub rsp，97e行出现了callq。这是尾递归不可优化，栈上额外保留空间的特征。我们随后可以分析栈上都出现了什么。
975和976是两条push，rbp用来保存n->next(97b)，rbx用来保存n(994)，也就是一个保存源码里的n，一个保存源码里的t。至于那个sub rsp，直到后面add rsp我都没看到引用过rsp。貌似就是缓冲空间，没有别的作用。
我们分析是否能将n和t消除掉呢？结果是不行的。后续组链的核心就是t->next = n，这里t和n都是必须的。而通过n保存t呢？由于n节点不能新分配，因此需要原始复用。而原始复用中，需要借用next指针。因此这也是不可行的。因此，这里的额外空间花销是不可消除的。通过比较这段算法和原始的无环形态，我们可以看出，这个算法的空间复杂度还是O(n)，但是系数是2。
和TCO以及迭代版本的带环算法相比，TCO版本的空间复杂度貌似也是O(n)，系数为2n。因为新生成了n个对象，每个对象是一个node，有两个指针(一个指针一个数据空间)。所以总空间使用量为2n。但是如果没有外界干扰，系统采用引用计数gc的话。在上一轮循环结束时，原始node就是失去所有引用。虽然它还引用了node_nil，但是引用计数归零，所以直接释放回queue。下一轮循环的new过程中，又被复用。这个分析对于所有节点几乎都成立，只有一个节点除外——交叉节点。因此，总内存分配量其实也就是两个node。
而如果系统采用复制gc的话，那么情况就不一样了。由于不能保证运行过程中触发young gc，因此只能假定新生成n个对象，总空间使用量为2n。这样就和当前算法空间复杂度一致了。
java实现fib
java版本很简单
public static int fib (int n) {
if (n <= 0) {
return 1;
}
return fib(n-1) + fib(n-2);
}
用javap -v输出byte code decompiler，结果如下：
0: iload_0
1: ifgt 6
4: iconst_1
5: ireturn
6: iload_0
7: iconst_1
8: isub
9: invokestatic #2 // Method fib:(I)I
12: iload_0
13: iconst_2
14: isub
15: invokestatic #2 // Method fib:(I)I
18: iadd
19: ireturn
从字节码来分析，Java版本是没有做recursion转iterate优化的。我对JVM不熟，不能确定JVM或JIT时会不会进行优化。
gcc对fib的优化
gcc让我觉得更加惊人的是对fib的优化。源码很简单，请直接看“附录D: 用C解fib的三种解法源码”，我们关键是看O2优化。
int fib0(int n)
{
if (n <= 0) {
return 1;
} else {
return fib0(n-1) + fib0(n-2);
}
}
O2如下。
0000000000000720 <fib>:
720: 85 ff test %edi,%edi
722: 7e 27 jle 74b <fib+0x2b>
724: 55 push %rbp
725: 53 push %rbx
726: 31 ed xor %ebp,%ebp
728: 89 fb mov %edi,%ebx
72a: 48 83 ec 08 sub $0x8,%rsp
72e: 66 90 xchg %ax,%ax
730: 8d 7b ff lea -0x1(%rbx),%edi
733: 83 eb 02 sub $0x2,%ebx
736: e8 e5 ff ff ff callq 720 <fib>
73b: 01 c5 add %eax,%ebp
73d: 85 db test %ebx,%ebx
73f: 7f ef jg 730 <fib+0x10>
741: 48 83 c4 08 add $0x8,%rsp
745: 8d 45 01 lea 0x1(%rbp),%eax
748: 5b pop %rbx
749: 5d pop %rbp
74a: c3 retq
74b: b8 01 00 00 00 mov $0x1,%eax
750: c3 retq
751: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
756: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
75d: 00 00 00
代码并不复杂。但是有个非常吓人的地方。你看到了几次callq？
我们完整分析一下吧。上手检测edi(n)，如果小于等于0就返回1。然后推rbp和rbx进去。726和728乱序执行，清空ebp并且将n赋值给ebx。从736那个callq回来的add来看，ebp看来就是s。同样佐证的还有745行的赋值。每次调用时，传入n-1。每次循环间隙，运算n-2(733行)。人工写成循环的话，就是fib1。
我们来看一下fib1的O2结果。
0000000000000760 <fib1>:
760: 55 push %rbp
761: 53 push %rbx
762: 48 83 ec 08 sub $0x8,%rsp
766: 85 ff test %edi,%edi
768: 7e 26 jle 790 <fib1+0x30>
76a: 89 fb mov %edi,%ebx
76c: 31 ed xor %ebp,%ebp
76e: 66 90 xchg %ax,%ax
770: 8d 7b ff lea -0x1(%rbx),%edi
773: 83 eb 02 sub $0x2,%ebx
776: e8 e5 ff ff ff callq 760 <fib1>
77b: 01 c5 add %eax,%ebp
77d: 83 fb ff cmp $0xffffffff,%ebx
780: 7d ee jge 770 <fib1+0x10>
782: 48 83 c4 08 add $0x8,%rsp
786: 89 e8 mov %ebp,%eax
788: 5b pop %rbx
789: 5d pop %rbp
78a: c3 retq
78b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
790: bd 01 00 00 00 mov $0x1,%ebp
795: 48 83 c4 08 add $0x8,%rsp
799: 89 e8 mov %ebp,%eax
79b: 5b pop %rbx
79c: 5d pop %rbp
79d: c3 retq
79e: 66 90 xchg %ax,%ax
很类似。先判断edi(n)是否小于等于0，是的话，从790出去。随后同样是n赋值给ebx，清空ebp，调用。但是判断这行有点意思。在fib的形式里，fib的参数可以是0和-1(例如fib(1)的求值中，就会计算fib(0)和fib(-1))。因此，手工转写后，条件应当终止在n > -2上，而不是0。除此外，代码和fib版本高度一致。
但是，fib是什么？不可尾递归版本。无论是fib(n-1)还是fib(n-2)回来，都是要做一些事的。所以gcc实际上支持双路递归，非尾递归形态编译优化为迭代形态的。
顺带一提，fib其实是有TCO算法的，而且开销更小。具体来说就是附录D的fib2函数。但是这明显是另一种算法。
尾递归和转迭代关系
尾递归必然可以转为迭代形态，而可转为迭代形态的未必满足尾递归。
在x86-64的调用条件下，尾递归其实并不难实现。甚至非递归函数，只要满足TCO条件，也可以用这个优化来减少开销(无效的一次出入栈+一个字长的内存消耗)。假设存在函数f和g，f最后调用g并直接返回。f可以将g的参数设定到正确的寄存器后(这个和正常调用相同)，将callq g换为long jmp。g在完成调用后的ret会回复到f的调用者手里。
如果是x86的调用条件，要完成尾递归就比较麻烦了。f需要设定g的调用参数，这个参数只能写到f自己的参数地址上去。如果f的参数空间比g短，那尾递归无论如何无法通过这种方式完成。碰到pascal式调用，还能调整栈来解决这个问题。碰到C式调用，即使可以移动栈，空间清理也做不好。
而迭代转递归则是另一个事。我们可以简单研究一下递归可转迭代的条件，以及转换方法。假设递归满足以下模式。
- 退出条件在函数开头。这个条件可以被转换为一个退出判断函数test。
- 以调用自身的地点为界，之前的函数叫f1，之后的函数叫f2。
- 退出时可以将参数p转为另一个数据(例如恒定回复1)。这个转换参数叫final。
可以证明，递归可转为迭代的充分条件是。f1不直接向f2传递数据，包括递归的参数。f2的所有参与数据，只能从环境中，或递归函数的返回中获得。
具体来说，附录E给出了一个例子，如何完成递归转迭代。不过这个例子用的是双递归，所以只能转为单路迭代，迭代内还嵌套递归。另外代码也有一点改动，fib(n-2)，实际上需要用到参数。这里变成了从返回值中获得这个数。
至于gcc的优化，我测试了一下，是另一个套路。gcc对于某些递归后运算，可以将其转换为连续迭代来进行计算。主要就是+*这些常见运算。如果你把递归函数写成下面这样子的话，gcc就不优化了。
int foo(int n)
{
if (n <= 0) {
return 1;
}
return foo(n-1) << 1;
}
O2反汇编
0000000000000770 <foo>:
770: 85 ff test %edi,%edi
772: 7e 1c jle 790 <foo+0x20>
774: 48 83 ec 08 sub $0x8,%rsp
778: 83 ef 01 sub $0x1,%edi
77b: e8 f0 ff ff ff callq 770 <foo>
780: 48 83 c4 08 add $0x8,%rsp
784: 01 c0 add %eax,%eax
786: c3 retq
787: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
78e: 00 00
790: b8 01 00 00 00 mov $0x1,%eax
795: c3 retq
796: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
79d: 00 00 00
可以看到，这个函数保持了递归。
而这个函数是可以转为迭代的。具体可以参考附录E。
附录A：用Python解链表反向问题的六种解法源码
PLACEHOLDER = 'fix data'
def reverse_tco(ll, rslt):
if not ll:
return rslt
return reverse_tco(ll[1], [ll[0], rslt])
def reverse_loop_tco(ll, rslt):
if not ll or ll[1] == PLACEHOLDER:
return rslt
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return reverse_loop_tco(ll, rslt)
def reverse_recursion(ll):
if not ll[1]:
return ll
rslt = reverse_recursion(ll[1])
ll[1][1], ll[1] = ll, None
return rslt
def reverse_loop_recursion(ll):
if not ll[1] or ll[1][1] == PLACEHOLDER:
return ll
t, ll[1] = ll[1], PLACEHOLDER
rslt = reverse_loop_recursion(t)
t[1], ll[1] = ll, None
return rslt
def reverse_iterate(ll):
rslt = None
while ll:
rslt, ll[1], ll = ll, rslt, ll[1]
return rslt
def reverse_loop_iterate(ll):
rslt = None
while ll and ll[1] != PLACEHOLDER:
ll[1], rslt, ll = PLACEHOLDER, [ll[0], rslt], ll[1]
return rslt
def main():
t = [5, None]
ll = [1, [2, [3, [4, t]]]]
t[1] = ll[1][1]
print(ll)
# rslt = reverse_tco(ll, None)
# rslt = reverse_recursion(ll)
# rslt = reverse_iterate(ll)
rslt = reverse_loop_tco(ll, None)
# rslt = reverse_loop_recursion(ll)
# rslt = reverse_loop_iterate(ll)
print(rslt)
if __name__ == '__main__':
main()
附录B: 用C解链表反向问题的六种解法源码
#include <stdio.h>
#include <stdlib.h>
struct node {
int i;
struct node *next;
};
struct node node_nil = {-1, NULL};
int print_node(struct node *n, int depth)
{
if (n != NULL && depth != 0) {
printf("%i ", n->i);
print_node(n->next, depth-1);
} else {
printf("\n");
}
return 0;
}
struct node* reverse_tco(struct node *n, struct node *result)
{
struct node *t;
if (n == NULL) {
return result;
}
t = n->next;
n->next = result;
return reverse_tco(t, n);
}
struct node* reverse_recursion(struct node *n)
{
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL) {
return n;
}
/* result can be defined just in here */
result = reverse_recursion(n->next);
n->next->next = n;
n->next = NULL;
return result;
}
struct node* reverse_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL) {
t = n;
n = n->next;
t->next = result;
result = t;
}
return result;
}
struct node* reverse_loop_tco(struct node *n, struct node *result)
{
struct node *t;
struct node *n1;
if (n == NULL || n->next == &node_nil) {
return result;
}
n1 = (struct node*)malloc(sizeof (struct node));
n1->i = n->i;
n1->next = result;
t = n->next;
n->next = &node_nil;
return reverse_loop_tco(t, n1);
}
struct node* reverse_loop_recursion(struct node *n)
{
struct node *t;
struct node *result = NULL;
if (n == NULL) {
return NULL;
}
if (n->next == NULL || n->next->next == &node_nil) {
return n;
}
/* we had to keep t in stack. */
t = n->next;
n->next = &node_nil;
result = reverse_loop_recursion(t);
t->next = n;
n->next = NULL;
return result;
}
struct node* reverse_loop_iterate(struct node *n)
{
struct node *t;
struct node *result = NULL;
while (n != NULL && n->next != &node_nil) {
t = (struct node*)malloc(sizeof (struct node));
t->i = n->i;
t->next = result;
result = t;
t = n->next;
n->next = &node_nil;
n = t;
}
return result;
}
int main(int argc, char *argv[])
{
struct node node6 = {6, NULL};
struct node node5 = {5, &node6};
struct node node4 = {4, &node5};
struct node node3 = {3, &node4};
struct node node2 = {2, &node3};
struct node node1 = {1, &node2};
struct node *result;
/* node3.next = &node2; */
print_node(&node1, 7);
/* result = reverse_tco(&node1, NULL); */
/* result = reverse_recursion(&node1); */
/* result = reverse_iterate(&node1); */
result = reverse_loop_tco(&node1, NULL);
/* result = reverse_loop_recursion(&node1); */
/* result = reverse_loop_iterate(&node1); */
print_node(result, 7);
return 0;
}
附录C: 用Scheme解链表反向问题的六种解法源码
(define placeholder "fix data")
(define (reverse-tco ll rslt)
(if (eq? ll '())
rslt
(reverse-tco (cdr ll) (cons (car ll) rslt))))
(define (reverse-loop-tco ll rslt)
(if (or (eq? ll '())
(eq? (cdr ll) placeholder))
rslt
(let ((t (cdr ll)))
(set-cdr! ll placeholder)
(reverse-loop-tco t (cons (car ll) rslt)))))
(define (reverse-recursion ll)
(cond
((eq? ll '()) '())
((eq? (cdr ll) '()) ll)
(else
(let ((rslt (reverse-recursion (cdr ll))))
(set-cdr! (cdr ll) ll)
(set-cdr! ll '())
rslt))))
(define (reverse-loop-recursion ll)
(cond
((eq? ll '()) '())
((or (eq? (cdr ll) '())
(eq? (cddr ll) placeholder))
ll)
(else
(let ((t (cdr ll)))
(set-cdr! ll placeholder)
(let ((rslt (reverse-loop-recursion t)))
(set-cdr! t ll)
(set-cdr! ll '())
rslt)))))
(define (reverse-iterate ll)
(let ((rslt '())
(t '()))
(while (not (eq? ll '()))
(set! t (cdr ll))
(set-cdr! ll rslt)
(set! rslt ll)
(set! ll t))
rslt))
(define (reverse-loop-iterate ll)
(let ((rslt '())
(t '()))
(while (and
(not (eq? ll '()))
(not (eq? (cdr ll) placeholder)))
(set! t (cdr ll))
(set-cdr! ll placeholder)
(set! rslt (cons (car ll) rslt))
(set! ll t))
rslt))
(define ll '(1 2 3 4 5 6))
(let
((t (cddr ll)))
(set-cdr! (cdddr t) t))
(display ll)
(newline)
;; (display (reverse-tco ll '()))
;; (display (reverse-recursion ll))
;; (display (reverse-iterate ll))
(display (reverse-loop-tco ll '()))
;; (display (reverse-loop-recursion ll))
;; (display (reverse-loop-iterate ll))
附录D: 用C解fib的三种解法源码
int fib0(int n)
{
if (n <= 0) {
return 1;
} else {
return fib0(n-1) + fib0(n-2);
}
}
int fib1(int n)
{
int s;
if (n <= 0) {
return 1;
}
for (s = 0; n > -2; n-=2){
s += fib1(n-1);
}
return s;
}
int fib2(int n, int a, int b)
{
if (n == 0) {
return a;
}
return fib2(n-1, a+b, a);
}
int main(int argc, char *argv[])
{
int n = 20;
printf("fib0(%d): %d\n", n, fib0(n));
printf("fib1(%d): %d\n", n, fib1(n));
printf("fib2(%d): %d\n", n, fib2(n, 1, 1));
return 0;
}
附录E: 用Python解决递归转迭代
def fib(n):
if n <= 0:
return 1
return fib(n-1)+fib(n-2)
def iterate(test, final, f1, f2, p):
i = 0
while not test(p):
p = f1(p)
i += 1
p = final(p)
while i != 0:
p = f2(p)
i -= 1
return p
def fib1(n):
p = [n, 1]
def test(p):
return p[0] <= 0
def final(p):
return p
def f1(p):
p[0] -= 1
return p
def f2(p):
p[1] += fib1(p[0]-1)
p[0] += 1
return p
return iterate(test, final, f1, f2, p)[1]
def foo(n):
def test(p):
return p <= 0
def final(p):
return 1
def f1(p):
return p-1
def f2(p):
return p << 1
return iterate(test, final, f1, f2, n)
def main():
print(fib(10))
print(fib1(10))
print(foo(3))
if __name__ == '__main__':
main()