In Java, I want to create a recursive method that looks for a specific integer in an array and when it finds it, it returns the array index.
My code so far is:
private static int contains(int[] data, int value, int index)
{
if (index >data.length)
{
return 0;
}
if(data[index] == value)
{
return index;
}
else
{
return contains(data,value,index);
}
}
The method does not return the right index. what am I doing wrong?
First, 0 is a valid index, the first index in an array. If you've gone off the end of the array in your base case, return -1 instead to indicate "not found". Also, you've gone off the end of the array when index reaches data.length, not when it has passed data.length, so you need to change your if condition here.
Second, your recursive call sends the same parameters, which will result in an infinite loop if the value isn't found in the initial recursive call. You want to look at the next index in the next recursive call, so pass index + 1 instead of index when calling contains again.
Well, when you want to do a recursive method, you need two things:
A base case
(in your method this is when index == data.length and index == value).
A recursive call if the value you have in the actual call is not a base case.
Then inside your method you have to do a new call to your method with a new value of the variable that is incrementing or decrementing.
In your case this variable is index.
Well, with all this, you have to think:
Your code would be something like this:
private static int contains(int[] data, int value, int index){
if(index == data.length) {
return -1;
}else if (data[index] == value){
return index;
}else{
return contains(data,value,index+1);
}
}
In recursion, you divide the problem into smaller similar problems, until you reach a point where the method/function can't or doesn't need to call itself anymore. In my version for contains, given below, each time the method is called, it checks if either it is past the end of the array ("before" the first element) or an occurrence of value has been found. If not, the method calls itself to look for the result. The method returns -1 if the element is not found - this can be a suitable choice, since no array element is at index -1. Also, the method should be called with the length of data - 1 as the third argument.
private static int contains( int[] data, int value, int index )
{
/* Base cases - end of recursion: */
if ( ( index == -1 ) || ( data[ index ] == value ) )
{
return index;
}
/* Recursion: */
return contains( data, value, index - 1 );
}