recursion - 递归函数和内存栈是什么关系？

Question

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

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) 中返回，这些是处理内存堆栈的递归的特殊情况还是它们总是在一起？

Answer 1

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

R:递归

一:迭代

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

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

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

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

所以现在具体到您的问题，当满足停止条件时，您所说的 n 值将保留在内存中，然后最后一个函数将显示 n，然后退出以将手交给刚刚调用它的函数也显示它自己的 n 值，同样的事情将重复，直到第一个函数被调用，但是迭代函数将显示一个计数器 n 的值(只使用了一个变量，我们正在改变它的值)。

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

Very deep or infinite recursion Main article: Infinite recursion The most common cause of stack overflow is excessively deep or infinite recursion. Languages like Scheme, which implement tail-call optimization, allow infinite recursion of a specific sort—tail recursion—to occur without stack overflow. This works because tail-recursion calls do not take up additional stack space.

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