递归与堆栈实现.为什么当Stack没有时,递归会返回StackOverflow？

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程序的SAME值的递归解决方案成功运行时,意味着Stack解决方案远远超出了递归解决方案的限制.

问题

• 为什么递归解决方案产生的StackOverflowError具有与Stack解决方案相同的迭代次数,但Stack解决方案不会出错？
• 如果Stack解决方案更强大并且使用更少内存,您何时会使用递归解决方案？
• Recursion和Stacks /迭代解决方案之间的基本区别是什么,在选择一个之前必须考虑哪些？

Answer 1

为什么递归解决方案产生的StackOverflowError具有与Stack解决方案相同的迭代次数,但Stack解决方案不会出错？

递归使用您的线程堆栈,并且具有更低的限制.STack使用堆,这个更大但最终会出现OutOfMemoryError.

如果Stack解决方案更强大并且使用更少内存,您何时会使用递归解决方案？

它更慢,更难编写,更容易出错并且使用更多内存.只是限制要高得多.

我看到很多人在Stacks上使用递归,这是因为递归"更容易",虽然效率低得多？(3行代码与本例中的7行).

你还没有预热代码来说哪个更有效率.我会忽略前10,000次迭代或第一次运行时间.

虽然我知道你不能说为什么其他人都使用递归,

通常递归的效率低于使用迭代的效率,但是使用递归时不能轻易地重构某些问题.使用Java中的迭代,95%的问题更有效.

我想质疑它的使用而不是使用它,因为"如果没有充分的理由,其他人都会这样做".

大多数时候人们使用递归,因为它更简单,更快,但它可以用尽堆栈空间,并且在极少数情况下你必须使用Stack或ArrayList,它比Stack更有效.