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

递归的使用

news 2024/11/1 0:40:44

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

递归的基本组成

终止条件（Base Case）：这是递归停止的条件，避免无限循环。例如，在阶乘问题中，n = 1 是递归的终止条件。
递归调用（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，栈开始回溯

回溯过程（栈出栈）

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

factorial(1) 返回 1（栈顶出栈）
factorial(2) 返回 2 * 1 = 2
factorial(3) 返回 3 * 2 = 6
factorial(4) 返回 4 * 6 = 24
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) = 0 和 f(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) 调用过程如下：

计算 fibonacci(5)：
- 需要 fibonacci(4) 和 fibonacci(3)
计算 fibonacci(4)：
- 需要 fibonacci(3) 和 fibonacci(2)
计算 fibonacci(3)：
- 需要 fibonacci(2) 和 fibonacci(1)
计算 fibonacci(2)：
- 需要 fibonacci(1) 和 fibonacci(0)
fibonacci(1) 返回 1，fibonacci(0) 返回 0，fibonacci(2) 得到 1。
倒推上去，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')，递归处理流程如下：

目录 /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
目录 /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')
目录 /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 树

进入节点 node，打印节点标签。
遍历 node 的每一个子节点，递归调用 traverseDOM(child)。
递归终止条件：当节点无子节点时自动结束。

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或以下，则直接返回（递归终止条件）。
选择基准值，将数组划分为小于基准和大于基准的两个子数组。
分别递归地对左右子数组进行排序，并将结果合并。

深度优先搜索（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;
}

检查当前位置是否有效，若无效返回 false。
标记路径（如path.push([x, y])），然后递归探索四个方向。
如果找到路径返回 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;
}