递归函数是否有一些限制？例如：函数需要多少层？

Question

制作了一个递归函数，给出了给定起始数的collatz序列中有多少项，这是代码n=13，例如：

int collatz(long n,long o)
{
    if (n!=1) {
        if(n%2==0)
            return collatz(n/2,o+1);
        else
            return collatz((n*3)+1,o+1);
    } else
        printf("%ld\t",o);
}
void main()
{
    collatz(13,0);
}

功能按预期运行；然而，对于一些整数，例如“n=113383”，有些东西溢出（我猜）并返回：

Process returned -1073741571 (0xC00000FD)   execution time : 4.631 s
Press any key to continue.

请原谅我的非技术性解释，非常感谢！

Answer 1

这里发生的是堆栈溢出。这是因为函数的每次调用都会创建一个新的堆栈帧，如果堆栈帧太多，堆栈的内存就会耗尽。您可以通过使用迭代而不是递归来修复它。

此外，long可能无法保存collatz序列为起始值113383生成的数字（我在MSVC中没有）。改为使用long-long，即至少64位大。总而言之，它可能是这样的：

void collatz(long long n)
{
    long o;
    for (o = 0; n > 1; o++) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n * 3 + 1;
    }
    printf("%ld\t", o);
    return;
}

int main()
{
    collatz(113383);
    return 0;
}

请注意，我们现在有一个for循环，而不是递归。

Answer 2

C标准本身对递归深度没有限制。您可能会导致堆栈溢出，但堆栈大小在不同的环境中是不同的。我认为Windows有1MB，Linux有8MB。它还取决于函数堆栈帧的大小，而堆栈帧的大小又取决于它有多少个变量和类型。

在本例中，您有两个长变量，每个变量可能是8个字节。您还有一个字符串，它是5个字节，可能会在堆栈中结束，但我不确定。除此之外，还有两个指向函数返回地址和前一个堆栈帧的指针的开销，在64位html" target="_blank">系统上每个指针是8个字节。因此，函数的堆栈帧大约是32字节左右。也许再多一点。因此，在Linux系统上，我猜您的函数将在大约200000的深度崩溃。

如果这是一个问题，请考虑将函数重写为非递归变量。看看Blaze的答案，了解如何为您的案例做到这一点。正如andreee在下面评论的那样：

附加说明：您可以在Linux下使用ulimit-s增加堆栈大小（也可以使用ulimit-s unlimited），在MSVC中，您可以设置/F编译标志来增加程序的堆栈大小。有关MinGW，请参阅本文。