• Post Reply Bookmark Topic Watch Topic
  • New Topic

a tricky recursion problem (at least for me)  RSS feed

 
andy colins
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the problem as follows:
you have a boolean method called "check" . the input for this method is String.
the method checks if the string got pairs of '*' or '+' or '-' . if it does, the answer is true.
but if the '+' or '-' located next to another '+', '-' ,(like '++' or '--' , the answer is false.

also given that:
public static boolean check(String s) {
return check(________) ;

which means that the method check is calling to other method called check, but it is overridden .
the solution should be recursive . i have tried to think a lot about it, but so far, nothing came to mind about the solution
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
andy colins wrote:the problem as follows:
you have a boolean method called "check" . the input for this method is String.
the method checks if the string got pairs of '*' or '+' or '-' . if it does, the answer is true.
but if the '+' or '-' located next to another '+', '-' ,(like '++' or '--' , the answer is false.


Welcome to the Ranch!

I'm not quite sure what constitutes a pass or a fail in your check method though. What do you mean by pairs of '*' etc? Do you mean a String that has exactly two instances of those characters? Does it matter where those instances are? Do they have to be at the beginning and end of the String, or can they be anywhere?

You say they fail the check if the characters appear next to each other. Does that mean they fail the check if they appear next to each other anywhere in the String, or if the String only has 2 characters?

Perhaps you could give some examples of what Strings pass and what Strings fail the check.

andy colins wrote:. i have tried to think a lot about it, but so far, nothing came to mind about the solution


Well the Ranch won't give you the solution (which I'm sure isn't what you're after anyway) so you'll have to show us what you have so we can help.

In the meantime you should think about the following things. Recursion is the technique of having a method that calls itself repeatedly to solve a problem. Each time it calls itself again it makes the problem a little simpler. At some point the recursion needs to terminate (otherwise it will go on forever), so before the method calls itself again it needs to check if it can work out the answer yet.

So, a recursive method will look something like the following pseudo-code...



In this case, making the problem simpler probably means making the String a little shorter each time your method calls itself.

If your String runs out of characters then that is one solution, and you would return false.
If you find the situation you are looking for then that is the other solution, and you return true.

However until I understand exactly what Strings will pass and fail your check I can't guide you to a more specific implementation.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

So, you have to go through the String until you find a +, then check whether the remainder of the String following has a + at its start? Please write down carefully what it means about pairs of + but not two +s located adjacent to each other.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not only has MJT beaten me by 1 minutes, but he has also put the answer so much better than I did.
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Not only has MJT beaten me by 1 minutes, but he has also put the answer so much better than I did.


Normally I'm posting from my phone, but for once I'm posting from a PC so can type a little faster and be a little more verbose ;)
 
andy colins
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike. J. Thompson
first of all you are right - i don't want the answer. i want to understand .
now i shall explain a bit more the question:
the method check is boolean which is returning true if :
there are pair of the signs '*' or '+' or '-' in the string .
you will get a true result for the strings " " (empty string ) and ( +-*-+** )

but if there is '+' or '-' next to each other in the string ( '--' or '++' )
the result will be false;
for example, you will get false for the strings ( +*-a+ ) and (*++-* ) .

my attempt :


but i can't figure it out how recursively to check if there is a pair anywhere in the string of *, +, -
p.s: not recursively the task is pretty easy. but that's not the case
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Would the following string pass or fail?

"*+*++"

The answer to that question will determine what the terminator for the recursion will be.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

First of all, I am not a fan of assignments that says that something must be done recursively, when recursion is not the best / easiest solution. IMO, it is a sign of laziness on the part of the instructor.

andy colins wrote:
p.s: not recursively the task is pretty easy. but that's not the case


Converting any iterative solution to a tail recursion solution is incredibly easy. Just initialize (for the first iteration) and call the recursive method that does one iteration. The method will check for end state, and if so, return; Otherwise, it will do one iteration, setup for the next iteration, and call itself.

Local variables (including the index) that are used by the iterative solution should be changed to be parameters that are passed to the next iteration. Since it is tail recursion, you don't care that the "local variables" are being undone as the method stack is unwind. As for the result, that is passed back as the return value (from the last "iteration" method call all the way back to the first).

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!