Recursive fibonacci with memoization

Recursive functions can be used for when you have one big problem and want to split it up into many smaller problems or “divide and conquer” as it is commonly refered to.

The fibonacci sequence is a popular example to use in recursive functions since the function calls mirrors the actual formula¹. Below we have implemented a simple recursive function in golang.

// Example 1 - Recursive fibonacci
func fib_rec(number int) int {
    if number < 2 {
        return number;
    }
    return fib_rec(number-2) + fib_rec(number-1)
}

However in practice this could be considered an inefficient solution which leads to an unecessary amount of function calls since each function call for N>2 will spawn two more function calls. One way of solving this is by the use of memoization². Memoization an optimization technique more commonly known in functional programming languages but that doesn’t mean we can’t use it here. What it essentialy means is we’re saving the output of any function call in memory and use that saved output instead of the function call for any repeated calls with the same input.

// Example 2 - Recursive fibonacci with memoization
var cache [N+1]int

func fib_mem(number int) int {
    if number < 2 {
        return number;
    }
    if cache[number] == 0 { // Save to cache if not set
        cache[number] = fib_mem(number-2) + fib_mem(number-1)
    }
    return cache[number]
}

To visualize this I’ve made a tree where the number is the input parameter of a function call

 With memoization |      Without memoization
------------------+---------------------------------
                  |          ____ 6 ____
                  |         /           \
          6       |        4           _ 5 _
         / \      |       / \         /     \
        4   5     |      2   3       3       4
       / \        |     /   / \     / \     / \
      2   3       |    1   1   2   1   2   2   3
     /   /        |           /       /   /   / \
    1   1         |          1       1   1   1   2
                  |                             /
                  |                            1

As you may note F(1) is actually called twice, once from F(2) and once for F(3). This can easily be avoided by storing cache1=1 before starting the recursion and instead only return number if number==0 but even if we don’t F(1) will only be called twice no matter how big N we’re using, this because any subsequent calls to F(4) will just look up the memoized the output of F(4) instead of traversing further down the tree. Even if this reduction of function calls does not look huge, what we’re really doing is reducing the complexity from O(2ⁿ)³ to O(n) the benefit of which becomes more appearant the higher N, for each higher number of N we essentially need to copy the biggest branch of the existing tree and run through it all again, with memoization we’re storing the result of each branch in that tree and use that cache to avoid function calls when the result is known from a previous calculation. If N was 50 we’re talking many billions of function calls compared to 50.

Other solutions

As a sidenote it can be worth noting that using a standard iterative function can be considered just as fast and easier to understand. The Nth fibonacci can also more efficiently be solved by using various mathematical techniques: matrix exponetiation, fast doubling, or rounding but I consider that out of scope for this post.

// Example 3 - Iterative fibonacci
func fib_iter(number int) int {
    first, second := 0, 1
    for i := 0; i < number; i++ {
        first, second = second, first+second
    }
    return first
}