CODEWITHSUNDEEP
javastringrecursionreverse
user3563455
user3563455

Reputation: 29

Reversing a String using recursion in Java

I am currently getting my head around recursion in Java. Having come across the below code, I can't work out how the recursive method produces the reverse String. Any explanation would be appreciated!

class Backwards {
    String str;

    Backwards(String s) {
        str = s;
    }

    void backward(int idx) {
        if(idx != str.length()-1) {
            backward(idx+1);
        }
        System.out.print(str.charAt(idx));
    }
}


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

        Backwards s = new Backwards("This is a test");
        s.backward(0);
    }
}

Upvotes: 2

Views: 628

Answers (6)

vikash
vikash

Reputation: 455

Try this: 

private static String reverse(String str) {

    if (str == null || str.length() == 0) return "";

    return str.toCharArray()[str.length() - 1] + reverse(str.substring(0, str.length() - 1));
}

hope it will help.

Upvotes: 1

luiscosta
luiscosta

Reputation: 855

Your class:

public class Backwards {
    String str;

    Backwards(String s) {
        str = s;
    }

    String backward(int i) {
        int j = i+1;
        if(i <= str.length())
            return str.charAt(str.length()-i) + backward(j);
        return "";
    }
}

At the main:

public static void main(String[] args) {

    Backwards s = new Backwards("This is a test");
    System.out.println(s.backward(1));

}

Upvotes: 0

Snox
Snox

Reputation: 588

Take a look at the method backward.

void backward(int idx) {
if(idx != str.length()-1) {
    backward(idx+1);
}
System.out.print(str.charAt(idx));

}

It takes an index number and prints the character that is in that index position. Then it calls it self again (that's why it is recursive) but now with the index incremented by 1, because you want to print the next character - backward(idx+1);

Look at the effect of different index numbers:

Backwards s = new Backwards("test");

Index = 0 s.backward(0); output: tset

Index = 1 s.backward(1); output: tse

Index = 2 s.backward(2); output: ts

Upvotes: 0

Dmitry Ginzburg
Dmitry Ginzburg

Reputation: 7461

Look at the backward method. What it does? Step by step:

  1. If that's not last character (index of last character), you're invoking this function at the next character index
  2. Prints out the current character.

So, if we're expanding recursive calls, it would be (for string "hel"):

  1. call backward(0) (which will at the end print 0-th character)
  2. it would call backward(1) (which will at the end print 1-st character)
  3. it would call backward(2) (...)
  4. there recursive call would not be called as 2-nd charater is the last
  5. the third call will end after printing last characted: "l"
  6. the the control would go to the previous call, which would output "e"
  7. control would go to the first backward call, which will output "h"

Visualization: visualizations

So, the final output is "leh", which is what we want.

Upvotes: 1

Denis Kulagin
Denis Kulagin

Reputation: 8906

Take, for example, string "ABCD".

backward(0)
{
  backward(1)  
  {
    backward(2)
    {
      backward(3)
      {
        print D
      }
      print C
    } 
    print B
  }
  print A
}

Upvotes: 1

Mzf
Mzf

Reputation: 5260

If you debug it, with pen and paper, it would be simple to see what is going on.

Basically - it go to the end of the string and start printing char by char from the end to the start.

Upvotes: 2

Related Questions