背景知识
- 函数调用栈的作用 ：保持函数调用时的上下文信息。 即保持入口环境.
- 操作系统如何实现递归调用。（压栈出栈）
递归
简单地说，在函数中存在着调用函数本身的情况，并且有一个出口条件。
function factorial(n) {
//出口条件
if (n <= 0) {
return 1;
} else {
//调用本身
return n * factorial(n - 1);
}
}当我们计算 factorial(6) 时，会产生如下展开：
6 * (5 * (4 * (3 * (2 * 1)))))
6 * (5 * (4 * (3 * 2))))
6 * (5 * (4 * 6)))
...
720 // <= 最终的结果尾递归
尾递归是指递归调用发生在函数的最后一个语句中，从而使得函数调用不需要保存多个调用栈帧（因为每一层级的计算结果都通过参数传递给了下一层），而只需一个即可。
尾递归优化主要的应用场景就是：在没有循环的函数式语言(比如java8)里面需要用尾递归当循环用而产生的调用栈爆栈问题。
function factorial(n, r) { // <= 这里把 n, r 作为迭代变量提出来
if (n <= 0) {
return 1 * r; // <= 递归终止
} else {
return factorial(n - 1, r * n); // <= 用迭代函数替代 factorial。
}
}我们像上面一个普通递归函数一样来展开和运算 factorial(6)：
factorial(6, 1) // 1 是 factorial(0) 的值，我们需要手动写一下
factorial(5, 6)
factorial(4, 30)
factorial(3, 120)
factorial(2, 360)
factorial(1, 720)
720 // <= 最终的结果跟上面的普通递归函数比起来，貌似尾递归函数因为在展开的过程中计算并且缓存了结果，
使得并不会像普通递归函数那样展开出非常庞大的中间结果，所以不会爆栈是吗？
当然不是！ 尾递归函数依然还是递归函数，如果不优化依然跟普通递归函数一样会爆栈，
该展开多少层依旧是展开多少层。不会爆栈是因为语言的编译器或者解释器所做了"尾递归优化"，才让它不会爆栈的。(当前不是所有语言都支持尾递归优化的)尾递归为什么可以优化
入口环境没意义的情况下为啥要保持入口环境？尾递归，就恰好是这种情况。
因为尾递归的情况下，我们保持这个函数的入口环境没意义，所以我们就可以把这个函数的调用栈给优化掉（某些语言的编译器或者解释器做了"尾递归优化"）。手动优化尾递归
假设我们的语言没有原生支持尾递归优化.比如 java 当前jvm 还未支持，等等其他一些尾支持的语言。
手动递归优化很简单，就是转成循环调用。
function factorial(_n, _r) { // <= _n, _r 用作初始化变量
var n = _n;
// <= 将原来的 n, r 变量提出来编程迭代变量
var r = _r;
// <= 迭代函数非常简单,就是更新迭代变量而已
function _fact(_n, _r) {
n = _n;
r = _r;
}
// <= 生成一个迭代循环
_fact_loop: while (true) {
if (n <= 0) {
return r;
} else {
// <= 执行迭代函数，并且进入下一次迭代
_fact(n - 1, r * n); continue _fact_loop;
}
}
}递归 vs 循环 vs 尾递归
递归之所以能写出比循环可读性高的代码是因为递归隐含了一个栈，
而用循环实现的时候需要手动维护一个栈。
尾递归需要依赖 语言的编译器或者解释器做"尾递归优化" 才能够实现 使用一个栈。
它让语言能够识别可以优化的方法是: 将每一步的计算结果作为参数不断向后传递。
文章评论