# Thread: recursion help

1. Member
Join Date
Dec 2010
Posts
88
Rep Power
0

## 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.

Java 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.

2. 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

3. Member
Join Date
Dec 2010
Posts
88
Rep Power
0

## 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. :)

4. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11
Ok, I'll do the highest number one for you, and try to explain (kinda sleepy, probably won't make much sense :D)
Java 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:
Java 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:
Java 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.
Last edited by m00nchile; 02-18-2011 at 03:46 AM.

5. 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:

Java 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

6. Member
Join Date
Dec 2010
Posts
88
Rep Power
0

## 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.:)

7. Member
Join Date
Dec 2010
Posts
88
Rep Power
0

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•