JavaScript中关于递归与回溯的实例详解

什么是递归

在编程中，递归指的是函数调用自身的过程。具体来说，就是函数在执行过程中，可以调用自身来解决问题。递归算法的特点是在问题的求解过程中会把复杂问题分解成简单问题，直到最后简单问题得以解决。常见的递归算法有斐波那契数列、汉诺塔等。

递归的三个要素

递归算法的实现需要满足以下三个要素：

1. 问题的分解

将要解决的问题分解成更小的问题。这是递归算法的第一步，需要明确定义好问题的分解方法。

1. 确定递归出口

在递归算法中，必须要有一个结束条件，当满足这个条件时，递归算法才会停止执行，并返回结果。

1. 调用自身

递归算法的核心就是函数调用自身。在实现过程中，需要注意避免出现无限递归的情况。

什么是回溯

回溯算法是一种解决一些组合问题的有效算法。它采用的是试错的思想，即在解决问题的过程中，当发现已经走到了死路，就会回退一步或多步，重新选择之前没走过的路径继续解决问题。

回溯算法的应用

回溯算法在组合问题、排列问题、集合划分问题等都有应用。例如：

• 组合问题：从 n 个数中取 k 个数的所有组合，可以通过回溯算法实现。
• 排列问题：从 n 个数中取 k 个数的所有排列，也可以通过回溯算法实现。
• 集合划分问题：将 n 个元素分为 k 个子集，每个子集必须非空且互不相交，可以通过回溯算法求解。

JavaScript中递归与回溯的实例

实例一：斐波那契数列

斐波那契数列是指一个数列，其第 1 个元素是 0，第 2 个元素是 1，从第 3 个元素开始，每个元素是前两个元素的和。例如，斐波那契数列的前 10 个数字为 0、1、1、2、3、5、8、13、21、34。

斐波那契数列可以使用递归算法来实现。

function fib(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

实例二：组合问题

给定一个数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

例如，输入 candidates = [10,1,2,7,6,1,5], target = 8，输出为[[1,1,6],[1,2,5],[1,7],[2,6]]。

可以使用回溯算法来实现。

var combinationSum2 = function(candidates, target) {
  let res = [];
  candidates.sort((a,b)=>a-b); // 排序，便于后面的剪枝操作
  let helper = function(nums,idx,result,target){
      if(target === 0){
          res.push(result);
          return;
      }else if(target < 0){
          return;
      }
      for(let i = idx;i < nums.length;i++){
          // 如果 i-1 和 i 相等，则直接跳过，避免重复
          if(i > idx && nums[i]===nums[i-1]){
              continue;
          }
          helper(nums,i+1,[...result,nums[i]],target-nums[i]); // 继续从 i+1 开始组合
      }
  }
  helper(candidates,0,[],target)
  return res;
};

以上就是关于 JavaScript 中递归与回溯的实例详解，希望能给大家带来帮助。