Question

Prove that the recursive algorithm that you found in Exercise 10 is correct.

Short answer

It is proved that the recursive algorithm is correct.

Step-by-step solution

Consider the recursive algorithm

The recursive algorithm is,

$$\begin{gathered} \mathbf{procedure}\mathbf{}\mathbf{largest}\mathbf{}\mathbf{(}{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{a}}_{\mathbf{n}}\mathbf{\text{: integers with}}\mathbf{n}\mathbf{\ge }\mathbf{1}\mathbf{)} \\ \mathbf{if}\mathbf{}\mathbf{n}\mathbf{=}\mathbf{1}\mathbf{}\mathbf{then} \\ \mathbf{return}\mathbf{}{\mathbf{a}}_{\mathbf{1}} \\ \mathbf{else} \\ \mathbf{return}\mathbf{}\mathbf{max}\mathbf{}\mathbf{(}\mathbf{largest}\mathbf{}\mathbf{(}{\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{\left)}{\mathbf{a}}_{\mathbf{n}}\mathbf{\right)} \end{gathered}$$

Prove that the algorithm obtained in Exercise 10 is correct

This can be proved by Strong Induction.

For basic step, n = 1 .

The algorithm returns , which is also the maximum if the list only contains the integer , and thus the algorithm is correct for the basis step.

Assume that the algorithm is correct for the positive integer k with k > 1 . Then

I argest$\left(a_1,a_2,\dots ,a_k\right)=max\left(a_1,a_2,\dots ,a_k\right)$

It is required to prove that the algorithm is also correct for k + 1.

role="math" localid="1668584910378" $\begin{array}{r}\mathrm{I}\mathrm{argest}\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{k}},{\mathrm{a}}_{\mathrm{k}+1}\right)=max\left(\mathrm{largest}\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{k}}\right),{\mathrm{a}}_{\mathrm{k}+1}\right)\\ =max\left(max\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{k}}\right),{\mathrm{a}}_{\mathrm{k}+1}\right)\\ =max\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{k}},{\mathrm{a}}_{\mathrm{k}+1}\right)\end{array}$

It can be observed that the algorithm gives the maximum of the first k + 1 elements for the integer k + 1. Therefore, the algorithm is correct for the integer k + 1.

Hence, by the principle of mathematical induction, the recursive algorithm is correct.