4

递归函数和内存堆栈之间是否存在直接关系，更多解释请考虑该代码：

public static int triangle(int n) {
    System.out.println(“Entering: n = ” + n);
    if (n == 1) {
        System.out.println(“Returning 1”);
        return 1;
    } else {
        int temp = n + triangle(n - 1);
        System.out.println(“Returning“ + temp);
        return temp;
    }
}​

在此示例中，值 2,3,4,5 将存储在哪里，直到函数返回？请注意，它们将在 LIFO(LastInFirstOut) 中返回，这些是处理内存堆栈的递归的特殊情况，还是它们总是一起出现？

4

4 回答 4

3

是的，递归函数和内存堆栈之间存在直接关系，因为某些具有上限的函数会因为达到堆栈大小限制而使您的程序崩溃，并且函数将覆盖您的部分程序代码（这就是我们所说的堆栈溢出）。

R：递归

一：迭代

first call:
 R  |  I
|_|   |_|

second call:
 R  |  I
|_|   |_|
|_|

third call:
 R  |  I
|_|   |_|
|_|
|_|
.
.
.
n call :
 R  |  I
|_|   |_|
|_|
|_|
.
.
.
|_|

我希望这是有道理的，因为迭代调用函数一旦完成就会被推入堆栈，它会从堆栈中退出，下一次调用将加载一个类似的函数，另一方面，递归函数会加载到堆栈中并调用自身并重新加载每次调用的堆栈，然后当达到停止条件时它们开始关闭（LIFO 最后一个调用第一个出）。

所以现在具体到您的问题，当满足停止条件时，您所说的 n 值将保存在内存中，然后最后一个函数将显示 n，然后退出以将手交给刚刚调用它的函数，这将还显示它自己的 n 值，并且将重复相同的事情，直到调用第一个函数，但是迭代函数将显示计数器 n 的值（仅使用一个变量，我们正在更改其值）。

下面是一篇关于stackoverflow的好文章，

非常深或无限递归主要文章：无限递归堆栈溢出的最常见原因是过深或无限递归。像 Scheme 这样实现尾调用优化的语言，允许特定排序的无限递归——尾递归——在没有堆栈溢出的情况下发生。这是因为尾递归调用不占用额外的堆栈空间。

http://en.wikipedia.org/wiki/Stack_overflow

于 2012-12-12T22:44:05.420 回答
2

假设这是一个 C++ 类方法，对 triangle(n) 的调用会将数据推送到堆栈，如下所示：

  • function code
  • int *returnAddress
  • int n

在函数返回之前不会分配返回值。RS Shaw在此处为调用堆栈维基百科页面 提供了一个很好的图像示例。

每次递归时，此数据都会被推送到调用堆栈的顶部，因此最后一次调用 triangle(n) 的代码将位于顶部。存储的值*returnAddress是内存中结果需要去的地方，以便展开递归。

换句话说，结果本身（例如：三角形（1）为 1，三角形（2）为 3）最终在function code堆栈的某个位置，而不是在内存中的特定命名位置。如果您运行调试器，您应该能够通过在函数代码中returnAddress放置断点来跟踪您的位置。triangle

顺便说一句，这不是递归的特殊情况。这是经典的教科书案例。

于 2012-12-12T23:01:54.883 回答
0

临时变量 n 将在堆栈上，调用 n-1 的参数和返回地址都将在堆栈上。这些都在同一个堆栈上。

于 2012-12-12T22:31:08.133 回答
0

正如 QuentinQK 解释的那样，局部变量 n 将消耗堆栈空间以及函数的返回地址，并且 - 在短时间内 - 返回值和所有移交给递归函数的参数都会消耗堆栈空间。这发生在每个递归级别。因此，这取决于您的递归将进行多深（此函数调用自身的频率）最终将需要多少堆栈以及它是否会爆裂。

出于这个原因，必须有 sim final 条件。在你的例子中，它是这个if (n==1)' condition where the recursion is stopped when that value is reached. It only works along with then-1in the parameter list of the recursive call of三角形`。

但你真正想知道什么？

于 2012-12-12T22:45:38.683 回答