# How do you convert this iterative code to recursive?

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

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

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

Algorithm:

$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,\ldots,A[n]$):

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

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

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

This recursion splits the array $A,\ldots,A[n]$ into $A,\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,\ldots,A[n]$ is the same as the answer for $A,\ldots,A[n-1]$.