JavaScript基础篇-递归 #4

lzlu · 2018-03-31T07:41:05Z

JavaScript基础篇-递归

第一次写博客，文笔尚有些稚嫩之处，如果发现文中有任何不严谨或者不正确的地方，欢迎批评指正！

递归或者叫递归算法是编程里面十分重要的概念，解决很多实际工作中很多编程问题。

什么是递归

什么是递归，搜索一波，发现Google非常皮。

简单的说，递归就是在方法里面直接或者间接调用自己，当然不能无限制地去调用，递归需要有出口，否则会形成死循环，导致内存溢出。

递归的原理

先来看下阶乘，阶乘是递归的一个经典例子。相信大家高中都学过阶乘，比如6! = 1 * 2 * 3 * 4 * 5 * 6，用程序描述这个问题，实现一个factorial函数，输入n，输出n*(n-1)…21。仔细观察下，factorial(6)是 6 * factorial(5)，6 * 5 * factorial(4)… 6 * 5 * 4 * 3 * 2 * factorial(1)即6 * 5 * 4 * 3 * 2 * 1

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

上面代码的意思是当n不等于1的时候循环调用自己和传入的n相乘，n等于1，则返回1。
简单说下递归的原理，我们知道在JS中函数调用是一个叫的调用栈（Call Stack）实现的。比如传入n为5的时候，第一次执行factorial，当执行到factorial(n-1)，factorial会被压到栈中。递归方法的出入栈和其他普通方法唯一的区别是前者调用了自己。我们把每次调用的factorial已调用顺序命名下。当运行到n===1的时候，栈里依次存放则factorial1, factorial2, factorial3, factorial4, factorial5。
当factorial5被执行的时候，n是1，返回1,推出栈。当factorial4被调用的时候，n是2，返回2 * 1。接下去factorial3, factorial2依次被调用出栈，返回3 * 2和4 * 6，最后一个factorial1的时候，计算5 * 24，结束运行。

斐波那契数列

斐波那契数列是递归另一个经典的例子，这是个叫斐波那契的意大利人在数兔子的时候观察归纳出的一个数列。

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……]

即如果n是a,n+1是b，那么n+2一定是a+b。比如运行Fibonacci(6)，返回斐波那契数列第6个元素8。

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

递归使用技巧

根据上面的例子，总结下：

抽象问题，抽离出一个描述问题的子方法，这也是寻找循环体的一个过程。
寻找边界值。递归是有边界的，这结束递归的条件，当不满足边界的时候，继续递归下去；满足递归边界就结束递归返回。
下面介绍几个实际应用场景。

递归应用

树状菜单

树状菜单是比较常见的组件，一般后端数据都是二维扁平存储的，前端拿到数据后需要解析展开一下

let arr = [
    { id: 0, },
    { id: 1, parentId: 0, },
    { id: 2, parentId: 0, },
    { id: 3, parentId: 1, },
    { id: 4, parentId: 1, },
]

把上面的数组，展开成下面的格式。根据parentId放入对应id对象的children节点上。

let after = {
　　"id":0,
　　"children":[
　　　　{
　　　　　　"id":1,
　　　　　　"parentId":0,
　　　　　　"children":[
　　　　　　　　{
　　　　　　　　　　"id":3,
　　　　　　　　　　"parentId":1
　　　　　　　　}
　　　　　　]
　　　　}
　　]
}

我们先寻找一个基本的操作，叫find(), 这个函数用来遍历arr，如果发现数组里面的对象el的parentId等于当前对象的id，则把这个值放到当前对象result的children数组里面，这个时候，el也可能是别人的parent，所以我们需要继续寻找数组里面是否有parentId等于el的id，继续find下去。
这个递归函数的隐含的边界条件其实是el.parentId === result.id，如果相等则继续递归下去，一直到找不到相等为止。

