Recursive Linear Search
We looked at an iterative version of the
find function above. But what would it take to turn that function into a recursive function? While for this particular function, there is not a lot to be gained from the recursive version, it is still instructive to see how we would do it. We will find recursive functions more useful later on in the module.
In this case, to implement a recursive version of the function, we need to add a third parameter,
index, to tell us where to check in the array. We assume that at the beginning of a search,
index begins at 0. Then, if
number is not in location
index in the
index will be incremented before making another recursive call. Of course, if
number is in location
index, we will return the number of
index. The pseudocode for the
findR function is shown below.
function FINDR (NUMBER, ARRAY, INDEX) (1) if INDEX >= size of ARRAY then (2) return -1 (3) else if ARRAY[INDEX] == NUMBER (4) return INDEX (5) else (6) return FINDR (NUMBER, ARRAY, INDEX + 1) (7) end if (8) end function (9)
First, we check to see if
index has moved beyond the bounds of the array, which would indicate that we have searched all the locations in
number. If that is the case, then we return
-1 in line 3 indicating that we did not find
array. Next, we check to see if
number is found in
array[index] in line 4. If it is, the we are successful and return the index. However, if we are not finished searching and we have not found
number, then we recursively call
findR and increment
index by 1 to search the next location.
An example of using the
findR function is shown below. The top half of the figure shows the state of the data in the initial call to the
findR function (instance 1). The bottom half of the figure shows the recursive path through the function. The beginning of instance 1 shows the
if statement in line 2. In instance 1, since we have not searched the entire array (line 2) and
array is not equal to
number (line 4), we fall down to the
else part function and execute line 7, the recursive call. Since
0 in instance 1, we call instance 2 of the function with an
index of 1.
In instance 2, the same thing happens as in instance 1 and we fall down to the
else part of the
if statement. Once again, we call a new instance of
findR, this time with
index set at 2. Now, in instance 3,
array[index] is equal to
number in line 4 and so we execute the
return index statement in line 5. The value of
index (2) is returned to instance 2, which, in line 7, simply returns the value of 2 to instance 1. Again, in line 7, instance 1 returns that same value (2) to the original calling function.
Notice that the actual process of searching the array is the same for both the iterative and recursive functions. It is only the implementation of that process that is different between the two.