[Solved] 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 performs better than the first version of the method you write to reverse an ArrayList in Java. It's also one of the recommended best practices to prefer the library method instead of writing your own, as advised by great Joshua Bloch in Effective Java. There are so many benefits of using library methods like 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, maybe 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 like 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 the base case from where the 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 the base case and starts winding down, we end up with all the elements in the reverse order. To accommodate that, we have used the addAll() method of java.util.Collection class.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms courses like these best Data Structure and Algorithms courses to fill the gaps in your understanding.

Btw, recursive algorithms are quite popular in programming job interviews. You will often find recursive problems like the Fibonacci series, All permutations of String, or reverse String in place on written tests, telephonic rounds, 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 solutions for few more recursive problems. It's one of the best books for practicing coding problems, especially from a programming interview perspective.

Java Program to Reverse a List using Recursion? Example

Here is our sample Java program to reverse a List in Java. It demonstrates both the practical approaches using the Collections.reverse() method and the 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 the program goes Out Of Memory 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 like Vector, LinkedList, CopyOnWriteArrayList, or ArrayList in Java in production. The recursive algorithm is just for educational purposes. There is a task for you, try to reverse the list in place using an iterative algorithm, for the solution you can check here.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview: 189 Problems and Solutions
Grokking the Coding Interview: Patterns for Coding Questions


Need more questions for Practice? Here they are

• How to find all permutations of a String in Java? (solution)
• Write a program to find the top two numbers from an integer array? [solution]
• How to find duplicate words in Java String? (solution)
• How to reverse a String in place in Java? (solution)
• Top 20 Amazon and Google Interview Questions? (list)
• How to implement the Quicksort algorithm in Java? [solution]
• 7 Best courses to learn Data Structure and Algorithms (courses)
• 10+ Algorithms and Programming Courses to Crack Interviews (courses)
• 10 Books to learn Data Structure and Algorithms (books)
• How to check if a String is a Palindrome in Java? (solution)
• 10 Data Structure and Programming Courses to Crack Interviews (courses)
• How to find duplicate elements in an array? (solution)
• 20+ binary tree questions from coding interviews (questions)
• How do you print prime numbers up to a given number? (solution)
• 25 systems design questions from interviews (questions)
• How to check if an array contains a number in Java? [solution]
• How to print the Fibonacci series without recursion? (solution)
• 10 Free Data Structure and Algorithms Courses for beginners (free courses)
• How to find the highest and lowest element in the unsorted array? [solution]
• How to find the largest prime factor of a number in Java? (solution)
• How to count the number of words in a given String? (solution)

Thanks for reading this article so far. If you like these String programming coding problems then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P.S. - If you are preparing for Programming Job Interview and you need more such questions, can check the Data Structures and Algorithms Bootcamp by Jonathan Rasmusson course on  Udemy to refresh your knowledge in quick time.