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$. That is, you are given an array $A[1 .. n]$, such that some prefix $A[1 .. k]$ is sorted in increasing order, the corresponding sux $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$): $91316181923283137$ ...