Results 1 to 7 of 7

Thread: recursion help

  1. #1
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,570
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Yakg View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Smile 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. #4
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    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.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,570
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Yakg View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

    Default 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. #7
    Yakg is offline Member
    Join Date
    Dec 2010
    Posts
    59
    Rep Power
    0

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

Similar Threads

  1. more fun... with recursion
    By sonny in forum New To Java
    Replies: 19
    Last Post: 03-23-2010, 05:09 AM
  2. how do i do recursion.....
    By sonny in forum New To Java
    Replies: 4
    Last Post: 03-17-2010, 05:15 PM
  3. Recursion
    By mp0667 in forum New To Java
    Replies: 1
    Last Post: 01-20-2010, 07:49 AM
  4. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  5. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 02:26 AM

Posting Permissions

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