1

First of all this is not homework. Just me practicing. I'm trying to recursively determine the number of times "hi" appears in the given string, but in every case it skips to the last else if statement and things the string is empty. Any ideas?

Basically, if(string starts with "hi") increment count by 1 and recurse with the string after the 2nd index to skip over the "hi" it just counted

else if(string does not start with "hi" and string is not empty) recurse with the string after its 1st index to see if it starts with "hi" the next time around.

else if(string is empty) Print("End of text reached") return count;

public class Practice {

  public int recur(String str, int counter){
      int count=counter;
      if(str.startsWith("hi")){
          count++;
          recur(str.substring(2),count);
      }
      else if((!str.isEmpty())&&(!str.startsWith("hi"))){
          recur(str.substring(1),count);
      }
      else if(str.isEmpty()){
          System.out.println("End of text reached");
          return count;
      }
      return count;
  }

  public static void main(String args[]){
      String str="xxhixhixx";
      Practice p=new Practice();
      System.out.println(p.recur(str, 0));
  }
}
Improve this question
2
  • 2
    There are really better examples to start with practice in recursion than string processing wiki. Commented Nov 14, 2011 at 15:45
  • I have an issue with this - any caller can modify the results, because counter is part of the external call. At minimum, this should be made private, with a public wrapper that does not contain counter (and is not recursive). The other method is to do the addition during the recursive return. Also, you're checking with startsWith, then moving a cursor by 1 - what's wrong with indexOf (better optimization available there, I think). Commented Nov 14, 2011 at 16:43

6 Answers 6

Reset to default
7

This is a good opportunity to practice debugging recursive functions calls -- actually quite difficult. Suggestions:

  • use strategically placed print-statements to ensure that the arguments are being changed correctly from one recursive invocation to the next
  • refactor the order of case-analysis in the if-statement to make it more clear. For example, 1) check if the string is empty (base case), 2) check if the string starts with "hi", 3) catch-all -- not empty and doesn't start with "hi"
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Regarding strategically placed print-statements, I like to "align" the print with the depth of the recursion, as can be seen here: stackoverflow.com/questions/7774769/…
@user988052 -- that can be handy for some recursive problems, but more so for those involving trees. This is a 'linear' recursive problem, so it wouldn't be as helpful.
4

As @Steve mentioned, you have to use the return value that recur returns.

See below for a modified version of your code, I also simplified your if/else statements:

public int recur(String str, int counter) {

  if (str.startsWith("hi")) {
    return recur(str.substring(2), counter+1);
  } else if (!str.isEmpty()) {
    return recur(str.substring(1), counter);
  } else {
    System.out.println("End of text reached");
    return counter;
  }
}

public static void main(String args[]) {
    String str = "xxhixhixx";
    Practice p = new Practice();
    System.out.println(p.recur(str, 0));
}
Improve this answer

2 Comments

This is the correct solution. What was happening is that the top level function call was hitting the last return statement, which was returning zero since it wasn't doing anything with the return values from the recursive calls.
Ohhh I remember now. Thanks for your help guys; it's been a while since I've used recursion lol.
2

You aren't using the value returned from recur.

Improve this answer

Comments

2 
  public int countHi(String str) {
      if (str.length() <= 1) {
      return 0;
      }
      int count = 0;
      if (str.substring(0, 2).equals("hi")) {
      count = 1; 
      }
      return count + countHi(str.substring(1)); //substring off
    }

All this does is recursively count the number of the String "hi" inside a larger String. The rest of the implementations should be a piece of cake, happy Coding!

Improve this answer

Comments

1

Your program printing 'End of text' is correct as finally as per the logic it will reach there, reason for count always coming as 0 is that in every iteration they change there own copy and finally when the termination condition is reached(String is empty) the result is popped out of the stack, hence final outcome that you receive is the pop of the first iteration where count was 0, so you have to return the value returned by recur at every step instead of returning count.

Improve this answer

Comments

-1 
public static int recursive(String givenStr) {

    int count =0 ;

    Pattern pattern = Pattern.compile("hi");
    Matcher match = pattern.matcher(givenStr);
    while(match.find()){
        System.out.println(match);
        count++;
    }
    return count;
}

This Will return number of times "hi" has appeared into the String

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.