时间戳

首页 > 解决方案 > 递归函数有一些限制吗？例如：该功能需要多少层？

c - 递归函数有一些限制吗？例如：该功能需要多少层？

问题描述

制作了一个递归函数，它给出了给定起始编号的 collat​​z 序列中有多少项，这是示例的代码 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.

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

标签： crecursionstack-overflowcollatz

解决方案

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

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

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

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

推荐阅读