如何让更多的内存和避免大量递归堆栈溢出？

Question

我正在测试执行大量递归调用的算法的时间。我的程序在约128k的递归调用中死亡，这只需要0.05秒。我想让更多的记忆在我的分析中有更长的时间。我正在运行linux并使用gcc。是否有系统调用，或环境变量，或gcc标志或包装，或什么？

Answer 1

在Linux下gcc没有堆栈大小编译器选项。不过this text discusses how to set the stack size on Linux.使用ulimit命令。

Answer 2

试着组织你的递归函数使其拥有tail recursion。

也就是说，确保递归函数的最后一个操作是递归调用。通过这样做，编译器可以将其优化为简单的迭代。

尾递归会帮助你，因为迭代将显着减少使用的堆栈空间。

使用尾递归，您通常会将您的值一直递增，一次计算1步。所以当递归完成时，所有需要做的就是返回。

---

例子：

转换下面的代码：

unsigned fact(unsigned x) 
{ 
    if(x == 1) 
    return 1; 

    //--> Not tail recursive, multiply operation after the recursive call 
    return fact(x-1) * x; 
} 

要这样：

unsigned fact(unsigned x) 
{ 
    return tail_fact(x, 1); 
} 

unsigned tail_fact(unsigned x, unsigned cur_val) 
{ 
    if(x == 1) 
    return cur_val; 

    return tail_fact(x-1, x * cur_val); 
} 

Answer 3

你有三个选择：

1. 重写程序以使其不递归。这是最好的，但并不总是可能的。

2. 重写程序以使用单独的堆栈来存储执行状态。这样您保留了递归性质，但不再使用系统堆栈来存储递归算法状态数据。

3. 调整环境以推迟不可避免的。 Visual   C++具有堆栈大小的链接器设置。几乎可以肯定gcc也有一个。

Answer 4

看看setrlimit()：

RLIMIT_STACK
这是最初的线程的堆栈的最大大小，以字节为单位。该实现不会自动增加超过此限制的堆栈。如果超出此限制，则应为该线程生成SIGSEGV。如果该线程被阻塞SIGSEGV，或该方法忽略或捕捉SIGSEGV并没有作出安排，使用备用堆时，产生前它的SIGSEGV配置应被设置成SIG_DFL。

Answer 5

虽然其他答案谈谈如何要么避免递归完全，或如何使用尾递归，或如何简单地设置一个较大的堆栈大小，我认为完整性，这是值得考虑的内存使用模式（以回答“如何让更多的内存...在很多递归上”）。

出于习惯，许多程序员将分配缓冲区递归函数里面，并重新分配新的缓冲区，当函数被递归调用：

int recursive_function(int x) 
{ 
    if (1 == x) 
     return 1; 
    int scratchpad[100]; 
    ... // use scratchpad 
    return recursive_function(x-1) + scratchpad[x-1]; 
} 

由于这是一个一次性的样品，我不会打扰担心关于无效输入（负值，大于100的值），我会假设有人提出关于编程的问题要么知道如何做，要么足够聪明以找出答案。

重要这里的一点是，scratchpad堆栈每一次recursive_function()被称为的占用400个字节（32位机器上，800个字节的64位计算机上），所以如果recursive_function()被递归调用100倍，然后40000字节（或80000个字节的64位计算机上）的堆栈空间被用于缓存，它很可能，你可以修改函数重用每次调用同一个缓冲区：

int recursive_function(int x, int* buffer, int buffer_length) 
{ 
    if (1 == x) 
     return 1; 
    ... // use buffer (and buffer_length to avoid overflow) 
    int temp_value = buffer[x-1]; 
    return recursive_function(x-1, buffer, buffer_length) + temp_value; 
} 

当然你可以改为使用std::vector，它为你处理一些细节，以防止内存泄漏和缓冲区溢出（并且，对于记录，将数据保存在堆上[见脚注]，这意味着它可能会使用较少的堆栈空间）。

40k甚至80k可能看起来不多，但事情可以加起来。如果该函数没有其他堆栈分配变量，那么这可以支配堆栈空间（也就是说，如果它不是用于缓冲区占用的额外空间，则可能可以调用该函数的次数）。

这看起来很明显，即使在非递归函数中也是如此，即but it does come up。另外，缓冲区并不总是与数组一样明显。例如，它们可能是字符串或对象。

---

脚注：STL容器，比如数组不一定提上堆的所有数据。他们实际上采用模板参数来指定使用的内存分配;它只是默认使用的分配器将数据放在堆上。很明显，除非你指定一个以某种方式将数据放入堆栈的分配器，否则最终结果将是相同的：使用STL容器可能比使用堆栈分配的数组或对象使用更少的内存。

我说“可能”，因为虽然数据保存在堆（或其他地方），但容器只能通过它在内部保存的指针访问该数据，如果容器在堆栈上，那么这些指针将驻留在堆栈和这些指针占用空间。因此，一个或两个元素std::vector实际上可能占用堆栈上的空间多于对应的数组。