Recursive vs iterative: same answers, and how deep the recursion goes
=====================================================================

n=1000, elements 0,2,4,...,1998: 2003 keys from -1 to 2001 (present and absent)
give identical answers from the iterative and the recursive version.

n=       10  absent key above the last element: result=-1, recursion frames=5 (iterative uses 0 extra frames)
n=    1,000  absent key above the last element: result=-1, recursion frames=11 (iterative uses 0 extra frames)
n=1,000,000  absent key above the last element: result=-1, recursion frames=21 (iterative uses 0 extra frames)
