How do you convert the following algorithm from the iterative paradigm to the recursive paradigm?

Input: array $A[1],\ldots,A[n]$

Output: last index $i$ such that $A[i] = i$, or $-1$ if none


$index \gets -1$

For $i \gets 1,\ldots,n$:

$\quad$ If $A[i] = i$: $index \gets i$

Return $index$


Here is one way to convert your code into a recursive procedure:

procedure MagicIndex($A[1],\ldots,A[n]$):

$\quad$ If $n = 0$: Return $-1$

$\quad$ If $A[n] = n$: Return $n$

$\quad$ Return MagicIndex($A[1],\ldots,A[n-1]$)

This recursion splits the array $A[1],\ldots,A[n]$ into $A[1],\ldots,A[n-1]$ and $A[n]$, but any other way of splitting it into two contiguous halves will do.

Why does this work? Ignoring the trivial case $n=0$, the algorithm considers two cases:

  1. If $A[n] = n$ then the answer is always $n$.

  2. Otherwise, the last index such that $A[i] = i$ (if any) satisfies $i \leq n-1$, and so the answer for $A[1],\ldots,A[n]$ is the same as the answer for $A[1],\ldots,A[n-1]$.


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.