递归的实现——循环，汇编，CPS 与 y 组合子

递归和循环是等价的

如果定义一个概念需要用到这个概念本身，我们称它的定义是递归的（ Recursive ）。例如：

• beautiful

  an adjective used to describe something that is beautiful.

递归和循环是等价的 ，用循环能做的事用递归都能做，反之亦然。

举例子：

int loop(int n) {
    int sum = 0;
    for(int i=0; i<n; i++) {
          sum += i;
    }
    return sum;
}

逻辑等价于：

void loop(int i, int n) {
     if(i < n) {
         return i + loop(i+1, n);
     } else {
         return 0;
     }
}
loop(0, 10);

事实上有的编程语言（比如某些 LISP 实现）只有递归而没有循环。计算机指令能做的所有事情就是数据存取、运算、测试和分支、循环（或递归），在计算机上运行高级语言写的程序最终也要翻译成指令，指令做不到的事情高级语言写的程序肯定也做不到，虽然高级语言有丰富的语法特性，但也只是比指令写起来更方便而已，能做的事情是一样多的。

调用函数与递归的汇编实现

调用函数的汇编实现

在执行程序时，操作系统为进程分配一块栈空间来保存函数栈帧，每次调用一个函数都要分配一个栈帧来保存参数和局部变量。

#include <stdio.h>
int fun(int a, int b)
{
    int c = a+b;
    return c;
}
int main(void)
{
    int d= fun(123, 456);
    return d;
}

执行：

gcc main.c -g  #在编译时加上 -g 选项，用 objdump 反汇编时可以把 C 代码和汇编代码穿插起来显示
objdump -dS a.out

反汇编的结果很长，以下只列出我们关心的部分：

00000000004004d6 <fun>:
#include <stdio.h>
int fun(int a, int b)
{
  4004d6:	55                   	push   %rbp
  4004d7:	48 89 e5             	mov    %rsp,%rbp
  4004da:	89 7d ec             	mov    %edi,-0x14(%rbp)
  4004dd:	89 75 e8             	mov    %esi,-0x18(%rbp)
    int c = a+b;
  4004e0:	8b 55 ec             	mov    -0x14(%rbp),%edx
  4004e3:	8b 45 e8             	mov    -0x18(%rbp),%eax
  4004e6:	01 d0                	add    %edx,%eax
  4004e8:	89 45 fc             	mov    %eax,-0x4(%rbp)
    return c;
  4004eb:	8b 45 fc             	mov    -0x4(%rbp),%eax
}
  4004ee:	5d                   	pop    %rbp
  4004ef:	c3                   	retq
  
00000000004004f0 <main>:
int main(void)
{
  4004f0:	55                   	push   %rbp
  4004f1:	48 89 e5             	mov    %rsp,%rbp
  4004f4:	48 83 ec 10          	sub    $0x10,%rsp
    int d= fun(123, 456);
  4004f8:	be c8 01 00 00       	mov    $0x1c8,%esi
  4004fd:	bf 7b 00 00 00       	mov    $0x7b,%edi
  400502:	e8 cf ff ff ff       	callq  4004d6 <fun>
  400507:	89 45 fc             	mov    %eax,-0x4(%rbp)
    return d;
  40050a:	8b 45 fc             	mov    -0x4(%rbp),%eax
}

main 函数太特殊了，我们先把fun函本身数的过程的汇编代码过一遍。

必须要知道的前置知识是： 在 x86 平台上这个栈是从高地址向低地址增长的，esp 寄存器总是指向栈顶，ebp 总是指向当前栈帧的栈底。32 位开头的 x86 汇编，是 e 开头，如 esp，ebp ； 64 位是 r 开头，如 rsp，rbp 。

由于给出的例子都在我本机（ 64 位）进行测试，命名都用 r 开头。

