Help!! using recursion to search an array


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 6 of 6

Thread: Help!! using recursion to search an array

  1. #1
    Join Date
    Oct 2004
    Posts
    2

    Angry Help!! using recursion to search an array

    Hi there,
    I have been learning Java in my computer science course for the last couple of months. Everything was goin fine until I hit the brick wall which was recursion. I am very slowly getting my head around it. Anyway, I was wondering if anyone would have some code for how to search an array for the lowest number in the array (must use recursion!!). Most of the recursive code in the text books sorts the numbers to different positions in the array using various sort methods and the search methods I have looked at already know the value that they are looking for in the array. All I am looking for is a simple, explained method or class which will take in an unsorted array and throw back the lowest number in the array, but it must use recursion as an iterative search for the lowest number is no good to me.

    If anyone out there can help me with this it would be really great

    Many thanks in advance
    Baconsoft

  2. #2
    Join Date
    Feb 2004
    Posts
    541
    If you're searching for the lowest number in the array you can't avoid searching every single position in the array. I'm not sure why anyone would want to do that with recursion, but if it's an assignment you have to do as you're told i guess :P

    Anyway, even with recursion it will be an iterative process. The recursive method will be given an array location to start at, and it will be given the current lowest value found. I'll write some pseudo code for you to follow.

    Code:
    public int recursionMinSearch(int index, int minValue, int array[])
    
        IF value in array at index LESS THAN minValue
        make minValue equal that value
    
        IF index EQUALS max index in array
        RETURN minValue
    
        ELSE RETURN a recursionMinSearch with one added to index

  3. #3
    Join Date
    Oct 2004
    Posts
    2
    Hi MikeBarr81
    Thanks very much for your reply. However the pseudocode appears to require an initialised minValue. What if this minValue is set to zero and there is nothing lower than zero in the array? Would this code then return zero which is not even in the array of numbers? Maybe I am misinterpreting?

    The problem I am trying to complete gives the following code in which you are supposed to find the maximum value in the array ( I just wanted to find the smallest)

    Q. Using recursion, find the largest value in the array

    public class DataSet
    {

    .....
    public Dataset (int[] anArray) {.......}
    public int getMaximum () {.....}
    ......

    }

    If you or anyone could provide me with pseudocode or code to solve this one it would be very much appreciated. I have been trying but I cant do it.

    Thanks again
    Baconsoft

  4. #4
    Join Date
    Feb 2004
    Posts
    808
    when searching for a minimum value, you must start with the highest number imaginable, that way the first number found (if any) is guaranteed to be lower

    hence, yo kick off your recursion:

    recurse(0, Integer.MAX_VALUE, array)



    --

    recursion is simple, in a way:

    you write a method that does one of two things:
    exits, based on some condition or
    calls itself again with modified parameters (with the goal of reazching the exit condition before the stack is exhausted)

    hence, mikes method the exit condition is the end of the array is reached
    each time the method calls itself it bumps the array index up by one, therefore it will eventually reach the exit condition.
    at this point, because the min value found so far has been transported right the way through to the last time the method was called, it should be returned all the way back..

    so typically a recursive call will:

    return myself(some,changed,parameters)


    the myself part is evaluated and starts running.. and over and over, this will happen.. until that exit point of the recursion is reached.. then the value is returned, which is returned, which is returned... all the way back up
    The 6th edict:
    "A thing of reference thing can hold either a null thing or a thing to any thing whose thing is assignment compatible with the thing of the thing" - ArchAngel, www.dictionary.com et al.
    JAR tutorial GridBag tutorial Inherited Shapes Inheritance? String.split(); FTP?

  5. #5
    Join Date
    Feb 2004
    Posts
    808
    Originally posted by baconsoft
    Hi MikeBarr81
    Thanks very much for your reply. However the pseudocode appears to require an initialised minValue. What if this minValue is set to zero and there is nothing lower than zero in the array? Would this code then return zero which is not even in the array of numbers? Maybe I am misinterpreting?

    The problem I am trying to complete gives the following code in which you are supposed to find the maximum value in the array ( I just wanted to find the smallest)

    Q. Using recursion, find the largest value in the array

    public class DataSet
    {

    .....
    public Dataset (int[] anArray) {.......}
    public int getMaximum () {.....}
    ......

    }

    If you or anyone could provide me with pseudocode or code to solve this one it would be very much appreciated. I have been trying but I cant do it.

    Thanks again
    Baconsoft
    neither method is suited to recursion, really.. not without using class-wide variables.. i'd do this:

    getMaximum()

    //calls findMax(start index, maxval, array)


    and in findMax:

    int findMax(index, maxval, array)

    //exit condition, if the end of the array is reched, return the max val

    //otherwise we arent exiting, so
    //have a look at the number at the index
    //if it is larger than our known max then
    //maxval is our new found maximum value

    //return the result of calling the method again with an incremented index and the known maxval
    The 6th edict:
    "A thing of reference thing can hold either a null thing or a thing to any thing whose thing is assignment compatible with the thing of the thing" - ArchAngel, www.dictionary.com et al.
    JAR tutorial GridBag tutorial Inherited Shapes Inheritance? String.split(); FTP?

  6. #6
    Join Date
    Sep 2004
    Posts
    150
    I'll submit my suggestion. Assuming there is a class wide array of ints called testArray.

    PHP Code:
    public int findMax()
    {
       return 
    findMaxHelper(0);
    }
      
    public 
    int findMaxHelper(int index)
    {
       if (
    index == testArray.length 1)
       return 
    testArray[index];
       
       else return 

       
    Math.max(testArray[index],   findMaxHelper(index 1));

    This is similar to Cjards but is dependent on a class wide array.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center