Question

Give a recursive algorithm for finding a mode of a list of integers. (A mode is an element in the list that occurs at least as often as every other element.)

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}mod\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\right.:\mathrm{integers}\mathrm{with}\mathrm{n}\ge 1) \\ \mathrm{L}:=\left\{{\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\right\} \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_1 \\ \mathrm{else} \\ \begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\mathrm{k}:=\mathrm{k}+1\end{array} \\ \mathrm{if}\mathrm{k}=\mathrm{n}\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_{\mathrm{n}} \\ \mathrm{else} \\ \begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\end{array} \\ \mathrm{else} \\ \mathrm{return}\mathrm{x} \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for finding a mode of a list of integers.

Give a recursive algorithm for computing finding a mode of a list of integers

Call the algorithm "mod" and the input is a list of integers.

$\text{procedure}mod\left(a_1,a_2,\dots ,a_n\text{: integers with}n\ge 1\right)$

When the list contains only 1 integer, then the mode is the remaining integer.

$$\begin{gathered} \mathrm{L}:=\left\{{\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\right\} \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_1 \end{gathered}$$

If the list contains more than 1 value, then check, if the last value in the list is repeated somewhere in the list. Remove this value along with all other repetitions of the value form the list, while represents the number of values that were deleted. If , then all elements in the list were deleted and therefore, there should be return of $a_n$. Otherwise, apply the algorithm to determine the mode of the reduced list,

which occurs times. If k > m , then$a_m$ is the mode. If k < m, then the mode is the mode of the reduced list.
else

$\begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\mathrm{k}:=\mathrm{k}+1\end{array}$

And,

$\begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\\ \text{else}\\ \text{return}\mathrm{x}\end{array}$

By combining all the steps, the required algorithm will be as follows.

$$\begin{gathered} \mathrm{procedure}mod\left({\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\right.:\mathrm{integers}\mathrm{with}\mathrm{n}\ge 1) \\ \mathrm{L}:=\left\{{\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{n}}\right\} \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_1 \\ \mathrm{else} \\ \begin{array}{r}\mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{n}}\right\}\mathrm{k}:=1\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}=1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{L}:=\mathrm{L}-\left\{{\mathrm{a}}_{\mathrm{i}}\right\}\mathrm{k}:=\mathrm{k}+1\end{array} \\ \mathrm{if}\mathrm{k}=\mathrm{n}\mathrm{then} \\ \mathrm{return}{\mathrm{a}}_{\mathrm{n}} \\ \mathrm{else} \\ \begin{array}{r}\mathrm{x}:=\mathrm{mod}\left(\mathrm{L}\right)\mathrm{m}:=0\\ \text{for}\mathrm{i}:=1\text{to}\mathrm{n}-1\\ \text{if}{\mathrm{a}}_{\mathrm{n}}={\mathrm{a}}_{\mathrm{i}}\text{then}\\ \mathrm{m}:=\mathrm{m}+1\\ \text{if}\mathrm{k}\ge \mathrm{m}\text{then}\\ \text{return}{\mathrm{a}}_{\mathrm{n}}\end{array} \\ \mathrm{else} \\ \mathrm{return}\mathrm{x} \end{gathered}$$

Therefore, the recursive algorithm is shown above.