java - 用递归方法解决 stackoverflowException

Question

我为我的作业编写了一种方法，用于通过递归计算整数数组的所有排列。 (我正在尝试实现回溯算法)。但计算超过 7 个数字的前突变时会导致 StackOverflowException 。我不知道如何解决这个问题。如果我使用itration，它仍然实现回溯吗？

代码:

solve(0, arr, currentS);
//****************

private static void solve(int i, ArrayList<Integer> arr, int[] currentS) {
    if (i == arr.size()) {
        for (int j : currentS) {
            System.out.print(j + ",");
        }

        System.out.println();

        currentS[i-1] = 0;
        solve(i - 2, arr, currentS);

    } else {
        int x = nextValue(i, currentS, arr);
        if (x != -1&&travers.isCompatible(arr, currentS.clone())) {
            currentS[i] = x;
            solve(i + 1, arr, currentS);
        }
        else if((i != 0))
        {
            currentS[i] = 0;
            solve(i - 1, arr, currentS);
        }
    }
    return;
}

nextValue() 是检查树节点的子节点中不存在重复的方法，或者从根到每个叶子不存在重复的方法

异常(exception):

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList.get(Unknown Source) ....

Answer 1

并不是要让你失望，但我对这个问题的解决方案有 14 行代码。也许你应该重新考虑你的方法。

提示:您实际上不需要单独的列表来保存当前排列，您可以直接排列(和取消排列)数组。这意味着您不需要任何代码来检测列表中的重复项。

但是您的问题可能更基本。维基百科writes :

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly-designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.

(强调我的)。我没有看到任何尝试保证能够达到 i == arr.length 。有时我在递归时会变小，有时会变大，很可能它会简单地振荡而不会达到基本情况。换句话说，您的程序永远不会终止，但由于每个递归步骤都需要额外的内存，因此您会耗尽堆栈空间。