Reversing a String with Recursion in Java



reverse string recursion python (12)

import java.util.*;

public class StringReverser
{
   static Scanner keyboard = new Scanner(System.in);

   public static String getReverser(String in, int i)
   {
      if (i < 0)
         return "";
      else
         return in.charAt(i) + getReverser(in, i-1);
   }

   public static void main (String[] args)
   {
      int index = 0;

      System.out.println("Enter a String");
      String input = keyboard.nextLine();


      System.out.println(getReverser(input, input.length()-1));
   }
}

Here is some Java code to reverse a string recursively.

Could someone provide an explanation of how it works?

public static String reverse(String str) {
    if ((null == str) || (str.length() <= 1)) {
        return str;
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

I'm not understanding how this can possibly work.


Answer #1

Because this is recursive your output at each step would be something like this:

  1. "Hello" is entered. The method then calls itself with "ello" and will return the result + "H"
  2. "ello" is entered. The method calls itself with "llo" and will return the result + "e"
  3. "llo" is entered. The method calls itself with "lo" and will return the result + "l"
  4. "lo" is entered. The method calls itself with "o" and will return the result + "l"
  5. "o" is entered. The method will hit the if condition and return "o"

So now on to the results:

The total return value will give you the result of the recursive call's plus the first char

To the return from 5 will be: "o"

The return from 4 will be: "o" + "l"

The return from 3 will be: "ol" + "l"

The return from 2 will be: "oll" + "e"

The return from 1 will be: "olle" + "H"

This will give you the result of "olleH"


Answer #2

run the following and you'll see what's going on:

public class RS {

    public static String reverse(String str) {
        System.out.println("--- reverse --- " + str);
        if ((null == str) || (str.length() <= 1)) {
            return str;
        }
        return add(reverse(str.substring(1)), charAt(str));
    }

    public static char charAt(String s) {
        System.out.println("--- charAt --- " + s);
        return s.charAt(0);
    }

    public static String add(String s, char c) {
        System.out.println("--- add --- " + s + " - " + c);
        return s + c;
    }

    public static void main(String[] args) {
        System.out.println("start");
        System.out.println("result: " + reverse("hello"));
        System.out.println("end");
    }

}

Answer #3

Run the code below - it prints:

Step 0: ello / H
Step 1: llo / e
Step 2: lo / l
Step 3: o / l
Step 3 returns: ol
Step 2 returns: oll
Step 1 returns: olle
Step 0 returns: olleH

Code:

public class Test {

    private static int i = 0;

    public static void main(String args[]) {
        reverse("Hello");
    }

    public static String reverse(String str) {
        int localI = i++;
        if ((null == str) || (str.length()  <= 1)) {
            return str;
        }
        System.out.println("Step " + localI + ": " + str.substring(1) + " / " + str.charAt(0));
        String reversed = reverse(str.substring(1)) + str.charAt(0);

        System.out.println("Step " + localI + " returns: " + reversed);
        return reversed;
    }
}

Answer #4

The call to the reverce(substring(1)) wil be performed before adding the charAt(0). since the call are nested, the reverse on the substring will then be called before adding the ex-second character (the new first character since this is the substring)

reverse ("ello") + "H" = "olleH"
--------^-------
reverse ("llo") + "e" = "olle"
---------^-----
reverse ("lo") + "l" = "oll"
--------^-----
reverse ("o") + "l" = "ol"
---------^----
"o" = "o"


Answer #5

The function takes the first character of a String - str.charAt(0) - puts it at the end and then calls itself - reverse() - on the remainder - str.substring(1), adding these two things together to get its result - reverse(str.substring(1)) + str.charAt(0)

When the passed in String is one character or less and so there will be no remainder left - when str.length() <= 1) - it stops calling itself recursively and just returns the String passed in.

So it runs as follows:

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"

Answer #6
import java.util.Scanner;

public class recursion{
    public static void main (String []args){

    Scanner scan = new Scanner(System.in);
    System.out.print("Input: ");
    String input = scan.nextLine();

    System.out.print("Reversed: ");
    System.out.println(reverseStringVariable(input));

    }public static String reverseStringVariable(String s) {
        String reverseStringVariable = "";

        for (int i = s.length() - 1; i != -1; i--) {
            reverseStringVariable += s.charAt(i);

        }

        return reverseStringVariable;
    }
}

Answer #7

Run it through a debugger. All will become clear.


Answer #8

Best Solution what I found.

public class Manager
{
    public static void main(String[] args)
    {
        System.out.println("Sameer after reverse : " 
                         + Manager.reverse("Sameer"));
        System.out.println("Single Character a after reverse : " 
                         + Manager.reverse("a"));
        System.out.println("Null Value after reverse : "
                         + Manager.reverse(null));
        System.out.println("Rahul after reverse : "
                         + Manager.reverse("Rahul"));
    }

    public static String reverse(String args)
    {
        if(args == null || args.length() < 1 
                                || args.length() == 1)
        {
            return args;
        }
        else
        {
                return "" + 
                               args.charAt(args.length()-1) + 
                               reverse(args.substring(0, args.length()-1));                                  
        }
    }
}

Output:C:\Users\admin\Desktop>java Manager Sameer after reverse : reemaS Single Character a after reverse : a Null Value after reverse : null Rahul after reverse : luhaR


Answer #9

Another Solutions for reversing a String in Java.

Convert you string into a char array using .toCharArray() function.

public static char[] reverse(char in[], int inLength, char out[],
            int tractOut) {

        if (inLength >= 0) {
            out[tractOut] = in[inLength];
            reverse(in, inLength - 1, out, tractOut + 1);
        }

        return null;

    }

Answer #10

You need to remember that you won't have just one call - you'll have nested calls. So when the "most highly nested" call returns immediately (when it finds just "o"), the next level up will take str.charAt(0) - where str is "lo" at that point. So that will return "ol".

Then the next level will receive "ol", execute str.charAt(0) for its value of str (which is "llo"), returning "oll" to the next level out.

Then the next level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "ello"), returning "olle" to the next level out.

Then the final level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "hello"), returning "olleh" to the original caller.

It may make sense to think of the stack as you go:

// Most deeply nested call first...
reverse("o") -> returns "o"
reverse("lo") -> adds 'l', returns "ol" 
reverse("llo") -> adds 'l', returns "oll" 
reverse("ello") -> adds 'e', returns "olle" 
reverse("hello") -> adds 'h', returns "olleh" 

Answer #11

Inline sample;

public static String strrev(String str) {
    return !str.equals("") ? strrev(str.substring(1)) + str.charAt(0) : str;
}




reverse