Results 1 to 7 of 7
Thread: recursion help
 02172011, 07:54 PM #1Member
 Join Date
 Dec 2010
 Posts
 59
 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(length1) == s2.charAt(0)){ return isSubstring (s1.substring(length1),s2.length(),s2); }else return false; result = isSubstring (s1,s2,length1); if (s1.charAt(length1) == s2.charAt(0)) return isSubstring (s1.substring(length1),s2.length(),s2); return false; } private static boolean isSubstring (String s3, int i, String s2){ return isSubstring (s3.substring(0,s2.length()),s2); }
 02172011, 08:48 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,016
 Blog Entries
 7
 Rep Power
 23
I have the stamina of a seal; I lie on the beach instead of running on it.
 02172011, 11:18 PM #3Member
 Join Date
 Dec 2010
 Posts
 59
 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. :)
 02182011, 04:42 AM #4Senior Member
 Join Date
 Feb 2010
 Location
 Ljubljana, Slovenia
 Posts
 470
 Rep Power
 6
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)); } }
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
Another easy example would be calculating a factorial:
Java Code:public static int factorial(int n) { if(n == 0) return 1; return factorial(n1)*n; }
Last edited by m00nchile; 02182011 at 04:46 AM.
Ever seen a dog chase its tail? Now that's an infinite loop.
 02182011, 08:43 AM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,016
 Blog Entries
 7
 Rep Power
 23
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 }
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 02182011, 01:39 PM #6Member
 Join Date
 Dec 2010
 Posts
 59
 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.:)
 02182011, 02:10 PM #7Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
Similar Threads

more fun... with recursion
By sonny in forum New To JavaReplies: 19Last Post: 03232010, 06:09 AM 
how do i do recursion.....
By sonny in forum New To JavaReplies: 4Last Post: 03172010, 06:15 PM 
Recursion
By mp0667 in forum New To JavaReplies: 1Last Post: 01202010, 08:49 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
Recursion
By kathyla18 in forum New To JavaReplies: 2Last Post: 04092009, 02:26 AM
Bookmarks