JavaScript专题之递归

[mqyqingfeng]

定义

程序调用自身的编程技巧称为递归(recursion)。

阶乘

以阶乘为例：

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

示意图(图片来自 wwww.penjee.com)：

斐波那契数列

在《JavaScript专题之函数记忆》中讲到过的斐波那契数列也使用了递归：

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)) // 1 1 2 3 5

递归条件

从这两个例子中，我们可以看出：

构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。

总结一下递归的特点：

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

了解这些特点可以帮助我们更好的编写递归函数。

执行上下文栈

在《JavaScript深入之执行上下文栈》中，我们知道：

当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。

试着对阶乘函数分析执行的过程，我们会发现，JavaScript 会不停的创建执行上下文压入执行上下文栈，对于内存而言，维护这么多的执行上下文也是一笔不小的开销呐！那么，我们该如何优化呢？

答案就是尾调用。

尾调用

尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。

举个例子：

// 尾调用
function f(x){
    return g(x);
}

然而

// 非尾调用
function f(x){
    return g(x) + 1;
}

并不是尾调用，因为 g(x) 的返回值还需要跟 1 进行计算后，f(x)才会返回值。

两者又有什么区别呢？答案就是执行上下文栈的变化不一样。

为了模拟执行上下文栈的行为，让我们定义执行上下文栈是一个数组：

    ECStack = [];

我们模拟下第一个尾调用函数执行时的执行上下文栈变化：

// 伪代码
ECStack.push(<f> functionContext);

ECStack.pop();

ECStack.push(<g> functionContext);

ECStack.pop();

我们再来模拟一下第二个非尾调用函数执行时的执行上下文栈变化：

ECStack.push(<f> functionContext);

ECStack.push(<g> functionContext);

ECStack.pop();

ECStack.pop();

也就说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

所以我们只用把阶乘函数改造成一个尾递归形式，就可以避免创建那么多的执行上下文。但是我们该怎么做呢？

阶乘函数优化

我们需要做的就是把所有用到的内部变量改写成函数的参数，以阶乘函数为例：

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

console.log(factorial(4, 1)) // 24

然而这个很奇怪呐……我们计算 4 的阶乘，结果函数要传入 4 和 1，我就不能只传入一个 4 吗？

这个时候就要用到我们在《JavaScript专题之偏函数》中编写的 partial 函数了：

var newFactorial = partial(factorial, _, 1)

newFactorial(4) // 24

应用

如果你看过 JavaScript 专题系列的文章，你会发现递归有着很多的应用。

作为专题系列的第十八篇，我们来盘点下之前的文章中都有哪些涉及到了递归：

1.《JavaScript 专题之数组扁平化》：

function flatten(arr) {
    return arr.reduce(function(prev, next){
        return prev.concat(Array.isArray(next) ? flatten(next) : next)
    }, [])
}

2.《JavaScript 专题之深浅拷贝》：

var deepCopy = function(obj) {
    if (typeof obj !== 'object') return;
    var newObj = obj instanceof Array ? [] : {};
    for (var key in obj) {
        if (obj.hasOwnProperty(key)) {
            newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
        }
    }
    return newObj;
}

3.JavaScript 专题之从零实现 jQuery 的 extend：

// 非完整版本，完整版本请点击查看具体的文章
function extend() {

    ...

    // 循环遍历要复制的对象们
    for (; i < length; i++) {
        // 获取当前对象
        options = arguments[i];
        // 要求不能为空 避免extend(a,,b)这种情况
        if (options != null) {
            for (name in options) {
                // 目标属性值
                src = target[name];
                // 要复制的对象的属性值
                copy = options[name];

                if (deep && copy && typeof copy == 'object') {
                    // 递归调用
                    target[name] = extend(deep, src, copy);
                }
                else if (copy !== undefined){
                    target[name] = copy;
                }
            }
        }
    }

    ...

};

4.《JavaScript 专题之如何判断两个对象相等》：

// 非完整版本，完整版本请点击查看具体的文章
// 属于间接调用
function eq(a, b, aStack, bStack) {

    ...

    // 更复杂的对象使用 deepEq 函数进行深度比较
    return deepEq(a, b, aStack, bStack);
};

function deepEq(a, b, aStack, bStack) {

    ...

    // 数组判断
    if (areArrays) {

        length = a.length;
        if (length !== b.length) return false;

        while (length--) {
            if (!eq(a[length], b[length], aStack, bStack)) return false;
        }
    }
    // 对象判断
    else {

        var keys = Object.keys(a),
            key;
        length = keys.length;

        if (Object.keys(b).length !== length) return false;
        while (length--) {

            key = keys[length];
            if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack))) return false;
        }
    }

}

5.《JavaScript 专题之函数柯里化》：

