递归 尾递归 CPS trampoline memoize 缓存
本文使用 JavaScript 进行描述。
本文简要介绍了几种常见的递归用法。文中出现的代码仅供示意，不代表可以直接用于生产环境。
作者水平有（很）限（菜），疏漏之处敬请谅解。
尾递归
先来提一下尾递归，顾名思义就是递归调用的位置在函数的最后。
如果你对递归和尾递归等相关概念还不太熟悉，可以看看张大胖学递归归这篇文章。
这里需要解释的是，尾递归本身只是一种书写的方法，就是字面意思上的把递归调用的位置放到了函数最后，仅此而已，并不能提升递归的效率。
真正起到魔法作用，其实是尾递归调用优化。宣称自己是函数式语言的都支持这种优化。你也可以用“一个语言是否支持尾递归优化”来判断这种语言是否是函数式语言。;)
JavaScript 主流实现仍然缺少对尾递归调用优化的支持，所以本文的某些例子仍然有可能导致溢出。
不过，在不引起歧义的前提下，也可以用尾递归来指代尾递归调用优化。
蹦蹦床
刚才说某些语言并不支持尾递归调用优化，难道除了干等着语言的实现者来实现，就没有办法了么？
有！蹦蹦床就是其中一种比较好玩的东西。看名字就比较好玩，它的运行原理也很像一张蹦床。为什么说它是个蹦床呢？先看代码：
function trampoline(maybeFuction) {
while (maybeFuction && maybeFuction instanceof Function) {
// 如果参数是个函数，那么执行这个函数，拿到执行结果，作为下次循环的判断条件
maybeFuction = maybeFuction();
}
// 如果不是函数，则就会跳出循环，返回最终结果
return maybeFuction;
}
那么怎么使用呢？首先，我们需要对原有的尾递归函数做一点非常微小的改动。比如这是一个尾递归形式的斐波那契数列：
// 修改前
function fibonacci(n, a = 0, b = 1) {
if (n === 0) {
return a;
} else {
return fibonacci(n - 1, b, a + b);
}
}
只需要把原来递归的动作包裹在函数中即可：
// 修改后
function fibonacci(n, a = 0, b = 1) {
if (n === 0) {
return a; // 蹦床会直接返回这个值
} else {
// 把要执行的动作放在函数里，这样蹦床就会弹起这个动作
return () => fibonacci(n - 1, b, a + b);
}
}
然后套上蹦床来执行，就不会发生栈溢出了。
trampoline(fibonacci(10000));
我们大致分析一下执行流程。如果返回值是函数，则证明接下来的动作其实并没有执行完毕，那就弹起来执行这个函数，如果再执行结果还是函数，那就再弹起来再执行，直到不是函数，则证明整个调用过程结束，可以返回结果了。
所以这张蹦床是只会弹起函数，如果不是函数，啪叽，摔地上了。
这种作法消灭函数调用栈的原理是，修改原来的递归函数，把递归的动作包裹在函数中直接返回，这样自然不会占用函数调用栈，最后其实真正触发执行的是交给了蹦床，而蹦床里用的是循环语句，也不会占用额外空间。
除了上面说的用法，蹦床还能用来改造相互递归调用，原理是一致的。感兴趣的同学可以自己查阅一下，在此就不赘述了。
Continuation-passing style
CPS (Continuation-passing style) 指的是一种编程风格，这种风格会把函数将要执行的下一步动作包裹在函数中，在需要递归的时候，把动作传入递归参数中，在下次需要的时候再执行。
是不是和上面的蹦床挺像？其实是有差距的，蹦床是一个“第三方”帮助函数，而 CPS 一种递归写法，两者甚至还能结合使用。
我们这里举一个二叉树遍历的栗子来进行说明。
先看看一般的递归写法，想要遍历二叉树，首先要有一颗二叉树，大概长这样。
/************
1
/ \
2 5
/ \
3 4
*************/
tree = {
value: 1,
left: {
value: 2,
left: {
value: 3
},
right: {
value: 4
}
},
right: {
value: 5
}
}
先来写一下前序遍历。我们回忆一下前序遍历的定义：首先访问根节点，然后访问左子树，最后访问右子树。对于左子树和右子树，再次用前序遍历的方式进行访问，直到没有节点可以访问为止。
这是个典型的递归定义，所以我们把根节点作为函数参数，进行递归处理
function preorder(nowNode) {
if (nowNode != null) {
console.log(nowNode.value); // 前序遍历，所以先打印根节点
preorder(nowNode.left); // 然后进行左子树遍历
preorder(nowNode.right); // 右子树遍历
}
}
preorder(tree);
虽然这种写法很简单很清晰，但是，为了按要求实现遍历，必须要等到左子树遍历执行完才能执行右子树的遍历。也就意味着这种写法在递归发生时需要保存调用堆栈信息，没有办法享受到尾递归优化。
这里就需要 CPS 登场了。
首先，我们要想办法把接下来的动作能随参数携带，这样在递归的时候就可以直接返回，也就是所谓的尾递归。
但是，遍历动作没办法以简单的数值形式进行传递，所以我们把它包裹在函数中，也就是说，我们把接下来要做的动作放进函数里，传递给下一次递归。
所以，我们需要一个参数，就取名叫 continuation 吧
function preorder(nowNode, continuation) {
if (nowNode != null) {
console.log(nowNode.value); // 前序遍历，先打印根节点
// 注意下面这行代码，依然先遍历左子树，所以 nowNode.left 作为递归的第一个参数
// 遍历右子树的动作属于“接下来要做的事情”，所以包装在函数中，作为下次递归的 continuation 参数。
// 而当前这次递归的 continuation 就变成了“接下来之后”“再接下来”做的事情，所以就是下次递归 continuation 参数中的 continuation 参数。
// 比较绕，理解一下
return preorder(nowNode.left, () => preorder(nowNode.right, continuation));
} else {
// 当前节点为 null 也就是说到底了，此时就要开始做“接下来要做的事情”了。
return continuation();
}
}
那么 continuation 的初始值是什么呢？第一次其实没有“接下来要做的事情”，所以初始值就是啥都不做的空函数。所以这样调用即可：
preorder(tree, () => {})
最后我们配合蹦床函数，使得在不支持尾递归优化的环境下也不会溢出，只需要非常简单的在递归的位置套上一层函数。
function preorder(nowNode, continuation) {
if (nowNode != null) {
console.log(nowNode.value);
// 递归的位置包一层函数，让蹦床工作起来
return () => preorder(nowNode.left, () => preorder(nowNode.right, continuation));
} else {
return continuation();
}
}
trampoline(preorder(tree, () => {}));
可见，这种作法并不是完全消灭了递归传递的链条，而是把它从栈移动到了函数里，而函数所在的内存区域并没有像栈那样受限，所以本来在栈中会溢出的就不会溢出了。
最后再给出中序遍历和后续遍历的代码，以供对比参考。注意三种遍历方式的打印语句分别处于哪一层 continuation。
// 中序
function inorder(nowNode, continuation) {
if (nowNode == null) {
return continuation();
} else {
return inorder(
nowNode.left,
() => {
console.log(nowNode.value);
return inorder(nowNode.right, continuation);
}
);
}
}
// 后序
function postorder(nowNode, continuation) {
if (nowNode == null) {
return continuation();
} else {
return postorder(
nowNode.left,
() => postorder(
nowNode.right,
() => {
console.log(nowNode.value);
return continuation();
}
)
);
}
}
这里留个问题，聪明的你能不能试着把 fibonacci 改写成 CPS 风格的代码呢？
CPS 好是好，就是太费脑子。那么有没有可能自动把一个递归函数转换成 CPS 呢？这样不就太爽啦？写出简单的递归代码，然后自动生成 CPS 代码，然后自动套上蹦床！小白啥也不做也能写出高效的递归了！
你想的真美好，现实是…还真有！甚至有些语言都内置了通用的自动转换的函数！真的是小白福音！
鉴于篇幅的原因（其实因为我不会），对于通用的 CPS 转换的原理感兴趣的同学可以阅读文末给出的参考文章（需要 lambda 演算相关的知识才能看懂）。
在递归中使用缓存
递归存在的另一个问题就是会重复计算相同的函数调用。(其实非递归形式也存在这种现象。)
一种通常的作法就是将函数结果缓存起来，下次遇到相同的调用时，直接返回上次计算的结果。
比如这是一个经典的斐波那契数列的递归写法：
function fibonacci(n) {
if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
我们可以像这样手动的给它加上缓存：
let cache = {};
function fibonacci(n) {
if (n in cache) { // 命中缓存
value = cache[n];
} else {
if (n == 0 || n == 1) {
value = n;
} else {
value = fibonacci(n - 1) + fibonacci(n - 2);
}
cache[n] = value; // 存入缓存
}
}
有了缓存，就可以免去多次重复计算的开销。但是这种必须修改原函数才能实现缓存的方式显然不够通用。
我们可以写一个高阶函数，使用函数的参数列表作为缓存的 key，利用闭包来存放缓存，最后生成一个带缓存的函数。
function memoize(func) {
let cache = {};
return function() {
// arguments 是函数的参数信息的封装
// [...arguments] 可以把它转成数组，作为缓存的 key
// 如果参数不在缓存中，就使用 apply 调用原函数得到结果，并缓存
if (arguments in cache) {
return cache[[...arguments]];
} else {
return cache[[...arguments]] = func.apply(this, arguments);
}
};
}
这样就可以非侵入地定义任意带缓存的函数了：
// 原始的未经修改的 fibonacci
function fibonacci(n) {
if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
// 生成出带缓存的版本
let memoized_fibonacci = memoize(fibonacci);
memoized_fibonacci(10);
这种作法所依赖的前提条件是，递归的函数必须是 引用透明 的。
引用透明的意思也就是说，函数的返回值只与参数有关。如果 f 函数具有引用透明的性质，那么你今天调用 f(1) 的结果是 1 ，那么明天、明年调用它，在任何代码段中调用它，它的结果始终是 1 。
比如如果一个函数读取了数据库中的值，那么可能过一会儿调用的返回值就不同了，那它就不是一个引用透明的函数。
显然，引用透明的函数可以被安全缓存。
总结
递归中有太多有趣知识，但是工作中却很少使用，尤其是对于广大使用非函数式编程的程序员。这里抛砖引玉，希望能让各种程序员都能体会到递归的美妙！
本人也是小白级别，如果阅读过程中发现了什么错误疏漏、晦涩语句，欢迎在下面留言交流。
参考文章
性能优化：memoization
尾递归与Continuation
JavaScript调用栈、尾递归和手动优化
CPS变换与CPS变换编译
On Recursion, Continuations and Trampolines
网友评论