Reverse a string with recursion

Photo by Shahadat Rahman on Unsplash

One of the first things you need to know when learning programming is the recursion algorithm. Recursion is basically a function that keeps calling itself until it reaches a base case. A base case is a simple condition for the function to return a value.

Most beginner programmers like myself would find it hard to wrap their heads around the idea of recursion since it requires another way of thinking. Let’s take a look at one of the most common applications of recursion — reverse a string. Below is a Java function to describe the implementation of reversing a string using recursion.

public static String reverse(String str) {
    
    // base case
    if (str.isEmpty()) {
        return str;
    }
    
    // recursive cases
    return reverse(str.substring(1)) + str.charAt(0);
}

Input: “Hello” => Output: “olleH”

The base case is that if the string is empty, return it. Else, call the same function with a substring starting from index 1 of the original string as a parameter.

Let’s continue with the above example.

string = “Hello”

The string is not empty, skip the base case. Call the function itself instead — reverse(str.substring(1)) + str.charAt(0).

1st call: 'ello'  +   'H'
2nd call: 'llo'   +   'e'
3rd call: 'lo'    +   'l'
4th call: 'o'     +   'l'
5th call: ''      +   'o' 

Keep calling the same function until the string is empty. Now we can return it.

1st return: ""     +   'o'  =   "o"
2nd return: "o"    +   'l'  =   "ol"
3rd return: "ol"   +   'l'  =   "oll"
4th return: "oll"  +   'e'  =   "olle"
5th return: "olle" +   'H'  =   "olleH"

That’s it. Recursion is not an easy concept to understand, so keep practicing.