03-进阶基础/05-递归

简单递归

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

递归的两个要点

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

阶乘

[math]\displaystyle{ n! = n \times (n-1)! }[/math]

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

斐波那契数列

[math]\displaystyle{ F(1)=1,\ F(2)=1,\ F(n)=F(n-1)+F(n-2) }[/math]

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

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

递推 vs 递归

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

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;
}

递归实现全排列

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;  // 回溯
        }
    }
}

递归注意事项

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