递归算法及其应用

递归算法定义递归是一种函数直接或间接调用自身来解决问题的方法。需要满足两个条件递归边界问题规模缩小到一定程度时直接给出答案不再递归。递归递推式把原问题分解为规模更小的同类型子问题通过调用自身求解。核心思想是将复杂问题分解为更小的同类问题。实际问题解决斐波那契数列斐波那契数列的递归定义为f(0) 0f(1) 1f(n) f(n-1) f(n-2)#include iostream using namespace std; int fib(int n) { if (n 0) return 0; if (n 1) return 1; return fib(n-1) fib(n-2); } int main() { int n; cin n; cout fib(n); return 0; }汉诺塔问题汉诺塔问题的递归解法将n-1个盘子从A移到B将第n个盘子从A移到C将n-1个盘子从B移到C#include iostream using namespace std; void hanoi(int n, char A, char B, char C) { if (n 1) { cout A - C endl; return; } hanoi(n-1, A, C, B); hanoi(1, A, B, C); hanoi(n-1, B, A, C); } int main() { int n; cin n; hanoi(n, A, B, C); return 0; }迷宫寻路迷宫寻路使用递归回溯法从起点开始尝试四个方向能走则递归继续不能走则回溯#include iostream using namespace std; int maze[5][5] { {0,1,0,0,0}, {0,1,0,1,0}, {0,0,0,1,0}, {0,1,1,1,0}, {0,0,0,0,0} }; int vis[5][5] {0}; int dx[] {-1,1,0,0}; int dy[] {0,0,-1,1}; bool dfs(int x, int y) { if (x 4 y 4) return true; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 nx 5 ny 0 ny 5 maze[nx][ny]0 !vis[nx][ny]) { vis[nx][ny] 1; if (dfs(nx, ny)) return true; vis[nx][ny] 0; } } return false; } int main() { vis[0][0] 1; if (dfs(0,0)) cout 找到路径; else cout 无路; return 0; }N皇后问题N皇后问题使用递归回溯法逐行放置皇后检查列和对角线是否冲突#include iostream #include cstring using namespace std; int n, ans 0; int col[20], dg[40], udg[40]; void dfs(int r) { if (r n) { ans; return; } for (int c 0; c n; c) { if (!col[c] !dg[rc] !udg[r-cn]) { col[c] dg[rc] udg[r-cn] 1; dfs(r1); col[c] dg[rc] udg[r-cn] 0; } } } int main() { cin n; dfs(0); cout ans; return 0; }递归与数学归纳法递归与数学归纳法有相似的结构基例对应递归边界归纳假设对应递归调用归纳步骤对应递归递推式递归是计算机实现数学归纳法的具体方式。递归通用模板递归问题的通用解法模板返回值 dfs(参数) { if (到达边界) return 结果; // 选择一种情况 标记; dfs(子问题); 取消标记; }