递归栈

一句话理解

递归栈是一层层还没返回的函数调用。

为什么要学

太深会爆栈，表现为 RE。

讲解

每进入一次调用，就压一层局部变量和返回地址。返回时弹出。

深度大约几千到几万就可能爆，和系统栈大小有关。能改成循环的，深层递归要小心。

例子

int g(int n) {
    if (n == 0) return 0;
    return g(n - 1) + 1;
}
// g(1000000) 很可能爆栈

虽然逻辑是对的，但深度一百万，栈装不下。

常见错误

• n=1e5 的链式递归当没事。
• 把栈爆当成 WA。