Reverse a Stack Using Recursion (Insert at Bottom)

In this last part of the stack tutorial, I’ll show you how to reverse the order of the elements of a stack using only recursion (i.e., no iteration).

Like the implementation of a stack with a queue, the algorithm shown in this article is primarily an exercise. So you may want to try to come up with a solution yourself first.

The Solution – Step by Step

We solve the task using two methods, which I will explain in the following two sections.

1. The reverse() Method

We first implement a reverse() method that proceeds as follows:

Step 1:

As long as elements are on the input stack, we take them off the stack and recursively call the reverse() method. This moves all elements from top to bottom to the call stack:

Step 2:

When exiting the recursion, we move the elements from the call stack back to the destination stack – but in reverse order! The destination stack is the same stack as the input stack that we emptied in step 1.

To do this, we create a method called insertAtBottom() to insert an element at the bottom of a stack. (You’ll see how this method works in the next section.)

Done. The destination stack contains the elements of the input stack in reverse order.

2. The insertAtBottom() Method

But how do we insert elements at the bottom of the stack?

For this purpose, we implement a second method – insertAtBottom(). For this one, too, we exclusively employ recursion.

The following images show the last insertAtBottom() invocation of the previous diagram. That is, the call where the element “peach” is inserted at the bottom of the destination stack, which already contains the elements “apple”, “orange”, and “pear” at that point.

The insertion process consists of three steps:

Step 1:

As long as there are elements on the destination stack, we take them off and call insertAtBottom() recursively. This moves the elements from the destination stack to the call stack:

Step 2:

Once the destination stack is empty, the element to be inserted is placed on the destination stack:

Step 3:

When exiting the recursion, we push the elements from the call stack back onto the destination stack:

With this, the insertAtBottom() method has done its job. The “peach” element has been inserted at the bottom of the destination stack.

Source Code for Reversing a Stack Using Recursion

The Java source code for reversing the stack consists of only a few lines for the two methods. Stack in this code is the small interface of this tutorial series with push(), pop(), peek(), and isEmpty() (Stack.java on GitHub) – not java.util.Stack.

You can find the code in the Stacks class in the GitHub repository:

public class Stacks {

  public static <E> void reverse(Stack<E> stack) {
    if (stack.isEmpty()) {
      return;
    }
    E element = stack.pop();
    reverse(stack);
    insertAtBottom(stack, element);
  }

  private static <E> void insertAtBottom(Stack<E> stack, E element) {
    if (stack.isEmpty()) {
      stack.push(element);
    } else {
      E top = stack.pop();
      insertAtBottom(stack, element);
      stack.push(top);
    }
  }
}

By the way, I chose the class name Stacks analogous to Java utility classes like Collections and Arrays.

Implementation Using an Interface Default Method

A more modern approach is to implement the methods directly in the Stack interface – private helper methods in interfaces have been allowed since Java 9:

public interface Stack<E> {

  // ...

  default void reverse() {
    if (isEmpty()) {
      return;
    }
    E element = pop();
    reverse();
    insertAtBottom(element);
  }

  private void insertAtBottom(E element) {
    if (isEmpty()) {
      push(element);
    } else {
      E top = pop();
      insertAtBottom(element);
      push(top);
    }
  }
}

You won’t find this variant in the GitHub repository because I didn’t want to confuse you with the reverse() method when I introduced the Stack interface at the beginning of the tutorial.

Running Time and Recursion Depth

reverse() empties the stack on the way down and fills it again on the way up – it is the same stack throughout. On every call, insertAtBottom() takes off all elements that are already back on it and then puts them on again. If there are k of them, one call costs O(k). reverse() calls insertAtBottom() once for each of the n elements, and the stack holds 0, 1, 2, up to n − 1 elements in turn. Together, that is n · (n − 1) / 2 moves, so the reversal costs O(n²): twice as many elements take four times as long.

Memory is a problem, too. Every element that is not on the stack at a given moment sits in a frame on the call stack, so the recursion gets about n calls deep. A thread’s call stack is limited: on my Mac with JDK 27 and default settings, Stacks.reverse() still reversed a stack of 20,000 elements; with 25,000 elements, the call aborted with a StackOverflowError.

That is why you would not reverse a stack this way in practice. Since Java 21, reversed() on an ArrayDeque returns a reverse-ordered view of the same elements without copying them. Collections.reverse() reverses a java.util.Stack in O(n). The algorithm in this article remains an exercise in recursion.

Conclusion

This concludes the tutorial series on stacks. If you have read all parts, you have learned how a stack works, which stack implementations exist in the JDK, how to implement stacks yourself in different ways, and – in this article – how to reverse a stack via recursion.