Results 1 to 15 of 15
  1. #1
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

    Default Recursion Problems. Pls Help!

    Hi there,

    I'm currently having difficulties in implementing fully recursive methods (those which do not use loops at all) and was wondering if anyone can give me a hand since i can't seem to grasp this topic.

    the first method to implement is
    boolean allEqual(int[] a, int start, int end) that checks if all elements in the array a from start to end are equal.

    my code is as follows as I cannot seem to understand how to implement it.
    public static boolean allEqual(int[] a, int start, int end){
    if (start==end) return true;
    boolean success = allEqual(a,start,end);
    if (success) return true;
    success = allEqual(a,start+1,end);
    return success;


    I'm not entirely sure if my base case is correct, so if someone can point that out it would be great. Returning a boolean from a recursive method confuses me. :confused:

    the other method is
    boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.


    and what i have done is
    public static boolean linearSearch(int[] a, int x, int start, int end){
    if (start==end) return a[start]==x;
    if (a[start]>a[end])
    return linearSearch (a, x, start+1, end);
    else return false;
    }


    again sorry, if my implementation looks like non sense. I have only recently started to understand how to implement basic recursive methods -- ones that don't deal with arrays such as factorials and harmonicSums.

  2. #2
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    About the equality checker, if you think about it, you have two base cases, or as I prefer to call them, exit conditions. Either all elements are equal and you return true, or an element is not equal to all the others and you return false. Currently, your method can't return a false.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  3. #3
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

    Default

    Ohhh alright, so for every recursive boolean method, you'd need to have two exit conditions? I tried adding in

    if (!(start==end)) return false;


    this seems to make every case return false now though :confused:

  4. #4
    r035198x is offline Senior Member
    Join Date
    Aug 2009
    Posts
    2,388
    Rep Power
    7

    Default

    Your equality checker doesn't have the body that actually does the comparison for elements in the passed in array a.
    You need an if that looks something like
    Java Code:
    if(a[start] != a[start +1]) 
        return false;

  5. #5
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    The exit condition
    Java Code:
    if(start == end)
      return true;
    can only be used to determine if the run was sucessfull, because every call to the method except the last one will have different values for start and end.
    Also, your method would loop infinitely because of this:
    Java Code:
    public static boolean allEqual(int[] a, int start, int end){
    if (start==end) return true;
    boolean success = allEqual(a,start,end); //this calls the method with the
    //same parameters
    if (success) return true;
    success = allEqual(a,start+1,end);
    return success;
    }
    This is equal to:
    Java Code:
    int recursive(int n) {
      return recursive(n); //no modification of n variable before recursive call
    }
    To make it more understandable:
    Java Code:
    int n = 10, sum = 0;
    while(n != 0) {
      sum += n;
    }
    in the example with the while loop, you don't modify the n variable and produce an infinite loop.
    I'll give you the solution, but in pseudocode, you translate it into valid Java:
    Java Code:
    if start and end are equal
      return true
    if variable with index start doesn't equal variable with index end
      return false
    call method again with start incremented by 1
    Try to write down the pseudocode for your other problem as well, it usually makes a problem much clearer.
    Ever seen a dog chase its tail? Now that's an infinite loop.

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

    Default

    Maybe my schizophrenic example applies here as well: suppose there's me, the big mouthed mr Know-It-All who claims he can check array elements for being all equal and there's my intelligent, a bit shy friend who is highly intelligent. When I'm given an array and a start and end index I can do the simple stuff: when both start and end are equal I assume there are no elements to be checked so I return true. I can also check two elements (one at the start and one at the end); when they're not equal I return false; otherwise I give the rest of the array to my shy and intelligent friend; here goes:

    Java Code:
    boolean me(int[] a, int start, int end) {
       if (start == end) return true;
       if (a[start] != a[end]) return false;
       return friend(a, start+1, end);
    }
    Here's where the schizophrenic part hits: I don't have a friend, my friend is me and I am my friend and I am schizophrenic; that method should actually read:

    Java Code:
    boolean me(int[] a, int start, int end) {
       if (start == end) return true;
       if (a[start] != a[end]) return false;
       return me(a, start+1, end);
    }
    A more sensible person might name this method 'allEqual' or similar ...

    kind regards,

    Jos

  7. #7
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

    Default

    Wow! Thanks r035198x, m00nchile, and JosAH

    All your tips helped out A LOT. I never thought about writing it in pseudocode beforehand, that in turn makes this a whole lot easier, seeing how I don't think recursively yet. So it doesn't come naturally to me yet.

    And the schizophrenic analogy is simply genius . If that was the way we were taught in school. Instead of out of the book verbatim. University would be a whole heck of a lot easier!

    Now i can tackle the rest of these 8 methods with more understanding about recursion. Thanks everyone!

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

    Default

    Quote Originally Posted by ferdzz View Post
    And the schizophrenic analogy is simply genius .
    Well, I won't call it 'genius' but it does make the quarter drop for a lot of people struggling with the concept of recursion.

    kind regards,

    Jos

  9. #9
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

    Default

    Would the pseudocode for this method

    boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.

    be
    if a[start] equals to x , a[start] is x
    therefore return true

    if end doesn't equal to x
    return false

    increment start by 1

    ?

  10. #10
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Almost.
    If start equals end and a[start] does not equal x
    return false
    If a[start] equals x
    return true
    call function with start incremented by 1

    If you simply define your exit condition if a[end] doesn't equal x, you'll get a false even if the array contains the element, but not at the index end.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  11. #11
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

    Default

    Thanks a lot. I'm starting to get the hang of it now, just gotta pay attention to minor details so I can get rid of logical errors such as that one. Thanks!

  12. #12
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Exactely, well put. Now, the best way to get the hang of recursion is with a few simple mathemtacial algorithms, like calculating x to the y, the factorial of n, the fibonacci sequence etc.
    Ever seen a dog chase its tail? Now that's an infinite loop.

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

    Default

    Quote Originally Posted by ferdzz View Post
    Thanks a lot. I'm starting to get the hang of it now, just gotta pay attention to minor details so I can get rid of logical errors such as that one. Thanks!
    Don't write down your pseudo code and think wham, bam, ready; because you have written down your intentions, not the instructions that have to be executed by an extremely dumb thing. Read your own pseudo code as if you were that dumb thing (I'm extremely good at that). Be extremely dumb but awfully exact and try to interpret that pseudo code. You'd be surprised at the outcome and then it's time to rewrite your pseudo code.

    kind regards,

    Jos

  14. #14
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    The way I explain how thick computers are to my friends who aren't tech-savvy is like this: say you're sitting on the couch with a friend, and you ask him to bring you a beer. If your friend is a computer, this becomes quite complicated. First, you have to specify the location of the beer, then instruct him to get up, rotate towards the door, take a number of steps, rotate towards the kitchen (again, you have to specify where and what kitchen is), take a number of steps again, open the fridge door, identify the beer, extend the arm, grab the beer, retract the arm, track back on the previous path, give you the beer, then sit down again.
    In short, you have to tell the computer exactely what you want it to do, include every minor detail and pay attention to the minutia that can produce erroneous behavior.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  15. #15
    ferdzz is offline Member
    Join Date
    Jun 2010
    Posts
    12
    Rep Power
    0

Similar Threads

  1. Recursion.
    By Cruncher in forum Advanced Java
    Replies: 30
    Last Post: 05-10-2010, 01:06 PM
  2. Recursion assignment problems
    By tfitz666 in forum New To Java
    Replies: 11
    Last Post: 01-24-2010, 09:18 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 ravian in forum New To Java
    Replies: 2
    Last Post: 12-03-2007, 05:15 PM

Posting Permissions

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