-3

What's the most efficient way to print a string backwards using recursion in java? If youre given this header:

public void printBackwards(String s)
flowinwind
  • 69
  • 1
  • 11
  • Are you asking how to implement or purely efficiency? – OneCricketeer Nov 17 '15 at 02:56
  • If by 'efficient' you mean raw performance then this question will be impossible to answer. Java is a language specification; the most efficient way to reverse a string will depend on the implementation of that specification, the platform you are operating on and a host of other factors. Luckily, in 99.99% of cases you can ignore all that and use the most elegant solution rather than the most efficient. – sprinter Nov 17 '15 at 02:57
  • Is the answer supposed to be Big-O notation? – OneCricketeer Nov 17 '15 at 03:02
  • @3kings - an index isn't needed, you can write the method as stated – OneCricketeer Nov 17 '15 at 03:03
  • SO is not a code writing service. Please make an attempt at solving the problem on your own and ask for help if you get stuck. – Mark Sholund Nov 17 '15 at 03:29
  • Possible duplicate of [Reverse a string in Java](http://stackoverflow.com/questions/7569335/reverse-a-string-in-java) – diziaq Nov 17 '15 at 03:47

3 Answers3

2

Efficiency-wise the most efficient way is to not use recursion.

The iterative approach (loop-backwards over the string and print the characters) is linear, O(N), where N is the length of the string.

Since you ask about the recursive solution, though, it is quadratic, O(N^2) for time-complexity since N characters are printed and N substrings are made for each function call. (N-1 characters are copied into memory each time). 

  public void printBackwards(String s) {
      if (!s.isEmpty()) {
          int endPos = s.length() - 1;
          System.out.print(s.charAt(endPos));
          printBackwards(s.substring(0, endPos));
      }
  }
OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
  • You beat me to it >:-( :) – hyper-neutrino Nov 17 '15 at 03:10
  • I'm not the downvoter, but this has `O(N^2)` time complexity because `substring` has to copy characters. It would have been linear, before they "improved" the implementation of `String`. – Paul Boddington Nov 17 '15 at 03:19
  • 1
    @PaulBoddington An iterative method would actually be much better! – hyper-neutrino Nov 17 '15 at 03:20
  • @PaulBoddington - Nice catch. Updated. I have a tendency to overlook standard methods :\ I suppose we got downvoted for helping with an assignment – OneCricketeer Nov 17 '15 at 03:24
  • I think that's probably it. To be honest, I'm not entirely sure the space complexity is linear either. If you invoke method on `"String"`, the substrings `"Strin"`, `"Stri"`, `"Str"`, `"St"` and `"S"` are all created. Doesn't this require `O(n^2)` space? I'm not actually sure on that one. – Paul Boddington Nov 17 '15 at 03:27
  • @PaulBoddington - I'm not sure either, really. Is storing `"String"` itself considered 1 unit of storage? With the definition of `N` being the length of the string, it isn't... So I'm fine with admitting both are quadratic. – OneCricketeer Nov 17 '15 at 03:32
  • I think the amount of storage is proportional to the length of the string, not just one unit. Because this whole thing is recursive, all the subtrings remain in memory until the very end (I think). But I'm not 100% sure. If you just get rid of the bit about space complexity I'll upvote this. – Paul Boddington Nov 17 '15 at 03:34
  • 1
    @PaulBoddington - I'd assume parameters stay in the call stack for when the function returns, so you are probably correct. – OneCricketeer Nov 17 '15 at 03:47
0

Since you want recursion, I'll give you a hint (as this is a question in your class):

Print the last character first. How would you print it forwards recursively? Now just go backwards!

Hover to reveal code :)

public void printBackwards(String s) {
if (s.length() == 0) return;
System.out.print(s.charAt(s.length() - 1);
printBackwards(s.substring(0, s.length() - 1);
}

hyper-neutrino
  • 5,272
  • 2
  • 29
  • 50
0

The most efficient way using recursion is like this:

static void printBackwards(String s)
{
    printBackwards(s, 0, s.length());
    System.out.println();
}

static void printBackwards(String s, int start, int end)
{
   if ((end-start)<2)
   {
       if (end>start)
       {
          System.out.print(s.charAt(start));
       }
       return;
   }
   int mid = start + (end-start)/2;
   printBackwards(s, mid, end);
   printBackwards(s, start, mid);
}

This is more efficient than the other answer, because it doesn't allocate a whole bunch of new strings and only uses O(log N) stack...

But, really you don't need recursion to print a string backwards.

NOTE: If this is homework and you hand this in, your prof will probably know that you didn't write it :)

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87