递归

什么是递归？

递归（recursion）是一种编程技术，通过在函数内部调用自身来解决问题。递归函数在处理问题时将其分解为更小的子问题，并通过递归调用自身来解决这些子问题。递归通常用于解决可以被分解成相同类型的更小问题的问题。

递归的基本原理和工作方式

• 函数定义中包含对自身的调用。
• 函数在每次调用时都会改变输入参数，以便将问题规模缩小到更小的子问题。
• 函数定义中包含一个或多个停止条件（也称为基本情况），用于结束递归并返回结果。
• 递归的基本原理是将复杂的问题划分为更小的、可解决的子问题，并通过递归调用自身来解决这些子问题。每次递归调用都会将问题的规模缩小，直到达到停止条件为止。

递归的优点和缺点

递归的优点：

• 可以简化复杂的问题，使代码更加简洁和可读。
• 可以处理需要多层嵌套的问题，使代码结构更清晰。

递归的缺点：

• 可能导致性能问题，因为递归函数会对同一问题进行多次计算。
• 如果停止条件不正确或缺失，可能导致无限递归，最终导致栈溢出错误。

如何正确使用递归

要正确使用递归，需要考虑以下几点：

• 定义明确的停止条件，以确保递归在适当的时候结束。
• 确保每次递归调用都将问题的规模缩小，以便最终达到停止条件。
• 避免无效的递归调用，以提高性能并避免栈溢出错误。

常见的递归应用场景

递归在许多编程问题中都有应用，例如：

计算阶乘

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

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

遍历树或图

// 定义二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 递归遍历二叉树的函数
function traverseTree(root) {
  if (root === null) {
    return;
  }

  // 前序遍历代码位置
  console.log(root.val);

  traverseTree(root.left); // 递归遍历左子树

  // 中序遍历代码位置
  // console.log(root.val);

  traverseTree(root.right); // 递归遍历右子树

  // 后序遍历代码位置
  // console.log(root.val);
}

// 创建二叉树
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// 调用递归遍历函数
traverseTree(root);

解决分治问题

递归实现简单的归并排序算法

function divideAndConquer(problem) {
  // 判断是否需要继续分治
  if (problem.length < 2) {
    return problem;
  }

  // 分治
  const mid = Math.floor(problem.length / 2);
  const left = problem.slice(0, mid);
  const right = problem.slice(mid);

  // 递归处理左右子问题
  const leftResult = divideAndConquer(left);
  const rightResult = divideAndConquer(right);

  // 合并结果
  return merge(leftResult, rightResult);
}

function merge(left, right) {
  let result = [];

  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  return result.concat(left, right);
}