拷贝与递归

拷贝

在 JavaScript 中，"拷贝"通常指的是复制一个变量的值。根据变量的数据类型，拷贝可以分为两种类型：浅拷贝（Shallow Copy）和深拷贝（Deep Copy）。

浅拷贝（Shallow Copy）

浅拷贝只复制对象的第一层属性。如果对象的属性值是基本数据类型（如 String, Number, Boolean, null, undefined, Symbol），则拷贝的是值本身。如果属性值是复合数据类型（如对象或数组），则拷贝的是引用。

例如，你可以使用Object.assign()方法或展开运算符（...）来创建一个对象的浅拷贝：

let original = { a: 1, b: { c: 2 } };
let copy = Object.assign({}, original);
let spreadCopy = { ...original };

original.a = 3;
original.b.c = 4;

console.log(copy); // { a: 1, b: { c: 4 } }
console.log(spreadCopy); // { a: 1, b: { c: 4 } }

在这个例子中，修改original对象的a属性不会影响拷贝，因为它是一个基本数据类型的值。但是修改original对象的b.c属性会影响拷贝，因为b是一个对象，而浅拷贝只复制了对象的引用。

实现浅拷贝

1. 使用数组方法：

   • slice()：返回一个新的数组对象，是一个由开始到结束（不包括结束）选择的浅拷贝。
   • concat()：用于合并两个或多个数组，如果只用一个数组调用它，就会返回这个数组的浅拷贝。

   let original = [1, 2, 3];
   let shallowCopy1 = original.slice();
   let shallowCopy2 = original.concat();

2. 使用展开运算符（Spread Operator）：

   • 展开运算符...可以用来创建数组的浅拷贝。

   let original = [1, 2, 3];
   let shallowCopy = [...original];

3. 使用Array.from()方法：

   • 创建一个新数组实例，从一个类似数组或可迭代的对象中拷贝其元素。

   let original = [1, 2, 3];
   let shallowCopy = Array.from(original);

浅拷贝只复制数组的第一层元素，对于数组中的对象或数组等引用类型，浅拷贝只会复制它们的引用，而不是值。

深拷贝（Deep Copy）

深拷贝复制对象的所有层级。不管是基本数据类型的值还是复合数据类型，深拷贝都会创建一个新的实例。

在 JavaScript 中，可以使用JSON.parse()和JSON.stringify()来实现一个简单对象的深拷贝：

let original = { a: 1, b: { c: 2 } };
let deepCopy = JSON.parse(JSON.stringify(original));

original.a = 3;
original.b.c = 4;

console.log(deepCopy); // { a: 1, b: { c: 2 } }

在这个例子中，修改original对象的任何属性都不会影响深拷贝，因为深拷贝创建了完全独立的副本。

但是要注意，使用JSON.parse(JSON.stringify())方法进行深拷贝有一些局限性：

• 它不能复制函数。
• 它不能复制引用自身的对象（循环引用）。
• 它不能复制特殊的对象，如Map, Set, RegExp, Date等，这些对象会丢失或者不会按预期方式被复制。

对于复杂的对象或包含以上特殊情况的对象，你可能需要使用库（如 lodash 的_.cloneDeep方法）或者自己编写函数来实现深拷贝。

实现 JavaScript 中的深拷贝可以有多种方法，每种方法适用于不同的场景和需求。以下是几种实现深拷贝的方法：

实现深拷贝

1. 使用 JSON.parse() 和 JSON.stringify()

这是最简单的深拷贝实现方式，但它有局限性，例如不能复制函数、循环引用以及特殊对象（如Date, RegExp, Map, Set等，在 parse 过程中会变为字面量）。

function deepClone(obj) {
  return JSON.parse(JSON.stringify(obj));
}

let original = { a: 1, b: { c: 2 } };
let clone = deepClone(original);

2. 手动实现递归深拷贝

你可以手动编写一个递归函数来处理各种数据类型的深拷贝：

function deepClone(obj, hash = new WeakMap()) {
  if (obj === null) return null;
  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof RegExp) return new RegExp(obj);
  if (typeof obj !== "object") return obj;

  if (hash.has(obj)) return hash.get(obj); // 处理循环引用

  let clone = Array.isArray(obj) ? [] : {};
  hash.set(obj, clone);

  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key], hash);
    }
  }
  return clone;
}