const find = (result, arr) => {
    arr.forEach((el) => {
        if (el.parentId === result.id) {
            //设置默认值
           	result.children = result.children || [];
           	result.children.push(el);
				find(el, arr);
        }
    });
};
//设置入口函数
const arrToTree = (arr) => {
    let result = {
        id: 0
    };
    find(result, arr);
    return result;
}
console.log(JSON.stringify(arrToTree(arr))); //'{"id":0,"children":[{"id":1,"parentId":0}]}'

优化下find函数，每次都遍历整个数组，会显得很浪费，把已经符合条件的对象从当前数组删除。数组为空则直接返回。

const find = (result, arr) => {
    //如果arr的长度是0，则终止递归。
    if(arr.length === 0) return;
    arr.forEach((el) => {
        if (el.parentId === result.id) {
            //设置默认值
            result.children = result.children || [];
            result.children.push(el);
            //删除数组指定内容
            arr.splice(arr.indexOf(el),<
8000
/span> 1);
            //继续递归子集
            find(el, arr);
        }
    });
};
const arrToTree = (arr) => {
    let result = {
        id: 0
    };
	   //为了不影响源数组，需要复制一份。
    find(result, Array.from(arr));
    return result;
}

比较两个JS对象是否相等

首先我们来重新定义下相等。

NaN和NaN是相等的，在js里面就算使用===号也是不相等的。
-0和+0是不相等的。
[1]和[1]、{value: 1}和{value: 1}是相等的，即相同内容的数组和对象是相等的。 
前面两种情况可以是用ES6新增的Object.is处理，第三种情况需要遍历数组/对象的每个key对应的value是否相等。为了方便对比，我们抽象出两个函数，eq和deepEq。eq主要判断原始类型的相等，deepEq则是遍历引用对象进行对比。这里的递归并未直接调用原函数，而是间接调用，eq调用deepEq，deepEq又调用eq。

对于deepEq，我们需要做一下判断

如果类型不一样，则返回false。
数组类型，判断长度是否相等，不相等返回false。相等，则继续遍历判断数组的每个元素是否相等，为了判断，我们需要用eq进行递归，因为数组的元素可能是对象也可能是数组或者普通的值。
对象类型，如果target的key不在source里面，返回false。如果二个value不相等则返回flase。

const eq = (target, source) => {
//判断是否是原始类型
    if (isPrimitive(target)) {
        if (Object.is(target, source)) return true;
        else return false;
    } 
//递归引用对象
    return deepEq(target, source);
};
const deepEq = (target, source) => {
//如果类型不一样就认为不相等返回false
    if (type(target) !== type(source)) return false;
    if (isArray(target)) {
//数组长度不一样就返回false
        if (target.length !== source.length) return false;
        let len = target.length;
        while(len --){
//遍历每个数组元素是否相等
            if(!eq(target[len], source[len])) return false;
        }
    }
    if (isObject(target)) {
        let keys = Object.keys(target),
            len = keys.length;
        while (len--) {
            let key = keys[len];
//如果target的key不在source里面就返回false
            if (isUndefined(source[key])) return false;
            if (!eq(target[key], source[key])) return false;
        }
    }
//通过上述验证则返回true
    return true;
};

代码还引用了一个Type.js，用来做类型判断。具体代码会贴在这里方便大家查看。
这里只是对递归思想进行解释，更多实现细节可以参考这篇JavaScript专题之如何判断两个对象相等 · Issue #41 · mqyqingfeng/Blog · GitHub

对象深拷贝

深拷贝具体细节可以参考我写得这篇浅析JS的拷贝。这里只对递归做解释。
深拷贝是值对js的基本类型做复制操作（=），遇到引用类型，需要继续递归下去。
1. 深拷贝的基本操作是复制原始类型(String，Number，Undefined，Null，Boolean，Symbol)。
2. 边界条件是值是否是引用类型，如果是，则继续递归下去。

