0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$)

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.