java - boolean function that contains "bab" -

how have recursive boolean method check if contains bab. have i'd recursively.

public static boolean hasbab(string str) {       if (str.length() < 3) return false;       if (str.substring(0,3).equals("bab"))         return true;       else         return false;     } 

recursion should thought of 2 parts.

1) base case. trivial case can easly determined. have far start base case. 1) string less 3? return false. 2) string start "bab" return true.

2) recursive case. splits problem tinier problems, , if split them enough have base case.

@logiraptro has example of simple recursion.

public static boolean hasbab(string str) {   if (str.length() < 3) return false;   if (str.substring(0,3).equals("bab"))     return true;   else     return hasbab(str.substring(1)); } 

this uses base cases, , recursive case checks string index 1 on. reduces our string 1 charter, enough solve problem.

this means end stack level of length of string.

can better? little, breaking problem in half need stack level of ln(n) n length of string. not big deal lengths, if searching string length of 1 million maybe significant. first version our stack 1,000,000 deep! binary version need go 14 levels deep.

this comes @ cost though, our solution because more involved.

our base cases 1) if string less length of search string, return false. 2) if string length of search string, if equal return true, else return false. 3) if string appears on mid point of string return true.

if none of these true,we break string 2 parts , recursively check on string.

here example of algorithm, can replace "bab" string like, although hasn't been tested i'm pretty sure okay.

public static boolean hasbab(string str) {       string searchstring = "bab";        // base cases       if (str.length() < searchstring.length())            return false;        if (str.length() == searchstring.length())       {           if (str.equals(searchstring))           {               return true;           }           return false;       }        int halfway = str.length()/2;        // check search string on "break"       (int = 0; < searchstring.length(); i++)       {           int startindex = halfway - 1 - i;           int endindex = startindex + 3;           if (startindex >= 0)           {               string substring = str.substring(startindex, endindex);               if (substring.equals(searchstring))               {                   return true;               }           }       }       // recursive cases       //  did find search string on break,so break string 2 equal(ish) pieces , check       if(hasbab(str.substring(0,halfway -1)))          return true;       if(hasbab(str.substring(halfway, str.length())))          return true;       return false; }