...
const baseMerge = function(target, source) {
    for (let key in source) {
        if (source.hasOwnProperty(key)) {
            //如果是object或者array递归下去

            if (isPlainObject(source[key]) || isArray(source[key])) {
					...
					//引用类型继续递归
                baseMerge(target[key], source[key]);
            } else if(source[key] !== void 0){
					//原始类型则复制。
                target[key] = source[key];
            }
        }
    }
    return target;
};
...

尾调用优化

递归虽然能用比较简洁的方式解决问题，但递归的运行效率比较低，原因在用递归同时调用栈保存了成百上千个调用帧，容易发生堆栈溢出的错误。

调用栈的工作机制：调用函数的时候，会被推到调用栈的顶部，而执行完毕之后，就会从调用栈移除。

上文提到的阶乘函数。通过debugger发现调用到n为1的时候，Call Stack[调用栈]会有5个factorial函数调用帧。

使用尾调用可以解决这个问题的，尾调用就是指某个函数的最后一步是调用另一个函数。

function foo(x){
    return bar(x);
}

下面这三种情况都不属于尾调用。

// 情况一
function foo(x){
  let y = bar(x);
  return y;
}

// 情况二
function foo(x){
  return bar(x) + 1;
}

// 情况三
function foo(x){
  bar(x);
}

当然尾调用不一样要在函数的尾部，只要是最后一步操作即可（return）。
改写下之前的factorial函数，

const factorial = (n, m=1) => {
    if(n === 1){
        return m*1;
    }
    return factorial(n-1, m*n);
}

尾递归只在严格模式生效，class module也会生效，因为class module内部默认是严格模式。
尾部调用是函数最后一步操作，而不需要保留外部函数的调用帧，因此只存在一个调用帧。
在实际chrome上跑代码的时候，发现并没有生效，因为支持度非常感人，一片飘红。各大浏览器（除了safari）并未部署尾调用优化。

原因是在尾调用的实现中，许多调用帧被抛弃，导致很难在调试栈中调试代码。
T39又提出一种语义上的尾调用方案Syntactic Tail Calls。用明确的语义来标识需要尾调用优化的场景。比如

function foo1() { return continue bar(); }

小结

递归算法的内容远远不止这些，如二叉树查找，汉诺塔问题，能力有限，只能暂时介绍到这里了。

参考
http://imweb.io/topic/5a244260a192c3b460fce275
http://imweb.io/topic/584d33049be501ba17b10aaf
mqyqingfeng/Blog#41
https://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/
https://zhuanlan.zhihu.com/p/25644447
https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/
https://juejin.im/post/5a35e7c26fb9a0452341f70c#heading-6

joe223 · 2018-04-03T05:39:25Z

我觉得 Tail calls 可以再开一篇

lzlu · 2018-04-03T06:28:33Z

@joe223 我在补充下，写得有点简单

joe223 · 2018-04-03T15:49:36Z

@Expelliarmus923 期待续集

mqyqingfeng · 2018-04-24T12:51:14Z

给作者一个大大的赞 😀 ~

lzlu · 2018-04-27T02:37:25Z

@mqyqingfeng 谢谢大佬！

Pentium286 · 2020-06-10T13:56:36Z

作者大大，几个图片都无法浏览了

lzlu · 2020-06-24T02:23:00Z

@qianzhangsheng 图片备份丢了，我还在想办法

lzlu self-assigned this Mar 31, 2018

lzlu added the JavaScript label Mar 31, 2018

lzlu changed the title ~~写好一个递归~~ JavaScript基础篇-递归 Apr 2, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

JavaScript基础篇-递归 #4

JavaScript基础篇-递归 #4

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

JavaScript基础篇-递归 #4

JavaScript基础篇-递归 #4

Comments

Uh oh!

JavaScript基础篇-递归

什么是递归

递归的原理

斐波那契数列

递归使用技巧

递归应用

树状菜单

比较两个JS对象是否相等

对象深拷贝

尾调用优化

小结

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!