Java recursion count

Question

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));
  }
}

There are really better examples to start with practice in recursion than string processing [wiki](http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursive_procedures). — PeterMmm, Nov 14 '11 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). — Clockwork-Muse, Nov 14 '11 at 16:43

score 7 · Answer 1 · answered Nov 14 '11 at 15:47

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"

answered Nov 14 '11 at 15:47

Matt Fenwick

48,199
22
128
192

Regarding strategically placed print-statements, I like to "align" the print with the depth of the recursion, as can be seen here: http://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively/7775224#7775224 – TacticalCoder Nov 14 '11 at 16:12
@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. – Matt Fenwick Nov 14 '11 at 18:13

score 4 · Answer 2 · answered Nov 14 '11 at 15:48

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));
}

answered Nov 14 '11 at 15:48

laguille

637
4
6

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. – David H. Clements Nov 14 '11 at 15:52
Ohhh I remember now. Thanks for your help guys; it's been a while since I've used recursion lol. – user1045873 Nov 14 '11 at 16:02

score 2 · Answer 3 · answered Apr 30 '15 at 03:07

  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!

score 2 · Answer 4 · answered Nov 14 '11 at 15:44

2

You aren't using the value returned from recur.

answered Nov 14 '11 at 15:44

Steve C

647
3
6

score 1 · Answer 5 · answered Nov 14 '11 at 15:56

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.

score -1 · Answer 6 · edited May 02 '13 at 07:53

-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

edited May 02 '13 at 07:53

Rob

4,927
12
49
54

answered May 02 '13 at 07:36

CodeMadness

1
4

Java recursion count

6 Answers6