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.