let original = { a: 1, b: { c: 2 } };
let clone = deepClone(original);

3. 使用 structuredClone()

从 ECMAScript 2021 开始，structuredClone() 方法可以用来创建一个深拷贝的对象。它可以处理循环引用，并且能够复制许多内置类型，但不是所有环境都支持。

let original = { a: 1, b: { c: 2 } };
let clone = structuredClone(original);

4. 使用库函数

一些第三方库如 Lodash 提供了深拷贝的函数。例如，Lodash 的 _.cloneDeep() 方法：

// 需要安装 lodash 库
import cloneDeep from "lodash/cloneDeep";

let original = { a: 1, b: { c: 2 } };
let clone = cloneDeep(original);

5. 使用 MessageChannel

对于支持 HTML5 MessageChannel API 的环境（如浏览器），你可以使用它来异步地深拷贝对象：

function deepClone(obj) {
  return new Promise((resolve) => {
    const { port1, port2 } = new MessageChannel();
    port2.onmessage = (ev) => resolve(ev.data);
    port1.postMessage(obj);
  });
}

let original = { a: 1, b: { c: 2 } };
deepClone(original).then((clone) => {
  console.log(clone);
});

选择哪种方法取决于你的具体需求和目标环境。例如，如果你正在处理一个简单的对象并且不担心函数或特殊对象的问题，JSON.parse(JSON.stringify())可能足够了。但如果你需要一个更可靠的解决方案，可以处理各种边缘情况，那么使用递归函数或第三方库可能更合适。

JSON.parse(JSON.stringify())

• 循环引用：如果数组中包含循环引用，JSON.parse(JSON.stringify())会抛出错误，而structuredClone()可以处理。
• 特殊对象：对于特殊对象（如Date, RegExp, Map, Set等），JSON.parse(JSON.stringify())不会正确处理，而structuredClone()和一些库函数可以。
• 函数和原型链：函数和原型链不会被JSON.parse(JSON.stringify())复制，而structuredClone()和库函数有可能处理这些情况。

使用场景

深拷贝通常在需要完全独立副本的场景中使用，以确保原始数据和副本之间的操作不会互相影响。以下是一些典型的深拷贝使用场景和示例：

1. 防止对原始数据的意外修改

当你有一个对象或数组，并且你需要对其进行修改，但又不希望这些修改影响到原始数据时，深拷贝是非常有用的。

let originalConfig = {
  server: { host: "localhost", port: 8080 },
  permissions: ["read", "write"],
};

let newConfig = structuredClone(originalConfig);
newConfig.server.port = 9090; // 修改副本的端口
newConfig.permissions.push("delete"); // 添加权限

console.log(originalConfig); // 原始配置不变
console.log(newConfig); // 副本已经变更

2. 撤销/重做功能

在实现撤销/重做功能时，你可能需要保留操作前后的数据状态。深拷贝可以用来保存每次操作的状态。

function saveState(state) {
  history.push(structuredClone(state));
}

let state = {
  text: "initial state",
  changes: [],
};

saveState(state); // 保存初始状态

state.text = "changed state";
saveState(state); // 保存更改后的状态

// 可以使用 history.pop() 来撤销到上一个状态

3. 在并发编程中避免冲突

在进行并发编程，如 Web Workers 或 Node.js 的多线程时，深拷贝可以帮助避免共享状态导致的冲突。

// 在主线程
let originalData = { list: [1, 2, 3] };

// 发送数据到worker，深拷贝以防止共享引用
worker.postMessage(structuredClone(originalData));

// 在Web Worker
self.onmessage = function (e) {
  let data = e.data;
  // 对data的操作不会影响主线程的originalData
};

4. 缓存不可变数据

在某些应用中，你可能需要缓存数据，以便可以快速恢复到某个特定的状态。深拷贝可以确保缓存的数据保持不变。

let cache = {};

function fetchData(key) {
  if (!cache[key]) {
    // 假设 getDataFromDatabase 是一个异步获取数据的函数
    cache[key] = structuredClone(getDataFromDatabase(key));
  }
  return cache[key];
}

