c++ - 递归累积和

Question

我正在尝试用 C++ 编写一个简单的递归求和函数:

long long int recursum(long long int n){
    if(n==1)
        return 1;
    else
        return recursum(n-1)+n;
}

这应该可行，但我得到值大于 ~250000 的段错误。我非常确定这应该可行，因为它是一个非常简单的带有终止语句的递归。

Answer 1

您必须为您的编译器激活优化以尝试“取消递归”函数，以免破坏您的调用堆栈。

在我的电脑上测试的例子

#include <iostream>

long long int recursum(long long int n){
    if(n==1)
        return 1;
    else
        return recursum(n-1)+n;
}


int main(int argc, char const *argv[])
{
    std::cout << recursum(99000) << std::endl;
    return 0;
}

没有优化:

$ ./a.exe
Segmentation fault (core dumped)

使用 g++ -O3:

$ ./a.exe
4900549500

我什至尝试使用 500000。

如果没有特定的优化需求，尾递归优化和类似的事情(我不知道其他人的名字)是不会做的。