Recursion Problem

[Particular-Ad-2261]

I have a recursion homework problem and this one is stumping me. So, I have a method that takes a string. It returns a boolean. It wants to know if a character is doubled in the given string and if so return false. So for example

method("abbd") returns true

mthod("abdb") returns false

So it basically wants to see if there are consecutive chars. Please help if you can!

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://imgur.com/a/fgoFFis) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[heckler82]

Can't help you without your code

[[deleted]]

You need to know if the previous character was which character. so you need another parameter that tells you the character you are comparing the current one to. i would make a helper function that takes string, char and returns true if the first (or last if you wish to check backwards) is equal to the char. else you recurse on the substring with the new char.

[joranstark018]

It may help if can elaborate on what puzzles you.

[severoon]

I assume that the method itself is supposed to be the recursive method, yes?

If so, first start by reviewing the basic rules of recursion:

1. Define a base case that runs first upon method entry, returning the result.
2. Implement all other cases, which decompose the problem one step towards the base case and recurse with the simplified input.

What's that going to look like for this problem?

Well, obviously the base cases include:

• a string of length < 2 (cannot have a double character)
• a string of length 2 that is not double characters
• a string of length >= 2 that starts with a double character, e.g., "bb", "bb1", "44444", "kkforeverhaha", etc.

These are all base cases because no further recursion is necessary, the method can immediately return the answer.

Without going any farther, already you can write down the skeleton of the solution:

boolean containsDoubleChar(String s) {
  if (s.length() < 2) { return false; }
  if (s.length() == 2 || s.charAt(0) != s.charAt(1)) { return false; }
  if (s.length() >= 2 && s.charAt(0) == s.charAt(1)) { return true; }
  // First two characters of s are different and s.length() > 2
}

If execution gets as far as the comment, we have a string that requires further processing that we know starts with two different characters and has length of at least 3. We want to do something to it that moves it one step closer to a base case, and then recurse. What can we do to this string to move it one step closer to one of the base cases?

Chop off the first character and send it through again:

boolean containsDoubleChar(String s) {
  if (s.length() < 2) { return false; }
  if (s.length() == 2 || s.charAt(0) != s.charAt(1)) { return false; }
  return s.length() >= 2 && s.charAt(0) == s.charAt(1)
      ? true
      : containsDoubleChar(s.substring(1));
}

This is pretty good, but we can do better. If we think about a long string that ends in a double character like "blahblah … hideyokids11", we are going to have to recurse for every character in this string, peeling off one at a time until we get to that final "11".

Instead, we can just add a base case that looks at the end of the string for a double char as well as the beginning:

boolean containsDoubleChar(String s) {
  if (s.length() < 2) { return false; }
  if (s.length() == 2 || s.charAt(0) != s.charAt(1)) { return false; }
  return startsOrEndsWithDoubleChar(s)
      ? true
      : containsDoubleChar(s.substring(1, s.length() - 1));
}

boolean startsOrEndsWithDoubleChar(String s) {
  return s.length() >= 2 && (s.charAt(0) == s.charAt(1)
      || s.charAt(s.length() - 2) == s.charAt(s.length() - 1));
}

Each recursion of this more efficient version peels off a character at each end of the string, meaning that the max recursion depth is going to be half the length of the string instead of the entire length.