int fun(int a, int b)
{
  4004d6:	55                   	push   %rbp
  4004d7:	48 89 e5             	mov    %rsp,%rbp

push %rbp 指令等价于下面两条指令：

subq $8, %rsp （用伪语言介绍就是：%rsp = %rsp - 8，因为rsp 寄存器总是指向栈顶，所以 esp 栈指针-8，指向下面 8 字节后的地方，压了数据进栈后，指针要变嘛。）

movq %rbp, (%rsp) （ 也就是：rsp 的值 = rbp 的值，将 rbp 的数据放进栈顶指针 rsp 指向的地方）

注意的是，main 函数是最先调用的，所以这里的 rbp 值是 main 函数的栈底指针。

这里为什么要把 main 函数中的 rbp 的值压栈呢？

要注意rbp 总是指向当前栈帧的栈底，所以是不会有任何变动的，会利用 rbp + 偏移值来访问栈里的变量。

但是呢，全局只有一个 rbp 寄存器，main 函数原来的 rbp 值（也就是栈底）假设是 0x1234，在 fun 函数时，rbp 值就要改变成 fun 函数的栈底指针了。

4004d7: 48 89 e5 mov %rsp,%rbp

这里，为什么又把 main 函数 rsp （栈顶）的值赋值给 foo 函数的 rbp （栈底）呢？因为一个线程（ thread ）只有一个栈，函数都是公用一个栈的。所以，main 函数的栈与 foo 函数的栈是连在一起的——也就是说，main 的栈顶就是 foo 函数的栈底。

栈的布局是这样的:

0x123 rbp(main 栈底)[实际并不存在，是以前的值，便于理解]
0x11f c
0x11b b
0x117 a
0x113 rbp(foo 栈底) rsp(main 栈顶,foo 栈顶)
0x109 rsp(foo 栈顶)-4，foo 有多少参数，就这样往下跑。

接下来就是真正执行 foo 函数内的过程了：

  4004da:	89 7d ec             	mov    %edi,-0x14(%rbp)
  4004dd:	89 75 e8             	mov    %esi,-0x18(%rbp)
    int c = a+b;
  4004e0:	8b 55 ec             	mov    -0x14(%rbp),%edx
  4004e3:	8b 45 e8             	mov    -0x18(%rbp),%eax
  4004e6:	01 d0                	add    %edx,%eax

esi与edi通常代表不变的值，用来放函数的参数。

注意%edi 与 %esi已经在 main 函数体里，在调用 foo 之前赋值了：

  4004f8:	be c8 01 00 00       	mov    $0x1c8,%esi
  4004fd:	bf 7b 00 00 00       	mov    $0x7b,%edi
  400502:	e8 cf ff ff ff       	callq  4004d6 <fun>

所以现在的内存布局是这样的：

0x123 rbp(main 栈底)[实际并不存在，是以前的值，便于理解]
0x11f c
0x11b b
0x117 a
0x113 rbp(foo 栈底) rsp(main 栈顶)[实际并不存在，是以前的值，便于理解]
0x099 123
0x095 456 rsp(foo 栈顶)

foo 函数的汇编就是把$0x7b （ 10 进制是 123 ）与$0x1c8 （ 10 进制是 456 ）分别存在 edx 与 eax，然后做加运算，结果在eax上（返回值通过 eax 寄存器传递）

最后:

  4004e8:	89 45 fc             	mov    %eax,-0x4(%rbp)
    return c;
  4004eb:	8b 45 fc             	mov    -0x4(%rbp),%eax
}
  4004ee:	5d                   	pop    %rbp
  4004ef:	c3                   	retq

把123 + 456得出的在 eax 的值，赋值给 rbp （栈底）-4 的地方，弹出 rbp （栈顶）原来的值（ main 的栈顶），调用 retq 指令（ retq 是 call 的逆指令），返回到原来 call 的地址后运行。

递归的汇编实现

递归无非就是嵌套的函数调用，a 函数调用回 a 函数，不停的调用 call 指令，rbp （栈顶）不停往下跑，如：

0x123 rbp(main 栈底)[实际并不存在，是以前的值，便于理解]
0x11f c
0x11b b
0x117 a
0x113 rbp(foo 栈底) rsp(main 栈顶)[实际并不存在，是以前的值，便于理解]
0x099 123
0x095 456 rsp(foo 栈顶) 
假设 foo 是递归函数：
0x113 rbp(新 foo 栈底) rsp(旧的 foo 栈顶)[实际并不存在，是以前的值，便于理解]
0x099 123
0x095 456 rsp(新 foo 栈顶) 
。。。

最终，如果没有终止条件，自然栈的容量超过操作系统允许的一个进程的最大值，stackoverflow （栈溢出）

尾调用 (tail call) 和尾递归 (tail recursion)

• 非尾递归算法，需要 O (n) 的调用栈空间

• 尾递归是尾调用的特殊情形，尾调用并不要求 callee 和 caller 是同一个函数。

• 尾递归太特殊了，太容易优化了，所以在源码层面就能做递归到迭代的变换。

而一般的尾调用，callee 可能和 caller 没有任何联系，优化就只能寄期望于编译器或虚拟机了。

说到递归，不得不说递归的一种特殊形式：尾调用 (tail call)，指一个函数里的最后一个动作是返回一个函数的调用结果的情形。

而**尾递归 (tail recursion)**是为调用的的特殊情形，callee 和 caller 是同一个函数，而尾调用并不要求 。因此尾递归可以很简单的就可以做优化。