// 非完整版本，完整版本请点击查看具体的文章
function curry(fn, args) {
    length = fn.length;

    args = args || [];

    return function() {

        var _args = args.slice(0),

            arg, i;

        for (i = 0; i < arguments.length; i++) {

            arg = arguments[i];

            _args.push(arg);

        }
        if (_args.length < length) {
            return curry.call(this, fn, _args);
        }
        else {
            return fn.apply(this, _args);
        }
    }
}

写在最后

递归的内容远不止这些，比如还有汉诺塔、二叉树遍历等递归场景，本篇就不过多展开，真希望未来能写个算法系列。

专题系列

JavaScript专题系列目录地址：https://github.com/mqyqingfeng/Blog。

JavaScript专题系列预计写二十篇左右，主要研究日常开发中一些功能点的实现，比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里、递归、乱序、排序等，特点是研(chao)究(xi) underscore 和 jQuery 的实现方式。

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。

[SilenceZeng]

阶乘函数优化那节，factorial中的factorial多打了个2，newFactorial(5) // 24这个也手误了，newFactorial函数用的也不是你链接中的curry，而是partial

[mqyqingfeng]

@SilenceZeng 非常感谢指出~ 已经修改，以后写文章的时候会更加严谨一些~

[scutuyu]

终于明白了尾递归，没白来

[gentlelius]

如下场景：

// 尾调用
function f(x){
    return g(x);
}

在chrome中跑了下，那个控制台 -> Sources -> Call Stack中观察到，f(x) 和g(x)都在stack中，并没有出现如下这种情况啊

// 伪代码
ECStack.push(<f> functionContext);

ECStack.pop();

ECStack.push(<g> functionContext);

ECStack.pop();

[jasonzhangdong]

@coderLius 怎么观察的，我怎么看不到？

[mqyqingfeng]

@coderLius 很抱歉之前没有看到这个问题，V8 并没有部署尾递归优化，所以其实从 Call Stack 中看不到期望的效果

[mqyqingfeng]

@jasonzhangdong 在这里

[qujsh]

看了你这张截图，然后试着把数据跑出来，看着数据的变化，感觉更能理解这儿的this，执行上下文了。
然后我的第一反应是，在js深入讲解的时候，你应该就把截图操作的放上去做下举例；第二反应是，涨姿势了，然后希望你能更多的简单讲解下（甚至只是一张截图），这些工具在你们手上是怎么发挥作用的。

[mqyqingfeng]

@qujsh 感谢建议~ 以后可以写一个工具系列~ 哈哈

[hazxy]

@mqyqingfeng 如果真的能够写一个算法系列，那真是大大的好啊！

[mqyqingfeng]

@hazxy 算法系列真是任重而道远呐~

[iiicon]

执行上下文栈和函数调用栈是一个东西吧

[Tan90Qian]

@mqyqingfeng V8 并没有部署尾递归优化那就是说，尾递归能否对性能有改进，取决于运行的平台、环境咯？那么是否会存在一些平台反而是常规的递归性能比尾递归更好呢？

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

