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

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" 会溢出（我猜）和 returns :

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。它还取决于函数堆栈帧的大小，这又取决于它有多少变量和哪种类型。

在你的例子中，你有两个 long 变量，每个变量可能是 8 个字节。您还有 5 个字节的字符串 "%ld\t"，它可能最终出现在堆栈中，但我不确定。最重要的是，您有两个指向函数 return 地址和前一个堆栈帧的指针的开销，它们在 64 位系统上各为 8 个字节。所以你的函数的堆栈帧大约是 32 个字节左右。也许多一点。所以在 Linux 系统上，我猜你的函数会在大约 200'000 的深度崩溃。

如果这是个问题，请考虑将函数重写为非递归变体。查看 Blaze 答案，了解如何为您的案例完成此操作。正如 andreee 在下面评论的那样：

Additional note: You can increase the stack size under Linux with ulimit -s (also possible: ulimit -s unlimited) and in MSVC you can set the /F compilation flag to increase the stack size of your program. For MinGW, see this post.

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

Does recursive functions have some limitations? eg: how many layers does the function require?

c

recursion

stack-overflow

collatz