let data = fetchData("userInfo");
// data是userInfo的深拷贝，可以安全地修改而不影响缓存

5. 测试和模拟

在编写测试时，深拷贝可以帮助创建测试用例的隔离副本，从而避免测试间的数据干扰。

let initialState = {
  users: [{ id: 1, name: "Alice" }],
  loggedIn: false,
};

function testApplication() {
  let state = structuredClone(initialState);
  // 对state进行操作，测试不同的逻辑路径
  // 每个测试都使用未经修改的initialState的深拷贝
}

在这些场景中，深拷贝的关键优势在于创建数据的独立副本。这样，你就可以自由地修改副本，而不用担心会影响到原始数据。这对于保持数据的完整性和预测性至关重要。

除了前面提到的使用场景，深拷贝还可以应用于以下情况：

6. 状态管理 在一些前端框架中，如 React 或 Vue，状态管理库（如 Redux 或 Vuex）经常要求你不直接修改状态，而是通过返回一个新的状态对象来进行更新。深拷贝可以在这里确保不直接修改原始状态。

function reducer(state, action) {
  switch (action.type) {
    case "ADD_ITEM":
      // 使用深拷贝来创建新的状态
      let newState = structuredClone(state);
      newState.items.push(action.payload);
      return newState;
    default:
      return state;
  }
}

7. 数据归一化 在处理复杂的数据结构时，深拷贝可以帮助实现数据的归一化，即将嵌套的数据结构转换为每个实体的单一引用，以便于管理和更新。

let comments = {
  post1: [{ id: 1, text: "Great post!" }],
  post2: [{ id: 2, text: "Interesting read." }],
};

let normalizedData = structuredClone(comments);
// 使用深拷贝后，可以重构数据结构而不影响原始数据

8. 保持数据同步 在需要将数据同步到多个客户端或服务时，深拷贝可以确保每个地方都有一个一致的数据副本。

let sessionData = {
  user: { id: 1, name: "John Doe" },
  settings: { theme: "dark", notifications: true },
};

// 发送数据到另一个客户端
sendDataToClient(structuredClone(sessionData));

9. 创建复杂的默认参数 在函数编程时，如果你有一个包含多层嵌套对象的默认参数，你可能会想要在每次函数调用时创建这个默认参数的一个新副本，以免意外更改。

function initialize(config) {
  let defaultConfig = structuredClone({
    files: [],
    settings: {
      directory: "/default/path",
      createIfMissing: true,
    },
  });
  config = { ...defaultConfig, ...config };
  // 使用config进行初始化
}

10. 保护 API 返回的数据 当你从 API 接收到数据时，你可能想要对这些数据进行处理，但又不希望改变原始数据，以便日后的重用。

fetch("https://api.example.com/data")
  .then((response) => response.json())
  .then((data) => {
    let dataCopy = structuredClone(data);
    // 对dataCopy进行操作，而不影响原始data
  });

在所有这些场景中，深拷贝的目的都是为了数据的安全性和代码的可维护性。通过确保数据的不可变性，你可以避免很多因数据共享和意外修改导致的 bug 和问题。在进行深拷贝时，应该考虑到性能开销，特别是对于大型或复杂的数据结构，深拷贝可能会导致显著的性能下降。因此，应该在需要时才使用深拷贝，并且在可能的情况下寻找更高效的解决方案。

递归

是什么

递归是一种编程技术，它允许函数直接或间接地调用自身。在 JavaScript 中，递归通常用于处理那些可以分解为更小、更简单子问题的问题，尤其是在处理树形结构（如 DOM 树或数据结构）时非常有用。

递归函数通常有两个主要特征：

1. 基本情况（Base Case）：这是递归停止的条件。每次递归调用都应该使问题更接近基本情况，否则递归将无限进行下去，最终可能导致堆栈溢出错误。

2. 递归步骤（Recursive Step）：在这一步中，函数直接或间接地调用自身，通常是用一组不同的参数。

下面是一个简单的 JavaScript 递归函数示例，它计算一个数字的阶乘：

