Challenge: Recursion

Task

Suppose you are given a sorted array of $n$ distinct numbers that has been rotated $k$ steps for some unknown integer $k$ between 1 and $n$. In other words, you are given an array $A[1 .. n]$ such that some prefix $A[1 .. k]$ is sorted in increasing order, the corresponding suffix $A[k + 1 .. n]$ is sorted in increasing order, and $A[n] < A[1]$. For example, you might be given the following element array (where $k = 10$): $9 \ 13 \ 16 \ 18 \ 19 \ 23 \ 28 \ 31 \ 37 \ 42 \ 1 \ 3 \ 4 \ 5 \ 7 \ 8$ ...