JavaScript进阶教程(6)—硬核动图让你轻松弄懂递归与深浅拷贝

港控/mmm° 2022-12-06 12:59 104阅读 0赞

**目录**

一、递归

1.1 概念

1.2 出口

1.3 递归经典问题：递归求斐波那契数列

1.4 递归经典问题：递归求阶乘

1.5 递归求一个数字各个位数上的数字的和

1.6 递归遍历DOM树

二 深浅拷贝

2.1 浅拷贝

2.2 深拷贝

2.3 如何区分深拷贝与浅拷贝？

2.3.1 浅拷贝：仅复制了引用，彼此之间的操作会互相影响

2.3.2 深拷贝：在堆中重新分配内存，不同的地址，互不影响

三 总结

--------------------

# **一、递归** #

## **1.1 概念** ##

递归简单的来说就是程序自己调用自己，就像下面这幅图一样，一直循环往复。就像我们经常听到的小和尚的故事，从前有座山，山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚讲故事，故事内容是：从前有座山，山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚讲故事，故事内容是：从前有座山，山里有座庙，庙里......

![format_png][]

JavaScript的递归就是在函数中调用函数自己。

// 递归:函数中调用函数自己
    function f1() {
    	console.log("从前有座山，山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚讲故事，故事内容是：");
    	f1();
    }
    
    f1();

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70][]

## **1.2 出口** ##

如果程序一直这样循环往复的调用自己，一直都不结束，就是一个死循环，这没什么意义。所以我们需要为递归定义一个结束条件，即递归的出口，当条件不满足时，递归一直前进，不断地调用自己；当边界条件满足时，递归返回。

// 递归的结束条件为i大于5
    var i = 0;
    
    function f1() {
    	i++;
    	if (i > 5) {
    		return;
    	}
    	console.log("从前有座山，山里有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚讲故事，故事内容是：");
    	f1();
    }
    
    f1();

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 1][]

递归的应用通常是把一个大型的比较复杂的问题，通过层层转化为一个与原问题相似的小的问题来求解，就像下边统计排队人数的问题。

![format_png 1][]

上边的这个小姐姐问第一个排队的人，有多少人排队，第一个人回答：我(1个人)+后边的人，小姐姐没有得到具体的答案，但是她知道只要弄清楚第一个人后边有多少人排队+第一个人就是排队的人数，所以她继续问后边的人，结果得到了相同的回答，于是她得到的答案变成了：1+1+后边的人。于是她不得不一直这样问下去，等到问到最后一个人的时候，最后一个人回答，就我一个人，到此刻小姐姐终于得到了想要的答案即：1+1+········+1。上边就是一个经典的递归的例子，这里的递归结束条件为是否是最后一个人，只要不是最后一个人，就一直问下去。

## **1.3 递归经典问题：递归求斐波那契数列** ##

斐波那契数列（Fibonacci sequence），又称黄金分割数列、指的是这样的数列：0、1、1、2、3、5、8、13、21、34、……，从第三项开始，这个数列每一项都等于前两项之和。在数学上，斐波那契数列被以递推的方法定义：F(0)=0,F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）。下面的动图描述了如何用递归的方式来求斐波那契数列的第8项，即F(7)。根据定义F(7)=F(6)+F(5),求F(7)只需要知道F(6)和F(5)即可，而F(6)=F(5)+F(4),F(5)=F(4)+F(3).......依次类推，因为F(0)=0,F(1)=1是已知的，所以到第一项和第二项的时候就可以结束了，即递归的结束条件是n=0或n=1。

![format_png 2][]

**递归求斐波那契数列JS代码实现:**

// 递归:求斐波那契数列
    function getFib(x) {
    	if (x == 0) {
    		return 0
    	} else if (x == 1) {
    		return 1
    	}
    	return getFib(x - 1) + getFib(x - 2);
    }
    console.log(getFib(7)); // >13

## **1.4 递归经典问题：递归求阶乘** ##

n的阶乘，就是从1开始乘到n，即1\*2\*3\*...\*(n-1)\*n，即n!=1\*2\*3\*...\*(n-1)\*n=n\*(n-1)!，而(n-1)!=1\*2\*3\*...\*(n-1)=(n-1)\*(n-2)!，......依次类推当n=1时，1！=1\*0！=1，即递归的结束条件为1，由此，可以得出递归求阶乘函数factorial()的算法如下：

![format_png 3][]

**递归求阶乘JS代码实现：**

// 递归案例:求5的阶乘
    function factorial(x) {
    	if (x == 1) {
    		return 1
    	}
    	return x * factorial(x - 1);
    }
    console.log(factorial(5)); // >120

## **1.5 递归求一个数字各个位数上的数字的和** ##

// 递归案例:求一个数字各个位数上的数字的和:  123--->1+2+3=6                   
    function getEverySum(x) {
    	if (x < 10) {
    		return x;
    	}
    	// 获取的是这个数字的个位数
    	return x % 10 + getEverySum(parseInt(x / 10));
    }
    console.log(getEverySum(123)); // >6

## **1.6 递归遍历DOM树** ##

