Reversing a String with Recursion in Java

Question

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    lt   1             return str            return reverse str substring 1     str charAt 0       I m not understanding how this can possibly work

User · Accepted Answer

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"

User · Answer

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     lt   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

User · Answer

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   - gt  returns  o  reverse  lo   - gt  adds  l   returns  ol   reverse  llo   - gt  adds  l   returns  oll   reverse  ello   - gt  adds  e   returns  olle   reverse  hello   - gt  adds  h   returns  olleh

User · Answer

Try this   public static String reverse String str       return  str    null    str length    0    str   reverseString2 str substring 1   str charAt 0

User · Answer

Because this is recursive your output at each step would be something like this     Hello  is entered  The method then calls itself with  ello  and will return the result    H   ello  is entered   The method calls itself with  llo  and will return the result    e   llo  is entered   The method calls itself with  lo  and will return the result    l   lo  is entered   The method calls itself with  o  and will return the result    l   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

User · Answer

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

User · Answer

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

User · Answer

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    lt  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

User · Answer

import java util     public class StringReverser      static Scanner keyboard   new Scanner System in       public static String getReverser String in  int i             if  i  lt  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

User · Answer

Inline sample   public static String strrev String str        return  str equals       strrev str substring 1     str charAt 0    str

User · Answer

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

User · Answer

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

User · Answer

Run it through a debugger  All will become clear

User · Answer

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

User · Answer

AFAIK  there 2 thing in every recursion function      There is always a stop condition which is        if   null    str      str length    lt   1               return str           Recursion use the stack memory which use LIFO mechanism that s why the revert happen

User · Answer

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  gt   0                out tractOut    in inLength               reverse in  inLength - 1  out  tractOut   1                      return null

User · Answer

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    lt   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

[java] Reversing a String with Recursion in Java

Examples related to java

Examples related to string

Examples related to recursion

Examples related to reverse