Using recursion to count substrings (with exceptions to the rule) in Java
Similar to @Ben Aaronson above but uses indexOf() instead of startsWith()

public int countHi2(String str) {
    int pos = str.indexOf("hi");
    if (pos == -1) {
       return 0;
    }
    int increment = (pos == 0 || str.charAt(pos-1) != 'x') 
                      ? 1
                      : 0;   
    return countHi2(str.substring(pos+2))
           + increment;
}