Question

Give a recursive algorithm for finding the minimum of a finite set of integers, making use of the fact that the maximum of n integers is the smaller of the last integer in the list and the minimum of the first n - 1 integers in the list.

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}\mathrm{smallest}\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\text{:integers with}\mathrm{n}\ge 1\right) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_1 \\ \mathrm{else} \\ \mathrm{return}\min \left(\mathrm{smallest}\left({\mathrm{a}}_1{\mathrm{a}}_2,.....,{\mathrm{a}}_{\mathrm{n}-1}\right){\mathrm{a}}_{\mathrm{n}}\right) \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for the minimum of a finite set of integers.

Give a recursive algorithm for computing the minimum of a finite set of integers

Call the algorithm "smallest" and the input is finite set of integers${\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}$.

procedure smallest$\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}:\mathrm{integer}\mathrm{with}\mathrm{n}\ge 1\right)$

When the set of integers contains only 1 integer, then the maximum is the integer itself.

if n = 1 then

return$a_1$

The sum of the maximum of the first n integers is the minimum of the first n - 1 integers (when n is greater than 1 ) and the $n^{th}$integer $a_n$.

else

$\mathrm{return}\min \left(\mathrm{smallest}\left({\mathrm{a}}_1,{\mathrm{a}}_2,......,{\mathrm{a}}_{\mathrm{n}-1}\right){\mathrm{a}}_{\mathrm{n}}\right)$

By combining all the steps the algorithm is obtained as,

$$\begin{gathered} \mathrm{procedure}\mathrm{smallest}\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\text{:integers with}\mathrm{n}\ge 1\right) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_1 \\ \mathrm{else} \\ \mathrm{return}\min \left(\mathrm{smallest}\left({\mathrm{a}}_1{\mathrm{a}}_2,.....,{\mathrm{a}}_{\mathrm{n}-1}\right){\mathrm{a}}_{\mathrm{n}}\right) \end{gathered}$$

Therefore, the recursive algorithm is shown above.