<!DOCTYPE html>
    <html lang="en">
            <head>
                    <meta charset="UTF-8">
                    <title>递归遍历DOM树:公众号AlbertYang</title>
            </head>
    
            <body>
                    <h1>遍历 DOM 树</h1>
                    <div>
                            <ul>
                                    <li>123</li>
                                    <li>456</li>
                                    <li>789</li>
                            </ul>
                            <div>
                                    <div>
                                            <span>haha</span>
                                    </div>
                            </div>
                    </div>
                    <div id="demo_node">
                            <ul>
                                    <li>123</li>
                            </ul>
                            <p>hello</p>
                            <h2>world</h2>
                            <div>
                                    <p>dsa</p>
                                    <h3>
                                            <span>dsads</span>
                                    </h3>
                            </div>
                    </div>
    
            </body>
            <script>
                    // 获取页面中的根节点---根标签
                    var root = document.documentElement; // html
                    // 函数遍历DOM树
                    function forDOM(root1) {
                            // 获取根节点中所有的子节点
                            var children = root1.children;
                            // 调用遍历所有子节点的函数
                            forChildren(children);
                    }
                    // 把这个子节点中的所有的子节点显示出来
                    function forChildren(children) {
                            // 遍历所有的子节点
                            for (var i = 0; i < children.length; i++) {
                                    // 每个子节点
                                    var child = children[i];
                                    // 显示每个子节点的名字
                                    f1(child);
                                    //  判断child下面有没有子节点,如果还有子节点,那么就继续的遍历
                                    child.children && forDOM(child);
                            }
                    }
                    //函数调用,传入根节点
                    forDOM(root);
    
                    function f1(node) {
                            console.log("节点的名字:" + node.nodeName);
                    }
            </script></html>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 2][]

# **二 深浅拷贝** #

在JS中的数据类型可分为两种：基本类型和引用类型。基本类型有undefined,null,Boolean,String,Number,Symbol等，引用类型有Object,Array,Date,Function,RegExp等。基本类型值在内存中占据固定大小，保存在栈内存中，引用类型的值是对象，保存在堆内存中，而栈内存储的是对象的变量标识符和对象在堆内存中的存储地址。不同类型的复制方式是不同的。对于基本类型，从一个变量向另外一个新变量复制基本类型的值，会创建这个值的一个副本，并将该副本复制给新变量。对于引用类型，从一个变量向另一个新变量复制引用类型的值，其实复制的是指针，最终两个变量都指向同一个对象。

## 2.1 浅拷贝 ##

浅拷贝就是直接复制，相当于把一个对象中的所有的内容，复制一份给另一个对象，对于基本类型复制的是具体的值的副本，对于引用类型复制的是指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 4][]

## **2.2 深拷贝** ##

深拷贝还是复制，对于基本类型复制的是具体的值的副本，对于引用类型会找到对象中具体的属性或者方法，并且开辟新的相应的空间，一个一个的复制到另一个对象中，在这个过程中需要使用递归。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 6][]

## **2.3 如何区分深拷贝与浅拷贝？** ##

假设B复制了A，当修改A时，看B是否会发生改变，如果B发生了改变，说明是浅拷贝，如果B没有变，说明是深拷贝。浅拷贝中B复制的是A的引用，深拷贝中，B复制的是A的本体。上边浅拷贝和深拷贝的代码中，对于基本类型的值都是深拷贝，而对于引用类型值，浅拷贝复制的是引用，深拷贝复制的是具体的本体对象。

### 2.3.1 浅拷贝：仅复制了引用，彼此之间的操作会互相影响 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 7][]

### **2.3.2 深拷贝：在堆中重新分配内存，不同的地址，互不影响** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 8][]

# **三 总结** #

递归就是函数中调用函数自己，递归一定要有结束的条件，否则就是死循环。递归的应用通常是把一个大型的比较复杂的问题，通过层层转化为一个与原问题相似的小的问题来求解。在JS中递归一般应用到深拷贝，菜单树，遍历DOM等操作上，递归效率很低，所以轻易不要使用递归。

今天的学习就到这里了，由于本人能力和知识有限，如果有写的不对的地方，还请各位大佬批评指正。**如果想继续学习提高，欢迎关注我，每天学习进步一点点，就是领先的开始。如果觉得本文对你有帮助的话，欢迎转发，评论，点赞！！！**

[format_png]: /images/20221123/83ba1288910440c0906e83173d46b45c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70]: /images/20221123/7844b1f653594d17ab27e06d07561250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 1]: /images/20221123/b2555e762729420284b0acef09668ab5.png
[format_png 1]: /images/20221123/d392090f55814110a3e55e0bfbb8f414.png
[format_png 2]: /images/20221123/9d10165044874185b616dcf2d606ad9b.png
[format_png 3]: /images/20221123/9e3abc19a09e48f2a6fd8d09554b7bcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 2]: /images/20221123/451ff4eb536a48599cb6644fa59593c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 3]: /images/20221123/d1116f001a434c5280ab5d682aa4340e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 4]: /images/20221123/904d772f417442148e8836a3d4cc4228.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 5]: /images/20221123/5b2ef0d7064e4c19907781feea3cca62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 6]: /images/20221123/43710e87417f47a3b29baa0732094c95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 7]: /images/20221123/8e05754e68334b139a6970dc4b2c9be0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzODUzNzQz_size_16_color_FFFFFF_t_70 8]: /images/20221123/260f4ec7cb2d425a9f233abf022b1c29.png