• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Jj Roberts
  • Tim Holloway
  • Piet Souris
Bartenders:
  • Himai Minh
  • Carey Brown
  • salvin francis

Recursive Method- String Reversal

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


I'm struggling with line 18. So


s is the parameter variable in which substring method acts upon. The first parameter of s.substring has the value e and I'm not so sure about the second parameter. Could someone explain, I'm not sure how this simplifies after each recursive call?


reverseString(...) this is where the recursion begins and substring method takes the entire string and uses it as a parameter for the reverseString method and the method repeats itself from there.
 
Marshal
Posts: 26114
77
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

George Foreman wrote:So what I'm struggling with is line 18.



Did you write that code, or is it somebody else's code you'd like to talk about?

It would be nice to know if it does what it's supposed to do, for example. I think it's correct, but the String.substring method is (for me) an open invitation to commit an off-by-one error so I might be wrong.

But if it does work correctly, it has a problem. Namely, the code in line 18 doesn't work the same way that the comment in line 6 says it does.

It has another problem, at line 16, but you aren't likely to find that one by putting in random strings.
 
George Foreman
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The program was orginally written by someone else on chegg... I would post a link but you have to pay for a membership. I modified the original code. I'm just doing some recursive problems trying to figure it out.

Btw, thanks for the reply    
 
Paul Clapham
Marshal
Posts: 26114
77
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

George Foreman wrote:
reverseString(...) this is where the recursion begins and substring method takes the entire string and uses it as a parameter for the reverseString method and the method repeats itself from there.



As I mentioned I'm sort of dyslexic with respect to the substring() methods. However the point is that it doesn't pass the entire string, it passes the string with the last character removed. Which is a shorter string than the earlier call to reverseString. (At least that's how it's supposed to work when written correctly.)

So you call reverseString with a string of length 4. In turn it takes one character from that string, the last (or first), and calls reverseString with a string of length 3.

Each time reverseString is called recursively, it's passed a string which is one character shorter. Will this go on for ever? No. Line 16 will eventually stop the recursive processing.
 
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wouldn't use Strings for that recursion at all; I would put the String into a StringBuilder and reverse that. The reason is that repeated use of the String concatenation operator + causes slow execution, even after the optimisation introduced in Java9. (Except that multiple +s in the same expression are all right; they can be optimised away at compile time.) People may say that using this method counts as cheating!
You will probably find it easier to take the first letter off the text. StringBuilder has methods to do this, and a method to put the letter back at the end. If you take the first letter off, there will be no need to do any counting; you always use the index 0.
If you use Chinese writing, emoticons, strange arrows, or anything else with a Unicode value > 0xffff, you will have to use the methods using code points rather than chars.
 
Marshal
Posts: 7845
538
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Well you got your base case wrong. Think in which case your program will fail.

edit: Paul Clapham already pointed it out actually

Hint: you can assume non null string is passed.


You got formatting wrong at line 10:


And line 17, you got 4 formatting mistakes (try to avoid such decoration, it is not worth it to save lines in such a way):


Correct formatting is as follows:
 
George Foreman
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
StringBuilder!!!
 
Campbell Ritchie
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Didn't I say yesterday that method would be regarded as cheating?
 
George Foreman
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Didn't I say yesterday that method would be regarded as cheating?



Well... who's going to say "no" to an offer like that. LOL
 
Paul Clapham
Marshal
Posts: 26114
77
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, in real life you'd just use StringBuilder.reverse() and move on to the next task on your list. But beginning programmers are often given homework which requires them to do things the hard way. Sort of like having the trainee security guard practice being attacked by an assailant with a passion fruit.
 
Ranch Foreman
Posts: 28
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you really want to practice recursion (without all the Java kruft  ), try The Little Schemer - lots of simple bite-sized exercises to get you thinking in a recursive and functional style, using the Scheme language (a variety of Lisp).  Because Scheme syntax is pretty minimal, it helps to reveal the underlying logical patterns in these exercises.  You'll probably never program in Scheme for real, but the principles are the same in any language.

And if you really want to dig deep, try Structure and Interpretation of Computer Programs (SICP) which is available free online.
 
Campbell Ritchie
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:. . . practice being attacked by an assailant with a passion fruit.

Now, that's something I have never seen
 
Liutauras Vilda
Marshal
Posts: 7845
538
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Recursion is very worth mastering. You'd find many places where you'd need to understand it.
 
Campbell Ritchie
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:. . . many places where you'd need to understand it.

I long ago gave up understanding recursion, or even trying. I wrote recursive code and just let it get on with it.
 
Liutauras Vilda
Marshal
Posts: 7845
538
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:... I wrote recursive code and just let it get on with it.


Sounds very much like you mastered it
 
Campbell Ritchie
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's become automatic, like riding a bicycle. I think, “Let's go left,” and the bicycle goes left.
 
Campbell Ritchie
Marshal
Posts: 71028
291
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Christopher Webster wrote:. . . You'll probably never program in Scheme for real, but the principles are the same in any language. . . .

Isn't that how they teach programming at MIT? Learnn the principles in Scheme, and you can apply them in any language.
 
George Foreman
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Christopher Webster wrote:If you really want to practice recursion (without all the Java kruft  ), try The Little Schemer - lots of simple bite-sized exercises to get you thinking in a recursive and functional style, using the Scheme language (a variety of Lisp).  Because Scheme syntax is pretty minimal, it helps to reveal the underlying logical patterns in these exercises.  You'll probably never program in Scheme for real, but the principles are the same in any language.

And if you really want to dig deep, try Structure and Interpretation of Computer Programs (SICP) which is available free online.



Thanks for that little tip. I'll look into that.
 
Christopher Webster
Ranch Foreman
Posts: 28
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Isn't that how they teach programming at MIT? Learnn the principles in Scheme, and you can apply them in any language.



I think they switched to Python for the introductory programming classes a few years ago.  Some of their courses are available online at the MIT OpenCourseWare site e.g. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/
 
Hold that thought. Tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic