How to Reverse an ArrayList in Java using Recursion - Example Tutorial

If you ever need to reverse a List in Java e.g. ArrayList or LinkedList, you should always use the Collections.reverse() method. It's safe and tested and probably perform better than the first version of the method you write toreverse an ArrayList in Java. It's also one of the recommended best practice to prefer library method instead of writing your own, as advised by great Joshua Bloch in Effective Java. There are so many benefits of using library method e.g it was written by experts, thoroughly and open source tested and more actively maintained. Anyway, if you have been asked to write a function to reverse a List using recursion in Java, may be as part of your homework, assignment or during an interview, then you are in the right place. In this tutorial, I'll show you how to reverse an ArrayList of String using recursion. You can use this technique to reverse any type of List e.g. List of Integer, List of String or List of your own custom objects.

In a recursive algorithm, a function calls itself to do the job. After each pass problem becomes smaller and smaller until it reaches to the base case from where programmer starts to wind down. The base case is very important for a recursive algorithm because without this your program will never finish and you will quickly run out of memory in both Stack and Heap.

In order to reverse a List using recursion our base case is a list of one element. If your list contains one element then the reverse of that list is the list itself, so just return it. Now, on each pass we need to add the last element on the list into a new list called reversed. Once the program reaches to base case and starts winding down, we end up all the elements in the reverse order. To accommodate that, we have  used the addAll() method of java.util.Collection class.

Btw, recursive algorithms are quite popular on programming job interviews. You will often find recursive problems like Fibonacci series, All permutations of String, or reverse String in place on written test, telephonic round or the face-to-face round of Java interviews.

If you are seriously preparing for a programming job, this is the one topic you cannot ignore.  You can also check Cracking the Coding Interview book, which contains more than 189 Coding problems and solution for few more recursive problems. It's one of the best books for practicing coding problems especially from programming interview perspective.

Java Program to Reverse a List using Recursion

Here is our sample Java program to reverse a List in Java. It demonstrates both practical approach using Collections.reverse() method and algorithmic approach by using recursion. Btw, a recursive method is quite expensive here as for each recursive call a new list is created, which is held in memory until the list is completely sorted. For a huge list of million elements, this can easily make program goes OutOfMemory because the list will be created in the heap space.

There is also a risk of StackOverFlow because each method call will take some space on stack memory. Instead of using recursion here, you can use iteration to sort the list in place, which will just need a variable to hold one value to swap the first element to last and so on. The algorithm is similar to what we have learned while reversing an array in place in Java.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


/*
 * Java Program to demonstrate how to reverse a List.
 * In this example, you will see two ways to reverse a List,
 * first, using Collections.reverse() method and second
 * by writing your own method using recursion. 
 */
public class TestSolution {

    public static void main(String args[]) {

        List<String> books = new ArrayList<>();
        books.add("Beautiful Code");
        books.add("Clean Code");
        books.add("Working Effectively with Legacy Code");

        System.out.println("Original order of List: " + books);

        // Easy way to reverse a List in Java, use Collections.reverse()
        // method, use this to reverse ArrayList or LinkedList in
        // production
        Collections.reverse(books);

        System.out.println("The reversed List: " + books);

        // Now, let's try to reverse a List using recursion
        List<String> output = reverseListRecursively(books);
        System.out.println("Reversed list reversed again: " + output);
    }

    /**
     * A recursive algorithm to reverse a List in Java
     *
     * @param list
     * @return
     */
    private static List<String> reverseListRecursively(List<String> list) {
        if (list.size() <= 1) {
            return list;
        }

        List<String> reversed = new ArrayList<>();
        reversed.add(list.get(list.size() - 1)); // last element
        reversed.addAll(reverseListRecursively(list.subList(0, list.size() - 1)));
        return reversed;
    }

}

Output
Original order of List: [Beautiful Code, Clean Code, Working Effectively with Legacy Code]
The reversed List: [Working Effectively with Legacy Code, Clean Code, Beautiful Code]
Reversed list reversed again: [Beautiful Code, Clean Code, Working Effectively with Legacy Code]

That's all about how to reverse a list in Java. You have seen 2 ways to reverse the list, first by using the Collections.reverse() method, which you should use to sort any List implementation e.g. Vector, LinkedList, CopyOnWriteArrayLis, or ArrayList in Java in production. The recursive algorithm is just for educational purpose. There is a task for you, try to reverse the list in place using an iterative algorithm, for the solution you can check here.