递归&&给定堆栈内存挑战

Question

我研究了 C 编程的递归，并且我对递归函数执行时递归调用的堆栈内存处理有一个担忧。具体来说，事情是如何在堆栈内存上完成的..

假设给出的递归函数如下：

void recursion(int num) {


    if (num == 1 || num < 1 )
     {
       return ;
      }
     recursion(num/10);
}

假设 num 作为函数的输入 100，并且我们有堆栈 给定的内存范围为 0 - 100 字节，这意味着隐式给出了整数数组，其大小从索引 0 到 100。假设给定 stackmemory[100]，递归函数对其进行处理

现在我关心的是如何通过递归调用继续跟踪我没有达到堆栈内存的最大值？没有达到叠加流程.. 这意味着我如何确定在下一个递归调用时有足够的堆栈内存用于下一个递归调用，并且堆栈内存上是否没有足够的空间 然后递归将停止。

我怎样才能继续跟踪它？我正在考虑使用指针来保存/存储一些指针并以某种方式与“&”相关以解决该问题。

有任何想法或任何帮助来解决这个问题吗？顺便说一下，可以编辑原始函数（上面给出的递归函数）并添加任何其他附加函数..

谢谢。

void recursion(int num) {


    if (num == 1 || num < 1 )
     {
       return ;
      }
     recursion(num/10);
}

Answer 1

假设 num 为函数的输入 100，并且堆栈内存为 0 - 100 字节

这没有任何意义。在您的除法算法中，值 100 与使用的堆栈量无关。堆叠的内容（根据“调用约定”）是返回地址和取决于目标的各种寄存器的状态，此外参数也可能被堆叠。

int

参数每次调用将占用 4 个字节。

这里的函数将有 n=100，然后 n=10，最后 n=1，所以 3 个函数调用。根据目标的不同，每次调用您可能最终会（大约）堆叠 4 到 16 个字节。

不存在“大小为 100 的隐式整数数组”。

另请注意，在最佳情况下，递归可以得到优化。例如，如果我们向您的函数引入副作用（这样它就不会得到 100% 优化，而目前它会这样做），那么至少最新的 gcc/x86 设法删除递归调用并将其替换为循环。 （所谓的尾部调用优化。） https://godbolt.org/z/eP1s6E9Th 请注意，程序集不包含任何

call recursion

指令。整个事情可能会内联到调用者代码中。

事实上，这个特定的示例非常简单，以至于在包含调用者代码时，它甚至没有内联函数，而是用 3 个 printf 语句分别打印 100、10 和 1 来替换整个内容：https://godbolt.org /z/cGjaEEnfT

对于更复杂的代码，编译器可能无法对其进行优化，这时就会发生堆栈溢出和不必要的缓慢执行。

现在我关心的是如何通过递归调用继续跟踪我没有达到堆栈内存的最大值？

你不能这样做。它将涉及内联汇编程序，该汇编程序在第一次调用之前访问堆栈指针，然后在每个递归调用中检查它。堆栈溢出的可能性是 C 中的递归被视为危险和不良实践的主要原因之一。

它可能可以通过一些非常hackish的方式在C中实现，例如剖析

jmp_buf

变量的内容，然后使用

setjmp

/

longjmp

作为故障保险。我不推荐。

有任何想法或任何帮助来解决这个问题吗？

是的 - 不要使用递归。在您能想到的 99% 的算法中，递归几乎肯定是错误的解决方案。不仅因为它很危险，还因为它很慢并且通常难以阅读。