为何尾递归模幂C++代码在本地Windows设备无法运行？

用户编写的代码如下：

#include <bits/stdc++.h>
using namespace std;
#define mod (1000000000+7)
#define ll long long

ll modexp(ll x,ll n,ll res=1){
    if(n==0) return res;
    return modexp(x, n-1,(x % mod *res % mod) % mod);
} 
int main(){
    cout<<modexp(2,100000);
}

本地编译运行操作：

PS C:\Users\User\Desktop\cpcpp> g++ test.cpp -o test.exe
PS C:\Users\User\Desktop\cpcpp> .\test.exe
PS C:\Users\User\Desktop\cpcpp>

编译成功但无输出，该代码在在线IDE可正常运行。

问题原因 #

核心问题是栈溢出。Windows系统下GCC默认栈空间仅约1MB，而代码中递归调用次数高达100000次，每次递归都会在栈上保存返回地址、参数等数据，很快耗尽栈空间导致程序直接崩溃，因此无任何输出。在线IDE通常配置了更大的栈空间，或默认开启优化选项将尾递归转换为循环，从而规避了栈溢出问题。

解决方案 #

方案1：开启编译器优化 #

使用-O2或更高优化级别编译，GCC会自动识别尾递归并将其优化为循环，避免栈溢出：

g++ test.cpp -o test.exe -O2

方案2：手动改写为迭代版本 #

不依赖编译器优化，直接将递归改为迭代实现，彻底避免栈溢出：

#include <bits/stdc++.h>
using namespace std;
#define mod (1000000000+7)
#define ll long long

ll modexp(ll x, ll n, ll res = 1) {
    while (n > 0) {
        res = (x % mod * res % mod) % mod;
        n--;
    }
    return res;
} 

int main() {
    cout << modexp(2, 100000) << endl;
}

进阶优化：快速幂算法 #

可以进一步改用二进制快速幂，大幅减少计算次数，提升效率：

#include <bits/stdc++.h>
using namespace std;
#define mod (1000000000+7)
#define ll long long

ll modexp(ll x, ll n, ll res = 1) {
    x %= mod;
    while (n > 0) {
        if (n % 2 == 1) {
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        n /= 2;
    }
    return res;
} 

int main() {
    cout << modexp(2, 100000) << endl;
}

内容的提问来源于stack exchange，提问作者akib35