CODEWITHSUNDEEP
javastringrecursionreverse
Bob Sanders
Bob Sanders

Reputation: 4367

Reversing a String with Recursion in Java

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.

Upvotes: 50

Views: 154372

Answers (18)

Sudeepa Pal
Sudeepa Pal

Reputation: 1

`public class reverseString {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    String  brr= "momo";
    int n=brr.length()-1;
    
    string_Finder(brr,n);
     
}
 public static void string_Finder(String arr,int n) {
      
       if(n==0) {
           System.out.println(arr.charAt(0));
       }else {
           System.out.println(arr.charAt(n));
           
           string_Finder(arr,n-1);
       }
       
       }

}`

Upvotes: 0

vikash
vikash

Reputation: 455

Try this:

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

Upvotes: -2

Human
Human

Reputation: 10815

AFAIK, there 2 thing in every recursion function :

  1. There is always a stop condition which is :

    if ((null == str) || (str.length() <= 1)) { return str; }

  2. Recursion use the stack memory which use LIFO mechanism that's why the revert happen.

Upvotes: 0

Fatih Mert Doğancan
Fatih Mert Doğancan

Reputation: 1092

Inline sample;

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

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1500425

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"

Upvotes: 20

Chris Zog
Chris Zog

Reputation: 13

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));
   }
}

Upvotes: 0

Kaustubh
Kaustubh

Reputation: 653

class Test {
   public static void main (String[] args){
      String input = "hello";
      System.out.println(reverse(input));
    }

    private static String reverse(String input) {
        if(input.equals("") || input == null) {
        return "";
    }
    return input.substring(input.length()-1) + reverse(input.substring(0, input.length()-1));
} }

Here is a sample code snippet, this might help you. Worked for me.

Upvotes: 0

mymy
mymy

Reputation: 1

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;
    }
}

Upvotes: -1

Rakesh Chaudhari
Rakesh Chaudhari

Reputation: 3502

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;

    }

Upvotes: 0

Venkata Buchi
Venkata Buchi

Reputation: 1

public class ReverseString{

private static  String reverse(String text, String reverseStr){
    if(text == null || text.length() == 0){
        return reverseStr;
    }
    return reverse(text.substring(1), text.charAt(0)+reverseStr);
}
public static void main(String [] args){
    System.out.println(reverse("hello", "")); //output is "olleh"
}

}

Upvotes: 0

Tom
Tom

Reputation: 4180

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");
    }

}

Upvotes: 0

Vicky K
Vicky K

Reputation: 1

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

Upvotes: 0

David Webb
David Webb

Reputation: 193696

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"

Upvotes: 105

assylias
assylias

Reputation: 328598

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;
    }
}

Upvotes: 3

PATRY Guillaume
PATRY Guillaume

Reputation: 4337

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"

Upvotes: 0

len
len

Reputation: 335

Take the string Hello and run it through recursively.

So the first call will return:

return reverse(ello) + H

Second

return reverse(llo) + e

Which will eventually return olleH

Upvotes: 0

jzworkman
jzworkman

Reputation: 2703

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"

Upvotes: 2

Dave
Dave

Reputation: 4597

Run it through a debugger. All will become clear.

Upvotes: 4

Related Questions