而一般的尾调用，callee 可能和 caller 没有任何联系，优化就只能寄期望于编译器或虚拟机了。

void foo(int a, b){
    bar(a+12, b*99+a)
}

就是尾调用。

而

void foo(int a, b){
    foo(a+12, b*99+a)
}

就是尾递归。

但是

void foo(int a, b){
    12 + foo(a, b)
}

就啥都不是，只是递归。

尾递归的优化从函数调用的汇编实现很容易理解，只要不涉及多余的参数（也就是不用额外的栈容量存，栈顶不用往下扩展再调用回函数），直接就可以改变 %edi, %esi的值，重新调用函数，也就是说不用任何额外的栈变量。

我想举一个尾递归以及非尾递归的例子的汇编代码在此，结果发现，gcc 除了对尾递归优化，已经用了黑科技优化递归- = - （ clang 没有）。

   int sum (int n) {
     if (n > 0)
       return n + sum (n - 1);
     else
       return 0;
   }

会优化成：

   int sum (int n) {
     int acc = 0;
     while (n > 0) {
       acc += n;
       n -= 1;         
     }
     return acc;
   }

只查到 gcc 的源码实现， 根据注释，优化的规律是这样的：

设两个变量 a_acc = 0 , m_acc = 1

对于a + m* f(...) 的递归形式，都拓展成a_acc + (a + m * f(...)) * m_acc，

a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(…)

可以参考 gcc 的源码 https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-tailcall.c， 我暂时还没有搞懂这个优化是怎么做的。

任何的递归，都可以转换成尾调用，然后优化。

• 如果算法本身就是尾递归的，那么，可以直接改写成迭代，这是尾调用优化的一种特例。

• 如果算法本身是非尾递归的，那么，CPS 变换可以将算法改写成尾调用形式，从而可以进行尾调用优化。

  改写过后的空间复杂度仍然是 O (n)，只不过是从 O (n) 的栈变成了 O (n) 的 continuation chain，这个改变对支持尾调用优化的简单解释器是有意义的。

此节的知识皆来自于此答案，在下只是做了推演：

https://www.zhihu.com/question/28458981/answer/40941851

我抄袭一下答案来讲解一下里面的Lua代码：

-- 递归版本
function sum(n)
    if n == 0 then
        return n
    else
        return n + sum(n - 1)
    end
end

-- 对于 sum，很容易找到尾递归版本
function sum_tail(n, result)
    if n == 0 then
        return result
    else
        return sum_tail(n - 1, result + n)
    end
end

-- 尾递归版本可以直接翻译成迭代: 外层增加 while true，将每个递归调用改成修改形参再 continue
function sum_iter(n, result)
    while true do
        if n == 0 then
            return result
        else
            n, result = n - 1, result + n
        end
    end
end

-- 对非尾递归算法(sum)进行 CPS 变换，使得所有调用都变成尾调用，从而允许解释器做尾调用优化
function sum_cps(n, k)
    if n == 0 then
        return k(n)
    else
        return sum_cps(n - 1, function(result)
            return k(result + n)
        end)
    end
end

-- CPS + trampoline，不再依赖解释器的尾调用优化
function trampoline_driver(v, k)
    while k do
        v, k = k(v)
    end
    return v
end
function sum_trampoline(n, k)
    if n == 0 then
        return n, k
    else
        return nil, function()
            return sum_trampoline(n - 1, function(result)
                return result + n, k
            end)
        end
    end
end

-- 递归深度为 N
local N = 100000
print(sum(N)) -- 溢出
print(sum_tail(N, 0)) -- 利用解释器的尾调用优化，不溢出
print(sum_iter(N, 0)) -- 直接改写成迭代，当然不溢出
print(sum_cps(N, identity)) -- 从非尾递归版本 sum 改写来的，依赖解释器的尾调用优化，不溢出
print(trampoline_driver(sum_trampoline(N, identity))) -- 既不依赖解释器的尾调用优化，也不溢出

递归，尾递归以及迭代的版本很容易看懂就不讲了，主要讲讲递归的 CPS 变换以及 CPS + trampoline （蹦床），即是怎么把递归转成普通的函数链调用。

print(sum_cps(N, identity)) -- 从非尾递归版本 sum 改写来的，依赖解释器的尾调用优化，不溢出
print(trampoline_driver(sum_trampoline(N, identity))) -- 既不依赖解释器的尾调用优化，也不溢出

递归的 CPS 变换

N = 10000
id = λ x:x
sum_cps(N, identity)
-- 对非尾递归算法(sum)进行 CPS 变换，使得所有调用都变成尾调用，从而允许解释器做尾调用优化
function sum_cps(n, k)
    if n == 0 then
        return k(n)
    else
        return sum_cps(n - 1, function(result)
            return k(result + n)
        end)
    end
