专栏首页AlbertYang的编程之路JavaScript进阶教程(6)—硬核动图让你轻松弄懂递归与深浅拷贝

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

一、递归

1.1 概念

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

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

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

f1();

1.2 出口

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

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

f1();

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

上边的这个小姐姐问第一个排队的人,有多少人排队,第一个人回答:我(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。

递归求斐波那契数列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()的算法如下:

递归求阶乘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>

二 深浅拷贝

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

2.1 浅拷贝

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

var obj1 = {
  age: 18,
  sex: "男",
  car: ["奔驰", "宝马", "特斯拉"]
};
// 另一个对象
var obj2 = {};

// 把一个对象的属性复制到另一个对象中,浅拷贝
// 把a对象中的所有的属性复制到对象b中
function extend(a, b) {
  for (var key in a) {
    b[key] = a[key];
  }
}
extend(obj1, obj2);
console.dir(obj2); // 开始的时候这个对象是空对象,复制之后有了obj1的属性
console.dir(obj1);

2.2 深拷贝

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

var obj1 = {
  age: 18,
  sex: "男",
  car: ["奔驰", "宝马", "特斯拉"],
  dog: {
    name: "欢欢",
    age: 3,
    color: "黑白相间"
  }
};

var obj2 = {}; //空对象
// 利用递归,把对象a中的所有的数据深拷贝到对象b中
function extend(a, b) {
  for (var key in a) {
    // 先获取a对象中每个属性的值
    var item = a[key];
    // 判断这个属性的值是不是数组
    if (item instanceof Array) {
      // 如果是数组,那么在b对象中添加一个新的属性,并且这个属性值也是数组
      b[key] = [];
      // 调用这个方法,把a对象中这个数组的属性值一个一个的复制到b对象的这个数组属性中
      extend(item, b[key]);
    } else if (item instanceof Object) { // 判断这个值是不是对象类型的
      // 如果是对象类型的,那么在b对象中添加一个属性,是一个空对象
      b[key] = {};
      // 再次调用这个方法,把a对象中的属性对象的值一个一个的复制到b对象的这个属性对象中
      extend(item, b[key]);
    } else {
      // 如果值是普通的数据直接复制到b对象的这个属性中
      b[key] = item;
    }
  }
}

extend(obj1, obj2);
console.dir(obj1);
console.dir(obj2);

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

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

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

var obj1 = {
  age: 18,
  sex: "男",
  car: ["奔驰", "宝马", "特斯拉"]
};
// 另一个对象
var obj2 = {};

// 把一个对象的属性复制到另一个对象中,浅拷贝
// 把a对象中的所有的属性复制到对象b中
function extend(a, b) {
  for (var key in a) {
    b[key] = a[key];
  }
}
extend(obj1, obj2);
obj1.car[0] = "五菱宏光"; // 改变obj1中的值obj2也会改变
console.log(obj1);
console.log(obj2);

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

var obj1 = {
  age: 18,
  sex: "男",
  car: ["奔驰", "宝马", "特斯拉"],
  dog: {
    name: "欢欢",
    age: 3,
    color: "黑白相间"
  }
};

var obj2 = {}; //空对象
// 通过函数实现,把对象a中的所有的数据深拷贝到对象b中
function extend(a, b) {
  for (var key in a) {
    // 先获取a对象中每个属性的值
    var item = a[key];
    // 判断这个属性的值是不是数组
    if (item instanceof Array) {
      // 如果是数组,那么在b对象中添加一个新的属性,并且这个属性值也是数组
      b[key] = [];
      // 调用这个方法,把a对象中这个数组的属性值一个一个的复制到b对象的这个数组属性中
      extend(item, b[key]);
    } else if (item instanceof Object) { // 判断这个值是不是对象类型的
      // 如果是对象类型的,那么在b对象中添加一个属性,是一个空对象
      b[key] = {};
      // 再次调用这个方法,把a对象中的属性对象的值一个一个的复制到b对象的这个属性对象中
      extend(item, b[key]);
    } else {
      // 如果值是普通的数据直接复制到b对象的这个属性中
      b[key] = item;
    }
  }
}

extend(obj1, obj2);
obj1.car[0] = "五菱宏光"; // 改变obj1中的值obj2不会改变
console.dir(obj1);
console.dir(obj2);

三 总结

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

本文分享自微信公众号 - AlbertYang(AlbertYang666),作者:AlbertYang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端进阶知识汇总

    年初突然有了个想法,前端也做了几年了,但是很多知识还很零散,应该系统的把知识归纳起来,于是给自己制定了一个计划,决定花大半年的时间整理一下大前端的知识,把他们都...

    蒋鹏飞
  • 每个JavaScript工程师都应懂的33个概念

    这个项目是为了帮助开发者掌握 JavaScript 概念而创立的。它不是必备,但在未来学习(JavaScript)中,可以作为一篇指南。

    Fundebug
  • 每个JavaScript工程师都应懂的33个概念

    这个项目是为了帮助开发者掌握 JavaScript 概念而创立的。它不是必备,但在未来学习(JavaScript)中,可以作为一篇指南。

    Fundebug
  • 面试题被问到再也不慌,深究JavaScript中的深拷贝与浅拷贝

    JavaScript中的深拷贝和浅拷贝是前端面试中频繁被问到的一道题, 于是我也自己去查阅了一些资料, 然后动手敲了代码测试了一下。那么我就用我的理解,给大家来...

    @零一
  • 【每周三面】2019前端面试系列——JS面试题

    可以判断出\'string\',\'number\',\'boolean\',\'undefined\',\'symbol\' 但判断 typeof(null)...

    趣学程序-shaofeer
  • 图解 Python 浅拷贝与深拷贝

    从字面上看,上述语句创建了变量 lst 和 new_list,并且 lst 和 new_list 的赋值都为一个列表。但是,Python 的赋值语句并不会复制对...

    lyhue1991
  • javascript基础修炼(8)——指向FP世界的箭头函数

    箭头函数是ES6语法中加入的新特性,而它也是许多开发者对ES6仅有的了解,每当面试里被问到关于“ES6里添加了哪些新特性?”这种问题的时候,几乎总是会拿箭头函数...

    大史不说话
  • 这里有 300 篇 Python 与机器学习类原创笔记

    主要包括计算机科学中基本的算法与数据结构,结合算法思想和Leetcode实战,总结介绍。

    好好学java
  • 阿里巴巴内推一面过程

    一面是有个人给我打的电话跟我约了一个面试时间,他们人真的很好,是按你的时间来,如果有事就可以往后延。然后我约了今天晚上7点半,于是就开始了我的一面,我面完试赶紧...

    @零一
  • Python中浅拷贝与深拷贝

    Python中的赋值语句没有创建副本对于对象来说,它们只是将名称绑定到对象。对于不可变的对象来说,通常是没有什么区别的。但是,为了处理可变对象或...

    Python知识大全
  • JavaScript中的拷贝(copy)

    如果现有var obj1 = {…}这个对象,想要复制对象obj1,一贯的做法就是obj2 = obj1,这时虽然obj2拥有了obj1的所有属性,但obj2却...

    刘亦枫
  • 创始人退休后的Python,起飞还是没落?

    今日Python 之父 Guido Van Rossum宣布退休的消息占据了多家科技媒体的版面。

    博文视点Broadview
  • 学习Python一年,这次终于弄懂了浅拷贝和深拷贝

    话说,网上已经有很多关于Python浅拷贝和深拷贝的文章了,不过好多文章看起来还是决定似懂非懂,所以决定用自己的理解来写出这样一篇文章。

    宇宙之一粟
  • 前端面试题库系列(4)

    defer 是“渲染完再执行”,async 是“下载完就执行”,defer 如果有多个脚本,会按照在页面中出现的顺序加载,多个async 脚本不能保证加载顺...

    李才哥
  • 记一次前端大厂面试

    链接:https://juejin.im/post/5b9770056fb9a05d2f3692ce

    闰土大叔
  • 我遇到的前端面试题分享

    前端安全问题主要有XSS、CSRF攻击 XSS:跨站脚本攻击 它允许用户将恶意代码植入到提供给其他用户使用的页面中,可以简单的理解为一种javascript代码...

    疯狂的技术宅
  • Array.from() 五个超好用的用途

    任何一种编程语言都具有超出基本用法的功能,它得益于成功的设计和试图去解决广泛问题。

    前端达人
  • 已阅冴羽大佬文章

    https://juejin.cn/post/6958361473953300488

    达达前端
  • 2019 最新 Java 核心技术教程,都在这了!

    以下是Java技术栈微信公众号发布的所有关于 Java 的技术干货,会从以下几个方面汇总,本文会长期更新。

    Java技术栈

扫码关注云+社区

领取腾讯云代金券