# Leonardo numbers

Because Fibonacci numbers are quite abused in programming, a similar concept.

L0 = L1 = 1 Ln = Ln-2 + Ln-1 + 1

My first impulse is to describe them in recursive way:

def leonardo(n): if n in (0, 1): return 1 return leonardo(n - 2) + leonardo(n - 1) + 1 for i in range(NUMBER): print('leonardo[{}] = {}'.format(i, leonardo(i)))

But this is not very efficient to calculate them, as for each is calculating all the previous ones, recursively.

Here memoization works beautifully

cache = {} def leonardo(n): if n in (0, 1): return 1 if n not in cache: result = leonardo(n - 1) + leonardo(n - 2) + 1 cache[n] = result return cache[n] for i in range(NUMBER): print('leonardo[{}] = {}'.format(i, leonardo(i)))

Taking into account that it uses more memory, and that calculating the Nth element without calculating the previous ones is also costly.

I saw this on Programming Praxis, and I like a lot the solution proposed by Graham on the comments, using an iterator.

def leonardo_numbers(): a, b = 1, 1 while True: yield a a, b = b, a + b + 1

The code is really clean.

Pingback: All you need is cache | Wrong Side of Memphis