Recursion vs. Stack implementation. Why does recursion return StackOverflow when Stack does not?

Question

The basis for this question:

I will graduate this summer with a CS degree and not once have I had a professor stress the importance of a Stack. I have, however, had multiple projects that were all focused on the use of recursion. I found recursion useful and exciting and I use it a lot in my personal projects.

I recently went to a job interview and the interviewers were very disappointed in recursive solutions to their problems. They wanted Stack solutions. I did a bunch of research but I'm still not sure when to use which.

Given the following demonstration:

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 + " ");
        }
    }
}

Both solutions complete in around 200 ms. Changing the value of x by adding a zero: x = 100000 gives me a StackOverflowError (on the recursive method).

When I comment out the recursive solution with the SAME value of x the program runs successfully, meaning the Stack solution works far beyond the limits of the recursive solution.

Questions

• 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?
• When would you use a recursive solution if the Stack solution is more capable and uses less memory?
• What are the fundamental differences between Recursion and Stacks/iterative solutions that one must consider before choosing one over the other?

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?

Recursion uses you thread stack and that has a much lower limit. The STack uses the heap and this is much larger but it will OutOfMemoryError eventually.

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

It is much slower, harder to write, more error prone and uses more memory. It is just that the limit is much higher.

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).

You haven't warmed up the code to say which is more efficient. I would ignore the first 10,000 iterations or the first second of running time.

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

Usually recursion is less efficient than using iteration, however some problems cannot be easily refactored to use recursion. 95% of problems are much more efficient using iteration in 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.

Most of the time people use recursion because it is simpler, faster, but it can run out of stack space, and in very rare cases you have to use a Stack or an ArrayList which is more efficient than a Stack.