查看“︁03-进阶基础/05-递归”︁的源代码


== 简单递归 ==

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

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

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:三三文档]]