Leonardo number

The Leonardo numbers are a sequence of numbers given by the recurrence:

Edsger W. Dijkstra used them as an integral part of his smoothsort algorithm, and also analyzed them in some detail.

Computing a second-order recurrence relation recursively and without memoization requires L(n) computations for the n-th item of the series.