33DAI：导入1个版本

2026-05-20T18:12:09Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本	2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:20Z

导入1个版本

←上一版本	2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 简单递归 ==

递归就是函数自己调用自己。

=== 递归的两个要点 ===

1. '''边界条件'''：何时停止递归
2. '''递归关系'''：如何用更小的问题表示当前问题

=== 阶乘 ===

<math>n! = n \times (n-1)!</math>

<syntaxhighlight lang="cpp">
int fact(int n)
{
if (n == 0) // 边界条件
return 1;
return n * fact(n - 1); // 递归关系
}
</syntaxhighlight>

=== 斐波那契数列 ===

<math>F(1)=1,\ F(2)=1,\ F(n)=F(n-1)+F(n-2)</math>

<syntaxhighlight lang="cpp">
int fib(int n)
{
if (n <= 2) // 边界条件
return 1;
return fib(n - 1) + fib(n - 2); // 递归关系
}
</syntaxhighlight>

注意：纯递归求斐波那契数列效率很低 (<math>O(2^n)</math>)，实际通常用递推。

=== 递推 vs 递归 ===

递推（循环实现，从下往上）：

<syntaxhighlight lang="cpp">
int fib(int n)
{
int a = 1, b = 1;
for (int i = 3; i <= n; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
</syntaxhighlight>

=== 递归实现全排列 ===

<syntaxhighlight lang="cpp">
int n;
int a[10];
bool vis[10];

void dfs(int step)
{
if (step > n) // 边界：选完了
{
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << "\n";
return;
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
vis[i] = true;
a[step] = i;
dfs(step + 1); // 递归选下一个
vis[i] = false; // 回溯
}
}
}
</syntaxhighlight>

=== 递归注意事项 ===

- 递归深度过大可能导致'''栈溢出'''（Windows 默认约 <math>8</math> MB，Linux 约 <math>8</math> MB）
- 可以用 <code>ulimit -s unlimited</code>（Linux）或开栈编译选项（Windows）增加栈空间
- 很多递归可以转化为递推来避免栈溢出

[[Category:进阶基础]]
[[Category:三三文档]]

03-进阶基础/05-递归 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档