谁能解释为什么这个递归函数会崩溃？

Question

为什么这个递归（我不确定，我发现这段代码的网站说它是“递归的”）代码崩溃（我在互联网上发现了这种奇怪的方法，但老实说我不明白如何它有效）输入值>4000（有时>4023，有时>4015，我真的不明白...）...

#include <iostream>
unsigned long long int sum(unsigned long long int k)
{
    if (k > 0) {
        return k + sum(k - 1);
    }
    else {
        return 0;
    }
}
int main()
{
    unsigned long long int n;
    std::cout << "This program prints the sum of the first N natural numbers.\n\
Enter N: _";
    std::cin >> n;
    std::cout << "The sum is: " << sum(n) << ".\n\
Press any key to exit...";
    system("pause>nul");
    return 0;
}

而这不是吗？

#include <iostream>
int main()
{
    unsigned int n;
    std::cout << "Questo programma stampa la somma dei primi N numeri naturali.\n\
Prego inserire N: _";
    std::cin >> n;
    unsigned long long int tmp = 0;
    for (n; n != 0; --n) {
        tmp += n;
        //std::cout << tmp << ' ';
    }
    std::cout << "La somma 2: " << tmp << ".\n\
Premere un tasto per uscire...";
    system("pause>nul");
    return 0;
}

Answer 1

递归版本每次调用自身都会占用一点栈space，所以受限于栈的大小，调用自身次数过多会崩溃。这是一个典型的 stack overflow 错误。

迭代的第二个版本没有这个问题。

Answer 2

你的第一个方法

第一种方法是递归的。这意味着它为每个 k 调用函数 sum() 一次。比方说，k 是 2，比 sum() 被调用两次等等。

每个函数调用的参数、局部变量和一些管理数据如堆栈指针、return函数调用时程序跳转到的return地址都需要在堆栈上space =]s 和其他一些东西。当您过于频繁地调用 sum() 时，可以说大约 4000 次，堆栈中没有足够的 space 来进行下一次对 sum() 的调用。结果导致堆栈溢出，应用程序崩溃。

在您的应用程序崩溃之前您可以提供的 k 的确切最大值取决于您的系统。这意味着，在具有 Windows、Linux 的桌面或具有“大”堆栈的 MacOS 上，您可以使用 k = round 调用函数约 4000 次，而在嵌入式系统上，每个线程的堆栈可能较低，并且您的应用程序更早崩溃。

你的第二种方法

您的第二种方法不是递归的，因此不需要在堆栈上添加任何额外的 space 来调用其他函数。因此，您的应用程序不会崩溃，因为您不会从第一种方法中获得堆栈溢出。

此外，您的第二种方法应该运行快得多，因为您不需要时间来调用许多函数。

谁能解释为什么这个递归函数会崩溃？

Can anyone explain why does this recursive function crash?

c++

recursion

你的第一个方法

你的第二种方法