java - 为什么我的代码会导致 java 中的堆栈溢出错误？它最终应该终止。 for循环版本不会导致错误

Question

更新 10/23/2014:我认为递归函数基本上是一个 void 函数，所以返回后不需要更多的工作，它应该等同于尾递归版本。而且它不应该导致堆栈溢出。我其实也试过尾递归非空返回类型，它仍然导致堆栈溢出错误。我想即使它是尾递归的，它仍然取决于编译器解释器如何实现它。

相同代码的 for 循环版本不会导致堆栈溢出错误。但是下面的代码(递归版本)确实如此。本质上他们应该做同样的事情。异常错误出现在循环 7000 (i=7000) 附近。

我很好奇为什么递归版本会导致错误，而 for 循环版本不会。我有一些怀疑，但不确定。

//recursive version, overflow

public class Solution {
    int n, low = -1, profit = 0;
    int[] a;

    public int maxProfit(int[] prices) {
        n = prices.length;
        if (n == 0 || n == 1)
            return 0;
        a = prices;
        maxProfit(1);
        return profit;
    }

    public void maxProfit(int i) {

        if (i == n - 1) {
            if (low != -1 && a[i - 1] <= a[i])
                profit += a[i] - low;
            return;
        }
        if (a[i - 1] < a[i] && low == -1) {
            low = a[i - 1];
        }
        if (a[i - 1] > a[i] && low != -1) {
            profit += a[i - 1] - low;
            low = -1;
        }
        //System.out.print(i+",");
        maxProfit(i + 1);
    }

    public static void main(String[] args) {
        Solution sl = new Solution();
        // int[] a = { 1, 9, 6, 9, 1, 7, 1, 1, 5, 9, 9, 9 };
        // int[] a = { 4, 4 };
        // int[] a = { 3, 2 };
        // int[] a = { 1, 2, 3, 4, 3 };
        // int[] a = { 3, 2, 1, 0, 4, 5, 6, 7, 10, 4, 9, 7 };
        int[] a = new int[100001];
        for (int i = 0; i < 100001; i++) {
            a[i] = 100000 - i;
        }
        System.out.println();
        System.out.println(sl.maxProfit(a));
    }
}

Answer 1

到目前为止还没有人真正解释发生了什么......

当你调用一个函数时，它不仅仅是去那里——它必须准确地记住你在哪里以及你所有的变量是什么，这样它才能在你的函数返回时返回到那个确切的位置。

它通过将当前状态存储在堆栈上(沿一个方向建立的内存区域)来实现这一点。每次您的应用程序递归时，堆栈都会变得更深，需要更多内存。

堆栈溢出是指堆栈变得太大以至于溢出分配给它的内存。

您的循环版本每次迭代不需要任何额外的内存，因为它不必记住何时返回——它只是绕着圈子跑，并且可以永远这样做。

抱歉，如果这不是您要问的。