java - 递归与堆栈实现。为什么递归返回 StackOverflow 而 Stack 不返回？

Question

本题依据:

我将在今年夏天毕业并获得 CS 学位，而且教授从未强调过 Stack 的重要性。然而，我有多个项目都专注于递归的使用。我发现递归很有用且令人兴奋，并且在我的个人项目中经常使用它。

我最近去参加了一次工作面试，面试官对他们问题的递归解决方案感到非常失望。他们想要 Stack 解决方案。我做了很多研究，但我仍然不确定何时使用哪个。

给出以下演示:

public class TestCode {

    static long startTime = 0;
    static long stopTime = 0;
    static long totalTime = 0;

    public static void main(String[] args) throws IOException {
        int x = 10000;
        startTime = System.currentTimeMillis();
        recursiveMethod(x);
        System.out.println();
        stopTime = System.currentTimeMillis();
        totalTime = stopTime - startTime;
        System.out.println(totalTime);
        System.out.println();

        startTime = System.currentTimeMillis();
        stackMethod(x);
        System.out.println();
        stopTime = System.currentTimeMillis();
        totalTime = stopTime - startTime;
        System.out.println(totalTime);
        }

    public static void recursiveMethod(int a){
        if(a >= 0){
            recursiveMethod(a - 1);
            System.out.println("Recursion: " + a + " ");
        }
    }

    public static void stackMethod(int a){
        Stack<Integer> myStack = new Stack<Integer>();
        while(a >= 0){
            myStack.push(a);
            a--;
        }
        while(myStack.isEmpty() == false){
            a = myStack.pop();
            System.out.println("Stack: " + a + " ");
        }
    }
}

两种解决方案都在大约 200 毫秒内完成。通过添加零来更改 x 的值:x = 100000 给我一个 StackOverflowError(在递归方法上)。

当我用 x 的相同值注释掉递归解决方案时，程序成功运行，这意味着 Stack 解决方案的工作远远超出了递归解决方案的限制。

问题

• 为什么递归解决方案在迭代次数与 Stack 解决方案相同的情况下会产生 StackOverflowError，但 Stack 解决方案不会出错？
• 如果 Stack 解决方案功能更强大且使用的内存更少，您什么时候会使用递归解决方案？
• 在选择递归和堆栈/迭代解决方案之前必须考虑的根本区别是什么？

Answer 1

Why is the recursive solution yielding a StackOverflowError with the same number of iterations as the Stack solution, but the Stack solution does not error out?

递归使用你的线程堆栈，并且有一个低得多的限制。 STack 使用堆，这要大得多，但最终会出现 OutOfMemoryError。

When would you use a recursive solution if the Stack solution is more capable and uses less memory?

它更慢、更难编写、更容易出错并且占用更多内存。只是上限高了很多。

I see many people using recursion over Stacks, is this because recursion is "easier" although far less efficient? (3 lines of code vs. the 7 in this example).

您还没有预热代码来说明哪个更有效。我会忽略前 10,000 次迭代或运行时间的第一秒。

While I know you cannot say why everybody else uses recursion,

通常递归比使用迭代效率低，但是有些问题不能轻易重构为使用递归。 95% 的问题在 Java 中使用迭代会更有效。

I'd like to question it's use rather than use it because "everybody else does" if there's not a good reason for it.

大多数时候人们使用递归，因为它更简单、更快，但它可能会耗尽堆栈空间，在极少数情况下，您必须使用比堆栈更高效的堆栈或数组列表。