递归的实现 —— 循环，汇编， CPS 与 y 组合子
递归的实现——循环，汇编，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, identityv, k = identity( 0 + 1 + 2 + 3)v, k = 6, nilreturn 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