当前位置: 首页 > news >正文

递归的使用

递归是一种算法设计思想,通过一个函数调用自身来解决问题,通常适用于可以分解为子问题的问题。递归的执行依赖递归栈,用于保存每次递归调用的执行状态,包括每一层的参数、局部变量等。每次函数调用会向栈中添加一个新的栈帧(stack frame),直到达到终止条件停止调用,然后从栈顶依次“回溯”返回每层的结果。

递归的基本组成

  1. 终止条件(Base Case):这是递归停止的条件,避免无限循环。例如,在阶乘问题中,n = 1 是递归的终止条件。

  2. 递归调用(Recursive Call):递归的核心部分,即函数调用自身,逐步解决规模更小的子问题。

阶乘计算

通过示例 阶乘计算 展示递归栈的链路。在阶乘计算中,n! = n * (n - 1)!,终止条件是 n = 1,返回 1。假设调用 factorial(5),执行链路如下:

function factorial(n) {if (n === 1) return 1; // 终止条件return n * factorial(n - 1); // 递归调用
}console.log(factorial(5)); // 输出120

递归栈的执行过程

调用 factorial(5) 时,递归栈的状态变化如下:

  • Step 1: factorial(5) 入栈
    参数 n = 5
    调用 factorial(4),等待结果
  • Step 2: factorial(4) 入栈
    参数 n = 4
    调用 factorial(3),等待结果
  • Step 3: factorial(3) 入栈
    参数 n = 3
    调用 factorial(2),等待结果
  • Step 4: factorial(2) 入栈
    参数 n = 2
    调用 factorial(1),等待结果
  • Step 5: factorial(1) 入栈(终止条件)
    参数 n = 1
    满足终止条件,返回 1,栈开始回溯

回溯过程(栈出栈)

递归调用结束后,栈从顶层逐步出栈并返回结果:

  1. factorial(1) 返回 1(栈顶出栈)
  2. factorial(2) 返回 2 * 1 = 2
  3. factorial(3) 返回 3 * 2 = 6
  4. factorial(4) 返回 4 * 6 = 24
  5. factorial(5) 返回 5 * 24 = 120

回溯阶段:

调用阶段:              回溯阶段:
factorial(5)            <---   factorial(5) = 5 * 24 = 120├─ factorial(4)       <---   factorial(4) = 4 * 6 = 24├─ factorial(3)   <---   factorial(3) = 3 * 2 = 6├─ factorial(2)   <---   factorial(2) = 2 * 1 = 2└─ factorial(1) = 1

每次调用自身时,递归栈会逐层递进并保留调用状态,遇到终止条件后逐步回溯出栈,直到得到最终结果。递归栈的结构使得每层调用的结果可以依次传递给上层调用,形成了一个完整的执行链路。

斐波那契数列

斐波那契数列的公式为:f(n) = f(n-1) + f(n-2),即每个数字等于前两个数字之和,初始条件是 f(0) = 0f(1) = 1。用递归计算斐波那契数的代码如下:

function fibonacci(n) {if (n === 0) return 0;if (n === 1) return 1;return fibonacci(n - 1) + fibonacci(n - 2);
}// 示例调用
console.log(fibonacci(5)); // 输出 5

执行过程分解

假设 fibonacci(5) 调用过程如下:

  1. 计算 fibonacci(5)

    • 需要 fibonacci(4)fibonacci(3)
  2. 计算 fibonacci(4)

    • 需要 fibonacci(3)fibonacci(2)
  3. 计算 fibonacci(3)

    • 需要 fibonacci(2)fibonacci(1)
  4. 计算 fibonacci(2)

    • 需要 fibonacci(1)fibonacci(0)
  5. fibonacci(1) 返回 1,fibonacci(0) 返回 0,fibonacci(2) 得到 1。

  6. 倒推上去,fibonacci(3) 计算完成得到 2,fibonacci(4) 计算完成得到 3,最终 fibonacci(5) 计算完成得到 5。

文件夹遍历(递归文件夹内容)

