转载

递归有关的几个小问题

引子

在加密系列里突然出这么一个问题，确实有点怪。我犹豫了一下，还是先写了再说。

这个问题的提起，是公司老大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()

原文 http://blog.shell909090.org/blog/archives/2864/

正文到此结束