Recursion: (Using The Module One Readings) Consider the following algorithm. int
ID: 3883805 • Letter: R
Question
Recursion: (Using The Module One Readings)
Consider the following algorithm.
int max(int a, int b) {
if (a > b) return a;
}
int findMax(int[] numList, int begin, int end) {
if (begin > end) return -1;
else if (begin == end) return numList[end];
else
return (max(numList[begin], findMax(numList, begin, end-1)));
}
Assume the max() function returns the larger of the two values passed to it, and that it works correctly. The other function, findMax() is the one of interest to us. findMax() is suppose to find the largest value in the numList array passed to it within the bounds indicated by begin and end. It does this by using max() to compare the first element in the array and the maximum of the rest of the list, determined recursively.
But, the algorithm has one or more flaws that prevent it from working correctly. This
flaw(s) is (are) logical, not syntactic (this is pseudo-code after all). The potential flaws are:
1. if (begin > end) return -1;
2. else if (begin == end) return numList[end];
3. else
return (max(numList[begin], findMax(numList, begin, end-1)));
Your team’s task is to determine which of these are actual logical errors that would cause this algorithm to not find the maximum of the values in the array. Are the error(s)?
A. 2?
B. 3?
C. 1&2? D. 2&3?
Explanation / Answer
The error is with (3).
The statement should be,
else
return (max(numList[end], findMax(numList,
begin,end-1)));
It is due to the reason that in the given line 3 in the question, the findMax() function recursively finds the maximum element in the remaining list excluding the last element. Hence, to get the maximum element, we should compare the last element and the max element returned by findMax () . Hence, in place of
numList[begin], we would use numList[end].
Hence, the correct psuedocode should be,
int findMax(int[] numList, int begin, int end)
{
if (begin > end)
return -1;
else if(begin == end)
return numList[end];
else
return (max(numList[end], findMax(numList,
begin,end-1)));
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.