导航

HTML

CSS

JavaScript

浏览器 & 网络

版本管理

框架

构建工具

TypeScript

性能优化

软实力

算法

UI、组件库

Node

冷门技能

对递归的深入理解和定义

定义

• 函数的内部语句可以调用这个函数自身，从而发起对函数的一次迭代
• 在新的迭代中，又会执行调用函数自身的语句，从而又产生一次迭代
• 当函数执行到某一次时，不再进行新的迭代，函数被一层一层返回，函数被递归。
• 递归是一种较为 高级的编程技巧，它把一个大型复杂的问题，层层转化为一个与原问题相似的，但规模较小的问题来求解。

举例说明，什么是递归 ？

使用 5 的阶乘来举例，了解什么是递归？

• 边界条件：确定递归到何时终止，也称之为递归出口
• 递归模式：大问题是如何分解为小问题的，也称为递归体

书写一个函数

这个函数内部自己会调用自己，从而形成递归

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);

递归，简单理解就是函数内部调用函数自身，达到某个条件之后，停止调用。

递归常规算法题

斐波那契数列

• 数列：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));
}

输出结果：

实现浅克隆

• 使用 var arr2 = arr1 这样的语句不能实现数组的克隆
• 浅克隆：准备一个空的结果数组，然后使用 for 循环遍历原数组，将遍历到的项都推入结果数组
• 浅克隆只克隆数组的一层，如果数组是多维数组，则克隆的项会 "藕断丝连"

// 通过以下方式实现浅克隆
// 准备原数组
let arr1 = [22, 33, 55, 11, 66, [77, 88, 99]];
// 准备一个结果数组
let result = [];

// 遍历原数组，将遍历到的项都推入到结果数组中
for (let 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]]

使用递归实现深克隆

使用 递归思想，整体思路和浅克隆类似，但稍微进行一些改动：

• 如果遍历到项是基本类型值，则直接推入结果数组；
• 如果遍历到的项是又是数组，则重复执行浅克隆的操作。

// 原数组
let arr1 = [22, 11, 33, 55, [88, 66, [97, 61], 99]];

// 函数，这个函数会被递归（暂时不考虑对象，等以后学习了再讲）
function deepClone(arr) {
  // 结果数组，”每一层“ 都有一个结果数组
  var result = [];
  // 遍历数组的每一项
  for (let i = 0; i < arr.length; i++) {
    // 类型判断，如果遍历到的项是数组
    if (Array.isArray(arr[i])) {
      // 递归
      result.push(deepClone(arr[i]));
    } else {
      // 如果遍历到项不是数组，是基本类型值，就直接推入到结果数组中
      // 相当于是递归的出口
      result.push(arr[i]);
    }
  }
  // 返回结果数组
  return result;
}

// 测试一下
let 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 没有被推入，深克隆成功