= Solution
For a nonnegative integer parameter $n$, make both branches of a <structural recursion> execute:
``
sml
fun binaryWalk 0 = ()
| binaryWalk n = (binaryWalk (n - 1); binaryWalk (n - 1));
``
The semicolon sequences two calls, so this is not a conditional choosing just one branch. The recursion tree has $2^n$ leaves and $2^{n+1}-1$ calls. Its <time complexity> satisfies $T(n)=2T(n-1)+\Theta(1)$, giving \b[$\Theta(2^n)$]. Here $n$ is the parameter specified by the question, not its binary encoding length; only $\Theta(n)$ calls are simultaneously on the stack.
Back to article page