这是一个常见的递归应用场景。我们通过递归来遍历目录结构,并打印每个文件和子文件夹的路径。

const fs = require('fs');
const path = require('path');function traverseDirectory(directory) {const files = fs.readdirSync(directory);files.forEach(file => {const fullPath = path.join(directory, file);const stats = fs.statSync(fullPath);if (stats.isDirectory()) {console.log("Directory:", fullPath);traverseDirectory(fullPath);  // 递归调用} else {console.log("File:", fullPath);}});
}// 示例调用
traverseDirectory('/path/to/directory');

执行过程分解

假设 /path/to/directory 目录结构如下:

/path/to/directory
├── file1.txt
├── subfolder1
│   ├── file2.txt
│   └── subfolder2
│       └── file3.txt
└── file4.txt

调用 traverseDirectory('/path/to/directory'),递归处理流程如下:

  1. 目录 /path/to/directory:

    • 遇到文件 file1.txt,输出 File: /path/to/directory/file1.txt
    • 遇到目录 subfolder1,输出 Directory: /path/to/directory/subfolder1,并递归调用 traverseDirectory('/path/to/directory/subfolder1')
    • 遇到文件 file4.txt,输出 File: /path/to/directory/file4.txt
  2. 目录 /path/to/directory/subfolder1:

    • 遇到文件 file2.txt,输出 File: /path/to/directory/subfolder1/file2.txt
    • 遇到目录 subfolder2,输出 Directory: /path/to/directory/subfolder1/subfolder2,并递归调用 traverseDirectory('/path/to/directory/subfolder1/subfolder2')
  3. 目录 /path/to/directory/subfolder1/subfolder2:

    • 遇到文件 file3.txt,输出 File: /path/to/directory/subfolder1/subfolder2/file3.txt

整个递归过程将逐层深入目录,在没有子目录后回溯,最终完成所有文件和目录的遍历。
这两个例子展示了递归的不同用法:

  • 斐波那契数列展示了如何通过递归逐步分解问题,每次返回值在回溯时逐步累积得到最终结果。
  • 文件夹遍历展示了递归如何深入嵌套的结构并按层级访问每个元素,同时在每一步将路径或状态传递至下一层

树或图结构的遍历

树结构的遍历可以通过递归来实现,因为树的每个节点可能包含子节点,而每个子节点又可能有它自己的子节点。递归遍历树结构的典型操作包括:

  • 前序遍历:先处理当前节点,然后递归处理子节点。
  • 后序遍历:先递归处理子节点,然后处理当前节点。
  • 中序遍历:仅用于二叉树,左子节点 -> 根节点 -> 右子节点。

代码示例(前序遍历 DOM 树)

function traverseDOM(node) {console.log(node.tagName); // 处理当前节点node.children.forEach(child => traverseDOM(child)); // 递归处理子节点
}// 调用
traverseDOM(document.body); // 遍历整个 DOM 树
  1. 进入节点 node,打印节点标签。
  2. 遍历 node 的每一个子节点,递归调用 traverseDOM(child)
  3. 递归终止条件:当节点无子节点时自动结束。

2分治法

分治法用于将一个问题分成几个相似的子问题,然后合并子问题的解。典型的例子包括快速排序和归并排序。

示例:快速排序

快速排序通过选择一个基准值,将数组划分为小于和大于基准的两部分,分别对两部分递归排序。

代码示例

function quickSort(arr) {if (arr.length <= 1) return arr; // 递归终止条件const pivot = arr[Math.floor(arr.length / 2)];const left = arr.filter(x => x < pivot);const right = arr.filter(x => x > pivot);return [...quickSort(left), pivot, ...quickSort(right)]; // 合并
}// 调用
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // 排序输出
  1. 如果数组长度为1或以下,则直接返回(递归终止条件)。
  2. 选择基准值,将数组划分为小于基准和大于基准的两个子数组。
  3. 分别递归地对左右子数组进行排序,并将结果合并。

深度优先搜索(DFS)

DFS 是遍历图或树的一种方法,适合递归实现。它会尽可能深地进入每个节点,再逐步回溯访问未访问的节点。

示例:迷宫路径查找

在一个二维迷宫中,找出从起点到终点的路径(假设迷宫中只有一个解)。

代码示例

function findPath(maze, x, y, path = []) {if (!isValid(maze, x, y)) return false; // 越界或已访问则返回path.push([x, y]); // 记录路径if (isExit(x, y)) return true; // 到达出口if (findPath(maze, x + 1, y, path) || findPath(maze, x - 1, y, path) ||findPath(maze, x, y + 1, path) || findPath(maze, x, y - 1, path)) {return true;}path.pop(); // 回溯,移除最后一步return false;
}// 判断是否越界、是否已访问等
function isValid(maze, x, y) {return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] === 0;
}// 判断是否到达出口(根据迷宫定义调整条件)
function isExit(x, y) {// 示例出口条件return x === maze.length - 1 && y === maze[0].length - 1;
}
  1. 检查当前位置是否有效,若无效返回 false
  2. 标记路径(如path.push([x, y])),然后递归探索四个方向。
  3. 如果找到路径返回 true;否则弹出路径中的当前位置,回溯到上一步。

回溯算法

回溯算法是一种试探搜索方法,通过不断递归尝试,并在发现不符合条件时“回退”。数独、迷宫和组合问题都是典型的回溯应用场景。

示例:数独求解

在数独中,回溯算法尝试填充每个空格,遇到不合法的状态则回退到上一步重新选择。

代码示例

function solveSudoku(board) {return backtrack(board, 0, 0);
}function backtrack(board, row, col) {if (row === 9) return true; // 全部填满if (col === 9) return backtrack(board, row + 1, 0); // 换行if (board[row][col] !== '.') return backtrack(board, row, col + 1); // 跳过已填for (let num = 1; num <= 9; num++) {if (isValid(board, row, col, num)) {board[row][col] = String(num); // 尝试填入数字if (backtrack(board, row, col + 1)) return true;board[row][col] = '.'; // 回溯}}return false;
}function isValid(board, row, col, num) {for (let i = 0; i < 9; i++) {if (board[row][i] === String(num) || board[i][col] === String(num) ||board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][Math.floor(col / 3) * 3 + i % 3] === String(num)) {return false;}}return true;
}
  1. 从左上角开始遍历每个空格。
  2. 在空格尝试放入 1-9 的数字,检查放置是否合法。
  3. 若放置合法则递归进入下一个空格,否则回溯,恢复空格为.
  4. 最终找到解,或者所有可能数填完回溯到头部返回 false

递归在这些应用中的核心是将问题逐层分解或尝试解答,逐步缩小问题规模,遇到边界条件时开始回溯并积累或合并每一层的结果。


http://www.mrgr.cn/news/62864.html

相关文章:

  • 字节青训营 补给站最优花费问题 一维DP
  • C++ 模板专题 - 静态多态(CRTP)
  • GDB(GNU Debugger)的使用教程
  • Go语言有哪些常用语句?
  • Linux中Samba服务配置和管理
  • 系统架构图设计(行业领域架构)
  • spark==windows启动spark集群
  • [java][高级]RequestResponse
  • 【实战篇】requests库 - 有道云翻译爬虫 【附:代理IP的使用】
  • 【算法】【优选算法】双指针(上)
  • Qt(文件IO)
  • Spring Boot 集成 RabbitMQ
  • Java阶段三02
  • Q-learning原理及代码实现
  • ubuntu交叉编译libffi库给arm平台使用
  • 【力扣打卡系列】二叉树的最近公共祖先
  • 2024最新Linkedln领英养号方法总结
  • 【数学二】线性代数-行列式
  • 早点包子店点餐的软件下载和点餐操作教程 佳易王餐饮点餐管理系统操作方法
  • redis安装使用
  • 攻防世界 MISC miao~详解
  • Android——Activity生命周期
  • 面试题整理 2
  • net framework 3.5组件更新失败错误代码0x80072f8f怎样解决
  • LC:贪心题解
  • Javaweb梳理5——约束