Write a recursive algorithm for locating the max number amongst k integers.

Question

Iteratively, I know how to find the max number: Set Max = List[0], for k in range(len(List)), if List[k] > Max, Max = List[k]. Return Max.

Recursively, I'm not quite sure. Here is my idea: I understand that the objective of recursion is to start out with a base case that will eventually end the recursion; until then, the goal is to recursively call the function that will make the data get smaller and smaller. (until it will reach the base case). I am not really sure how to implement this though.

Answer 1

Use the fact that for finite sets $A$ and $B$ $$\max(\max(A),\max(B)) = \max(A \cup B)$$

A proposed algorithm findMax(X) would first check if $|X| \leq 2$, in which case just check which element is largest and return this (base case). Otherwise split X into two roughly equal length arrays $X_1,X_2$ and then return the larger of findMax($X_1$) and findMax($X_2$)

Answer 2

For two numbers $a_1,a_2$, define $$\texttt{Max}(a_1,a_2) = \begin{cases} a_1,& a_1>a_2\\ a_2,&a_1\leqslant a_2,\end{cases} $$ and for $n>2$ numbers $a_1,\ldots,a_n$ define $$\texttt{Max}(a_1,\ldots,a_n) = \texttt{Max}(\texttt{Max}(a_1,\ldots,a_{n-1}),a_n). $$ For $n=2$ the algorithm is trivially correct. Now assume it is correct for some $n\geqslant 2$. Then $$\texttt{Max}(a_1,\ldots,a_n)=a_j $$ for some $1\leqslant j\leqslant n$, so $a_i\leqslant a_j$ for $1\leqslant i\leqslant n$ and hence $$\texttt{Max}(\texttt{Max}(a_1,\ldots,a_n),a_{n+1})=\texttt{Max}(a_j,a_{n+1})\geqslant a_i $$ for $1\leqslant i\leqslant n+1$. By induction we conclude that $\texttt{Max}$ is correct for all $n$.

Answer 3

Consider this definition: \begin{align} \DeclareMathOperator{listmax}{listmax} \listmax(L=[H \mid T]) &= \begin{cases} L & \text{; if } \lvert L \rvert \le 1 \\ [ \max(H, \listmax(T)) ] & \text{; else} \end{cases} \end{align} where $L = [H \mid T]$ is the usual split of a list $L$ into head element $H$ and remaining (tail) list $T$, $\lvert L \rvert$ is the number of elements of the list $L$ and $\max$ is the maximum of two values, which can be expressed as $$ \max(x,y) = \frac{x + y + \lvert x - y \rvert}{2} $$

It returns a list which is either empty or contains the maximum element of $L$.