function factorial(n) {
  // 基本情况
  if (n === 0 || n === 1) {
    return 1;
  }
  // 递归步骤
  else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5)); // 输出: 120

在上面的例子中，factorial函数调用自身，每次都将参数n减少 1，直到n等于 0 或 1，这时函数返回 1，递归调用结束。

递归是一种强大的工具，但也需要谨慎使用，因为不恰当的递归可能导致性能问题或堆栈溢出错误。为了避免这些问题，可以使用迭代方法或实现尾递归优化（在支持尾调用优化的 JavaScript 引擎中）。尾递归是一种特殊形式的递归，递归调用是函数体中的最后一个操作，这允许某些编译器或解释器优化递归，使其在内存使用上与迭代解决方案相媲美。

知识点

递归是计算机科学中的一个核心概念，它在算法设计和程序实现中扮演着重要的角色。理解递归需要掌握以下几个关键知识点：

1. 递归定义：

   • 递归是一种解决问题的方法，它将问题分解成更小的子问题，然后再将子问题分解成更小的子问题，直到这些子问题变得足够小，可以直接解决。
   • 递归函数是一种调用自身的函数。

2. 基本情况（Base Case）：

   • 基本情况是递归的停止条件。没有基本情况的递归将会无限进行下去，导致堆栈溢出错误。
   • 通常，基本情况对应于问题的最简单或最小实例。

3. 递归步骤（Recursive Step）：

   • 在递归步骤中，问题被分解成一个或多个更小的子问题，这些子问题本身又是原始问题的实例。
   • 递归步骤必须逐渐靠近基本情况，以确保递归最终会结束。

4. 栈内存（Stack Memory）：

   • 递归函数的每一次调用都会在调用栈上创建一个新的执行上下文。
   • 如果递归太深，可能会耗尽栈空间，导致堆栈溢出错误。

5. 尾递归优化（Tail Recursion Optimization）：

   • 尾递归是递归的一种特殊形式，其中递归调用是函数中的最后一个动作。
   • 尾递归可以被某些编程语言的编译器优化，以避免增加新的栈帧而重用当前的栈帧。

6. 递归与迭代（Recursion vs. Iteration）：

   • 递归和迭代都可以用来解决循环问题。
   • 在某些情况下，递归比迭代更自然地映射到问题上，尤其是在处理递归定义的数据结构（如树和图）时。

7. 递归树（Recursion Tree）：

   • 递归树是一种可视化递归调用的工具，它展示了递归函数如何将问题分解成更小的子问题。
   • 递归树有助于分析递归算法的时间复杂度。

8. 分治策略（Divide and Conquer）：

   • 分治策略是一种算法设计范式，它使用递归来解决问题。
   • 它将问题分解成若干个小问题，递归解决这些小问题，然后将小问题的解合并成原问题的解。

9. 递归缓存（Memoization）：

   • 递归中可能会出现重复计算相同子问题的情况，这会导致效率低下。
   • 通过缓存已解决的子问题的结果，可以避免重复工作，这种技术称为 memoization。

10. 递归算法的例子：

    • 许多经典算法都是递归的，比如快速排序、归并排序、二分搜索、深度优先搜索（DFS）、广度优先搜索（BFS）等。

理解上述知识点有助于在实际编程中更有效地使用递归，并能够识别和解决与递归相关的问题。

实现递归

在 JavaScript 中实现递归通常遵循以下步骤：

1. 确定基本情况

基本情况是递归终止的条件。在设计递归函数时，首先要确定当问题规模足够小以至于可以直接解答时，函数应该如何行为。基本情况防止了无限递归的发生。

2. 确定递归情况

递归情况定义了函数如何将较大的问题分解为较小的子问题，并且如何从这些子问题的解构建出原问题的解。递归函数在每次递归调用时都应该使问题规模变小，从而逐步逼近基本情况。

3. 编写递归函数

结合基本情况和递归情况，编写递归函数。确保每次调用都是向基本情况靠近，并且每个递归调用都是独立的，不会相互干扰。

4. 测试和调试

测试递归函数以确保它不仅可以处理基本情况，还可以正确处理更复杂的情况。调试任何可能出现的问题，如堆栈溢出错误、逻辑错误或性能问题。

5. 考虑优化