function factorial2(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.time('尾递归');
factorial(10000, 1)
console.timeEnd('尾递归');

console.time('正常递归');
factorial2(10000)
console.timeEnd('正常递归');

在chrome下，尾递归的性能通常较好，偶尔性能劣于正常的递归；
在safari和firefox下，尾递归的性能通常较差，甚至在firefox下经常出现4、5倍的耗时差距；

[mqyqingfeng]

@Tan90Qian 代码写错了哈……

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

function factorial2(n) {
    if (n == 1) return n;
    // 这里应该是 factorial2
    return n * factorial2(n - 1)
}

console.time('尾递归');
factorial(10000, 1)
console.timeEnd('尾递归');

console.time('正常递归');
factorial2(10000)
console.timeEnd('正常递归');

[cikeyin]

@mqyqingfeng 你好！有个疑问：你在《JavaScript深入之执行上下文栈》 中举的这个例子不也是尾调用吗？为什么执行上下文栈的变化和本章的尾调用不同？

[xiaolan92]

@cikeyin 这不是尾递归,这是闭包.朋友,基础很重要啊!!!

[fundatou]

@cikeyin 按照我的理解，这两个地方执行栈都没问题。一个是没有用尾调优化的栈，一个是使用了尾调用优化的栈（现在实际在chrome下跑也暂时还看不到尾调用优化的结果）。可能之前博主在写执行上下文栈的时候更多的重心是在执行上下文栈这块，现在写递归就顺带写了执行栈的优化。

[iversonwool]

关于尾调用刚开始还以为作者说错了 所以又仔细看了看阮老师的http://es6.ruanyifeng.com/#docs/function#%E5%B0%BE%E8%B0%83%E7%94%A8%E4%BC%98%E5%8C%96
还有尾调用优化的问题 是否跟是否使用严格模式有关系

[xsfxtsxxr]

以前看阮一峰老师的ES6，看到尾调用这边云里雾里，后来看了冴羽大神写的执行环境栈运行原理，回过头看尾调用终于看懂了。
尾调用就是保证每次执行的时候，ECS里面只有一个函数执行上下文，这样在递归时候不会栈溢出。

[leonwens]

function f(x){ return g(x) + 1; }
我想问下为啥return g(x)和return g(x)+1，前者的执行上下文栈会先push再pop，后者就不会？

[yangtao2o]

尾递归学习总结：

// 求和
function sum(n, res = 0) {
  if (n < 1) return res;
  return sum(n - 1, n + res);
}
sum(5); // 15

// 斐波拉契数
function fibonacci(n, sum1 = 1, sum2 = 1) {
  if (n <= 2) return sum2;
  return fibonacci(n - 1, sum2, sum1 + sum2);
}
fibonacci(5); // 5

// 阶乘
function factorial(n, res = 1) {
  if (n <= 1) return res;
  return factorial(n - 1, n * res);
}

[conan1992]

function f(x){ return g(x) + 1; }
我想问下为啥return g(x)和return g(x)+1，前者的执行上下文栈会先push再pop，后者就不会？

ES6 的尾调用优化只在严格模式下开启，正常模式是无效的。博主讲的应该是在严格模式下

[puck1006]

function f(x){ return g(x) + 1; }
我想问下为啥return g(x)和return g(x)+1，前者的执行上下文栈会先push再pop，后者就不会？

return g(x) 的时候 f(x)已经结束了,所以f(x)push之后就pop了
return g(x)+1的时候. 因为return会返回计算结果. 所以先g(x)调用的返回值与1相加.那么就是f(x)push之后g(x)push紧接着g(x)调用完pop 再返回最终结果. f(x)也pop

[tancgo]

function f(x){
    return g(x);
}
// 非尾调用
function f(x){
    return g(x) + 1;
}

谁能帮我解释下这俩的执行上下文栈有啥区别么

[xsfxtsxxr]

@tancgo 我理解的出入栈如下：

// 尾调用
function f(x){
    return g(x);
}
ECS:[] -> gloabalContext入栈 -> fContext入栈 -> fContext出栈 -> gContext入栈 -> gContext出栈
// 非尾调用
function f(x){
    return g(x) + 1;
}
ECS:[] -> gloabalContext入栈 -> fContext入栈 -> gContext入栈 -> gContext出栈 -> fContext出栈

[ZhangXinmiao]

function f(x){
    return g(x);
}
// 非尾调用
function f(x){
    return g(x) + 1;
}

谁能帮我解释下这俩的执行上下文栈有啥区别么

@tancgo 可以看下这个文章开头部分的解释
https://es6.ruanyifeng.com/#docs/function#%E5%B0%BE%E8%B0%83%E7%94%A8%E4%BC%98%E5%8C%96

[iversonwool]

function f(x){
    return g(x);
}
// 非尾调用
function f(x){
    return g(x) + 1;
}

谁能帮我解释下这俩的执行上下文栈有啥区别么

@tancgo 可以看下这个文章开头部分的解释
https://es6.ruanyifeng.com/#docs/function#%E5%B0%BE%E8%B0%83%E7%94%A8%E4%BC%98%E5%8C%96

函数调用会产生调用栈 call stack，用于保存函数调用的一些信息，比如局部变量等。非尾调用g(x) + 1，需要留存住这个 + 1，但是尾调用g(x)，不需要保留任何信息，直接用当前call stack 取代之前call stack 节省了空间。言语很拙劣，不知道讲清楚了没，😂。

[PointerToNextPole]

关于尾递归，推荐一下文章：https://site.douban.com/196781/widget/notes/12161495/note/262014367/ 虽然有点老...
另外，文章中《数据结构与算法分析：C描述》中的尾递归的介绍在 3.3.3章节的最后（我这边的版本是 P61 ）

[lh2218431632]

个人感觉递归最重要的一点是，函数的名字要具有语义化

[badmanbadman]

补充几个小点，可能更加容易理解：
1、尾调用的概念：某个函数的 最后一步是调用另外一个函数，即成为尾调用。
2、尾调用优化： 当函数最后一步调用另外一个函数（fn1）时，函数（fn1）内部么没有对父层函数的的任何变量有所依赖，或者说所有的依赖的计算都是在父函数中完成的，这时执行这个函数（fn1）时，父函数的执行上下文会被从栈内弹出，从而实现栈内只有 函数（fn1）的执行上下文，

*按照我的理解，只有进行了尾调用优化的尾调用才算是有实践意义的 ‘尾调用’；
举例说明：
1、没有进行尾调用
大佬文章的函数执行上下文栈中的例子

在这个例子中函数最后一步的确是调用 另外一个函数，从概念意义上讲，它是一个尾调用，但是由于调用的这个函数仍然依赖父层函数的变量scope ，所有并不会进行尾调用优化，所以它并不能称之为 有实践意义的 ‘尾调用’（可以理解为就是大佬文中所描述的那样的出入栈规则，）
另外 有些浏览器不支持尾调用优化，如chrome