Help!! using recursion to search an array

[baconsoft]

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

[mikeBarr81]

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.

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

[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

[cjard]

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

[cjard]

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

[Philwx]

I'll submit my suggestion. Assuming there is a class wide array of ints called testArray.

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.