# recursion help

• 02-17-2011, 07:54 PM
Yakg
recursion help
hi, trying to understand the recursion topic, specially with boolean results.
Somehow I've managed to get along at the beginning of the following method but then it all turned confusing. I got to say that I didn't find a really good explanation source for boolean recursion on the web and since I would like to understand the logic behind it. I would be happy if anyone could help.

My method:
It gets (String s1,String s2) s1 is the string "abcd" s2 is the string "bc" in that case it supposed to return true since s1 has the s2 string in it.

Code:

```public class A{     public static boolean isSubstring (String s1, String s2){         if (s1.equals(s2))         return true;         else return isSubstring (s1,s2,s1.length());     }     //find the first identical letter     private static boolean isSubstring (String s1,String s2, int length){     boolean result = false;         if (length == 1)     if (s1.charAt(length-1) == s2.charAt(0)){     return isSubstring (s1.substring(length-1),s2.length(),s2);     }else return false;         result = isSubstring (s1,s2,length-1);         if  (s1.charAt(length-1) == s2.charAt(0))     return isSubstring (s1.substring(length-1),s2.length(),s2);     return false;     }         private static boolean isSubstring (String s3, int i, String s2){         return isSubstring (s3.substring(0,s2.length()),s2);         }```
Sorry for the mess, you don't have to try too hard on it just an explanation would be great, thanks.
• 02-17-2011, 08:48 PM
JosAH
Quote:

Originally Posted by Yakg
hi, trying to understand the recursion topic, specially with boolean results.

The String class implements a startsWith( ... ) method; it returns true for s1.startsWith(s2) if s1, well, starts with s2. The substring( ... ) method helps you step over suffixes of String s1.

kind regards,

Jos
• 02-17-2011, 11:18 PM
Yakg
Sorry forgot to mention that we're restricted
with what we can use, so in that case only charAt(),substring(int),and length() are available.

Basically I need to understand how recursion works.
If you know any good examples online as I didn't find many.
I know the basic ones but in more complicated cases it doesn't help.

Good examples could be things like:
Finding the highest number in an array recursively
or the biggest difference between numbers
things like that if you know would be great..

Thanks. :)
• 02-18-2011, 04:42 AM
m00nchile
Ok, I'll do the highest number one for you, and try to explain (kinda sleepy, probably won't make much sense :D)
Code:

```public class RecTest {   public static int findHighest(int[] array) {     return findHighest(array, 0);   }   public static int findHighest(int[] array, int position) {     if(position == array.length) return 0;     int nextNum = findHighest(array, position+1);     if(array[position] > nextNum) return array[position];     return nextNum;   }   public static void main(String[] args) {     int[] array = {1,5,3,6,9};     System.out.println(findHighest(array));   } }```
So, what this little bit of code does, first it checks to see if the position is still in bounds of the array, if it isn't, it returns 0. This is called an exit condition, this tells the method when to stop recursion (result has been found). Next, the method calls itself with an incremented position. This goes on until you reach the end of the array (recursive call). Once the end of the array has been reached, values start being returned and the last if block is processed. The call stack looks something like this:
Code:

```findHighest(0) //ommiting array in call for clarity nextNum = findHighest(1)   findHighest(1)   nextNum = findHighest(2)     findHighest(2)     nextNum = findHighest(3)       findHighest(3)       nextNum = findHighest(4)         findHighest(4)         nextNum = findHighest(5)           findHighest(5)           position == array.length is true           return 0         nextNum = 0         0 > 9 false         return 9       nextNum = 9       6 > 9 false       return 9     nextNum = 9     3 > 9 false     return 9   5 > 9 false   return 9 nextNum = 9 1 > 9 false return 9 //the method returns this```
I hope this makes sense, if you have any questions, I'm here.
Another easy example would be calculating a factorial:
Code:

```public static int factorial(int n) {   if(n == 0) return 1;   return factorial(n-1)*n; }```
Try going through this example by yourself the way I went through my example.
• 02-18-2011, 08:43 AM
JosAH
Quote:

Originally Posted by Yakg
with what we can use, so in that case only charAt(),substring(int),and length() are available.

If you don't want to use the startsWith( ... ) method you can also get away with just using the substring( ... ) and equals( ... ) methods. The conditions for a String s containing a String t are:

1) is length(s) < length(t) s can't contain t (trivial)
2) t is a prefix of s
3) repeat the previous steps for the String s.substring(1) and t (all but the first char of s)

In code that would be:

Code:

```private static boolean contains(String s, String t) {         if (s.length() < t.length()) return false; // step 1                 if (s.substring(0, t.length()).equals(t)) return true; // step 2         return contains(s.substring(1), t); // step 3 }```
Note that step 2) is a replacement for the startsWith( ... ) method.

kind regards,

Jos
• 02-18-2011, 01:39 PM
Yakg
That's what I've been looking for!
Amazing replies ,above my expectations. I went through with a debugger and really saw what's going on and tried it myself on my method. I'm not through yet still need to figure out the ending but major improvement and getting there.

Thanks.:)
• 02-18-2011, 02:10 PM
Yakg
can't believe it but I got it!!
I managed somehow to write a method that finds the point which the array reaches the half of the total array sum. Probably it interest only me..
Anyway you helped me figuring this out, what a relief.

Thanks.