Optimising recursive algorithms via memoisation

Naive implementations of some recursive algorithms might be expensive. For example, to calculate the Fibonacci numbers, the following code can be used:

fn fib1(n: Int) -> Int:
	if n <= 1:
		return n
	return fib1(n - 1) + fib1(n - 2)

Fibonacci numbers are usually defined such that f(0) = 0, f(1)=1, f(n) = f(n-1) + f(n-2). So in the code above there are two recursive calls. To try out the implementation let's implement a loop:

fn main():
	for n in range(45):
		print(n, fib1(n))

If you now run time mojo fib.mojo it turns out that the program takes several seconds to run (5s on my computer). This is because there are too many recursive calls with the same input.

We might now try to store the results of the function and simply take them from a dictionary on subsequent calls:

var fibmap = Dict[Int, Int]()

fn fib2(n: Int) -> Int:
	if n <= 1:
		return n
	var r = fibmap.get(n)
	if r:
		return r.value()[]
	else:
		var r = fib2(n - 1) + fib2(n - 2)
		fibmap[n] = r
		return r

The fibmap dictionary contains the Fibonacci numbers calculated so far so no recursive calls are needed to get f(n) if it's already been calculated. If we now run

fn main():
	for n in range(45):
		print(n, fib2(n))

the program finishes in less that a second.

The presented technique is usually called memoisation (or tabling) and is an algorithmic paradigm of dynamic programming.