1.Previous
3.Next

is not guaranteed without further analysis.

Implementation issues

In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:

* Wrapper function (at top)
* Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)
* Hybrid algorithm (at bottom) - switching to a different algorithm once data is small enough

On the basis of elegance, wrapper

1.Previous
3.Next