对于某些递归函数，可能需要考虑优化以避免性能问题。优化可以包括使用尾递归（在支持的 JavaScript 引擎中），或者使用 memoization 来缓存和重用已经计算过的结果。

示例：计算斐波那契数列

下面是计算斐波那契数列的递归函数的一个例子：

function fibonacci(n) {
  // 基本情况
  if (n <= 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  // 递归情况
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 输出: 55

在这个例子中，基本情况是当n等于 0 或 1 时。递归情况是将fibonacci(n)分解为fibonacci(n - 1) + fibonacci(n - 2)。

注意：

上面的斐波那契数列实现非常直观，但它的效率很低，因为它重复计算了许多子问题。对于大的n值，这个实现会变得非常慢。使用 memoization 或迭代方法可以显著提高效率。

使用 Memoization 的斐波那契数列：

function fibonacciMemo(n, memo = {}) {
  if (n <= 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (!memo[n]) {
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  }
  return memo[n];
}

console.log(fibonacciMemo(10)); // 输出: 55

在这个优化版本中，我们使用一个对象memo来存储和查找已经计算过的斐波那契数，这样就避免了重复计算。

使用场景

递归在计算机科学中有许多使用场景，尤其是在处理那些自然具有递归结构的问题时，比如数据结构（如树和图）和算法（如分而治之策略）。以下是一些具体的使用场景和示例：

1. 遍历树结构

在遍历树结构（如 DOM 树、二叉树）时，递归能够简化代码，因为你可以对每个节点应用相同的逻辑。

示例：二叉树的中序遍历。

function inorderTraversal(node) {
  if (node !== null) {
    inorderTraversal(node.left);
    console.log(node.value);
    inorderTraversal(node.right);
  }
}

2. 文件系统操作

递归可以用来遍历文件系统中的目录树，例如，搜索文件、计算目录大小等。

示例：计算给定目录中所有文件的总大小（假设有一个 API 可以列出目录内容和获取文件大小）。

function calculateDirectorySize(directory) {
  let totalSize = 0;
  const files = listFilesInDirectory(directory); // 假设这个函数返回目录中的文件列表
  files.forEach((file) => {
    if (isDirectory(file)) {
      totalSize += calculateDirectorySize(file);
    } else {
      totalSize += getFileSize(file); // 假设这个函数返回文件的大小
    }
  });
  return totalSize;
}

3. 分而治之算法

许多算法使用分而治之的策略，将大问题分解成小问题，单独解决每个小问题，然后合并结果。典型的例子包括快速排序和归并排序。

示例：快速排序。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

4. 解决数学问题

递归在解决数学问题中也非常有用，比如计算阶乘、斐波那契数列、汉诺塔问题等。

示例：计算阶乘。

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

5. 搜索和路径发现

在图形和游戏编程中，递归用于搜索操作，如深度优先搜索（DFS）和广度优先搜索（BFS），以及寻找路径和解决迷宫问题。

示例：深度优先搜索。

function depthFirstSearch(node, target) {
  if (node.value === target) {
    return node;
  }
  for (let child of node.children) {
    const result = depthFirstSearch(child, target);
    if (result !== null) {
      return result;
    }
  }
  return null;
}

6. 动态规划

在动态规划问题中，通常会递归地定义值函数，并使用 memoization 来避免重复计算。

示例：使用递归和 memoization 解决背包问题。

function knapsack(items, capacity, index, memo) {
  if (memo[capacity][index]) {
    return memo[capacity][index];
  }
  if (index === 0 || capacity === 0) {
    return 0;
  }
  if (items[index - 1].weight > capacity) {
    return knapsack(items, capacity, index - 1, memo);
  } else {
    const withItem =
      items[index - 1].value +
      knapsack(items, capacity - items[index - 1].weight, index - 1, memo);
    const withoutItem = knapsack(items, capacity, index - 1, memo);
    memo[capacity][index] = Math.max(withItem, withoutItem);
    return memo[capacity][index];
  }
}

递归是一种强大的编程工具，但它也有缺点，如潜在的堆栈溢出问题和可能的性能问题。因此，在选择使用递归时，应当根据问题的性质和上下文来权衡利弊。