|
|
|
|
|
|
|
Problem-Solving Case Study Minimum Value in an Integer Array |
|
|
|
|
|
|
|
|
Problem: Find the minimum value in an integer array indexed from 0 through length - 1. |
|
|
|
|
|
|
|
|
Discussion: This problem is easy to solve iteratively, but the objective here is to think recursively. The problem has to be stated in terms of a smaller case of itself. Because this is a problem using an array, a smaller case involves a smaller array. The minimum value in an array of length length is the smaller of list[length-1] and the smallest value in the array from list[0] ... list[length-2]. |
|
|
|
|
|
|
|
|
Minimum (In: list, length) |
|
|
|
|
|
|
|
|
Set minSoFar = Minimum(list, length-1)
IF list[length-1] < minSoFar
Return list[length-1]
ELSE
Return minSoFar |
|
|
|
|
|
|
|
|
|
This algorithm looks reasonable. All we need is a base case. Because each recursive call reduces the length of the array by one, our base case occurs when length is 1. We know the minimum value for this call: it is the only value in the array. |
|
|
|
|
|
|
|
|
int Minimum(
/* in */ const int list[], // Array of integers to examine
/* in */ int length ) // One greater than index of
// last number in array
// Precondition:
// list[0..length-1] are assigned
// && length >= 1
// Postcondition:
// Function value == smallest number in list[0..length-1]
{
int minSoFar; // Minimum returned from recursive call
if (length == 1)
return list[0]; // Base case |
|
|
|
|
|