end

以 sum_cps(2, λ x:x) 为例子，其中设函数 id为 λ x : x

调用展开如下：

• sum_cps(2, identity)
• return sum_cps(1, λ result : id(result + 2) end)
• return sum_cps(0, λ result : (λ result : id(result + 2)) (result+1) )
• return （λ result : (λ result : id(result + 2)) (result+1)）(0) 最后调用 0

把 0 代入进去，计算最后的结果即可，也就是：

• (λ result : id(result + 2)) (0+1)
• id(0+1 +2)
• id(3)

也就是 3，其实CPS 转换就是，原来递归版本On 的栈的函数参数，转换成一个个尾调用函数的调用链。

这样子支持尾调用的编译器（解释器）就能够对此进行优化，

CPS + trampoline （蹦床）

identity = λ x: x, nil
trampoline_driver(sum_trampoline(N, identity))

-- CPS + trampoline，不再依赖解释器的尾调用优化
function trampoline_driver(v, k)
    while k do
        v, k = k(v)
    end
    return v
end
function sum_trampoline(n, k)
    if n == 0 then
        return n, k
    else
        return nil, function()
            return sum_trampoline(n - 1, function(result)
                return result + n, k
            end)
        end
    end
end

同样，我们展开看看：

• trampoline_driver( sum_trampoline(3, identity) )
• trampoline_driver( nil, λ: sum_trampoline(2, λ result: result + 3, identity) )
• v, k = λ: sum_trampoline(2, (λ result: result + 3, identity) ) (nil)
• v, k = nil, (λ: sum_trampoline(1, λ result: result + 2, (λ result: result + 3, identity) ) )(nil)
• v, k = nil, λ: sum_trampoline(0, (λ result: result + 1, λ result: result + 2, (λ result: result + 3, identity)) ) （ nil ）
• v, k = 0, (λ result: result + 1, λ result: result + 2, (λ result: result + 3, identity))(0)
• v, k = (λ result: result + 1, λ result: result + 2, (λ result: result + 3, identity)) (0)
• v, k = (0 + 1, λ result: result + 2, (λ result: result + 3, identity))
• v, k = λ result: result + 2, (λ result: result + 3, identity)) (1)、
• v, k = 0 + 1 + 2, (λ result: result + 3, identity))
• v, k = (λ result: result + 3, identity)(3)
• v, k = 0 + 1 + 2 + 3, identity
• v, k = identity( 0 + 1 + 2 + 3)
• v, k = 6, nil
• return v

就是这样，不停的循环将得到的未执行的函数(A thunk, in programming language jargon, is simply some expression wrapped in an argument-less function.)传递给 k，最后反过来调用 - = -

那为什么叫 trampoline （蹦床）呢？

看它最后在在求值时，也即是：

- v, k = 0, (λ result: result + 1,  λ result: result + 2, (λ result: result + 3, identity))(0)
- v, k = (λ result: result + 1,  λ result: result + 2, (λ result: result + 3, identity)) (0)
- v, k = (0 + 1,  λ result: result + 2, (λ result: result + 3, identity))
- v, k =  λ result: result + 2, (λ result: result + 3, identity)) (1)、
- v, k = 0 + 1 + 2, (λ result: result + 3, identity))
- v, k = (λ result: result + 3, identity)(3)
- v, k =  0 + 1 + 2 + 3,  identity

是不是相当于弹起来一个 v，再回到去原来的蹦床（在这里是 k ），重新求值把 v 弹出来。

组合子

递归是靠有名字的函数来实现的。

let fun = λ x: fun(x)
fun(x) # 这样子是递归函数

如果在没有实现变量绑定的解释器里（例如自己写的简陋的解释器），怎么样实现递归呢？

λ x: ???(x) 里， ??? 该填上什么呢？

在 lambda 演算里确实没有 let， 对此前人已经找出了解决方法，要讲清楚 Y 的来龙去脉，可是非常难。事实上，连发现它的哈斯卡大神也感慨不已，觉得自己捡了个大便宜，还因此将 Y 纹在了自己的胳膊上。我现在就只讲 Y 的用处了。

Y 大概是，先制造一个不断的返回自身的整个函数体，最后到了返回 自身的函数体=真正的自身 [也就是数学上的不动点，将函数应用于自身得到自身，x = f(x) ] 时，就实现了递归了 - = -，有兴趣可以查查。

看到最后的你

本文只是抛砖引玉； P

在下在 Shopee 工作，觉得水深火热不喜欢加班的同学可以考虑一下

拒绝 996，那就来 shopee，待遇 work life balance 两不： https://www.v2ex.com/t/672561#reply1