Write a program to reverse a string

Here we will swap first and last characters and recur for remaining substring. If string has only one character it is already reversed, this will make the base condition.

package com.cb.recursion;

/*
 * Recursion
 * */
public class ReverseAString {

    // abc abcd
    public static String reverse(String s, int startIndex, int endIndex) {
        if (startIndex >= endIndex)
            return s;
        String s1 = swap(s, startIndex, endIndex);
        return reverse(s1, startIndex + 1, endIndex - 1);
    }

    private static String swap(String s, int i, int j) {

        char[] chars = s.toCharArray();

        char c = chars[i];
        chars[i] = chars[j];
        chars[j] = c;

        return new String(chars);
    }

    public static void main(String[] args) {

        String s = "abc";
        System.out.println(reverse(s, 0, s.length() - 1));

        String s1 = "abcd";
        System.out.println(reverse(s1, 0, s1.length() - 1));
    }
}

cba
dcba

In every fn call, we are increasing start index and decreasing end index, that means fn is called n/2 or n/2+1 times for a string of size n; so Time Complexity is O(n).

We are also storing startIndex and endIndex in every call, so Space Complexity is 2n or O(n).