# 深入 JS 递归、深浅克隆
# 1、谈谈你对递归的简单理解 ?
以下图片:
- 画的一双手在画画,他画的是正在画画的双手 ....
- 每一次画作都跟前一次是相同的,形成了层层的嵌套,就越来越小
- 并且,嵌套的内容就是它本身,在 JS 中就称之为 递归
# 2、对递归的深入理解和定义
定义
- 函数的内部语句可以调用这个函数自身,从而发起对函数的一次迭代
- 在新的迭代中,又会执行调用函数自身的语句,从而又产生一次迭代
- 当函数执行到某一次时,不再进行新的迭代,函数被一层一层返回,函数被递归。
- 递归是一种较为 高级的编程技巧,它把一个大型复杂的问题,层层转化为一个与原问题相似的,但规模较小的问题来求解。
# 3、举例说明,什么是递归 ?
使用 5 的阶乘来举例,了解什么是递归?
- 边界条件:确定递归到何时终止,也称之为递归出口
- 递归模式:大问题是如何分解为小问题的,也称为递归体
# 4、书写一个函数
这个函数内部自己会调用自己,从而形成递归
function factorial(n) {
// 函数的功能是计算n的阶乘,n的阶乘是 n*(n-1)的阶乘
// n! = n * (n-1)!
if (n == 1) return 1;
// 如果询问的不是1的阶乘,就返回 n * (n-1)
return n * factorial(n - 1);
// 三目运算符
// return n == 1 ? 1 : n * factorial(n - 1);
}
// 调用函数
var result = factorial(5);
// 输出结果
console.log(result);
递归,简单理解就是函数内部调用函数自身,达到某个条件之后,停止调用。
# 5、递归常规算法题
斐波那契数列
- 数列:1、1、2、3、5、8、13、21 你找到规律了吗 ?
- 规律:数列下标为 0 和 1 的项的值都是 1,从下标为 2 的项开始,每项等于前面两项的和
// 编写一个函数,这个函数的功能是返回斐波那契数列中下标为n的那项的值
function fib(n) {
// 数列的下标为0的项和下标为1的项值是1
if (n == 0 || n == 1) return 1;
// 斐波那契数列的本质特征就是每一项,等于前面两项的和
return fib(n - 1) + fib(n - 2);
}
// 书写一个循环语句,计算斐波那契数列的前15项
for (var i = 0; i < 15; i++) {
console.log(fib(i));
}
# 输出结果:
# 6、实现浅克隆
TIP
- 使用
var arr2 = arr1
这样的语句不能实现数组的克隆 - 浅克隆:准备一个空的结果数组,然后使用 for 循环遍历原数组,将遍历到的项都推入结果数组
- 浅克隆只克隆数组的一层,如果数组是多维数组,则克隆的项会 "藕断丝连"
// 通过以下方式实现浅克隆
// 准备原数组
var arr1 = [22, 33, 55, 11, 66, [77, 88, 99]];
// 准备一个结果数组
var result = [];
// 遍历原数组,将遍历到的项都推入到结果数组中
for (var i = 0; i < arr1.length; i++) {
result.push(arr1[i]);
}
// 输出结果数组
console.log(result); // [22, 33, 55, 11, 66]
// 测试是否实现了浅克隆,就是说本质上是内存中的不同数组了
console.log(arr1 == result); // false
// arr1.push(88);
// console.log(result); // result数组是不会受影响的,因为它们被分开了
// 测试这样的克隆是浅克隆,"藕断丝连"
arr1[5].push(100);
console.log(result); // [22, 33, 55, 11, 66, [77, 88, 99, 100]]
# 7、使用递归实现深克隆
TIP
使用 递归思想,整体思路和浅克隆类似,但稍微进行一些改动:
- 如果遍历到项是基本类型值,则直接推入结果数组;
- 如果遍历到的项是又是数组,则重复执行浅克隆的操作。
// 原数组
var arr1 = [22, 11, 33, 55, [88, 66, [97, 61], 99]];
// 函数,这个函数会被递归(暂时不考虑对象,等以后学习了再讲)
function deepClone(arr) {
// 结果数组,”每一层“ 都有一个结果数组
var result = [];
// 遍历数组的每一项
for (var i = 0; i < arr.length; i++) {
// 类型判断,如果遍历到的项是数组
if (Array.isArray(arr[i])) {
// 递归
result.push(deepClone(arr[i]));
} else {
// 如果遍历到项不是数组,是基本类型值,就直接推入到结果数组中
// 相当于是递归的出口
result.push(arr[i]);
}
}
// 返回结果数组
return result;
}
// 测试一下
var arr2 = deepClone(arr1);
console.log(arr2);
// 测试是否藕断丝连
console.log(arr1[4] == arr2[4]); // false
arr1[4].push(88888);
console.log(arr2); // 数组的项么有被改变,深克隆成功
// 再测试
console.log(arr1[4][2] == arr2[4][2]);
arr1[4][2].push(56789);
console.log(arr1); // arr1被推入
console.log(arr2); // arr2 没有被推入,深克隆成功
大厂最新技术学习分享群
微信扫一扫进群,获取资料
X