Algorithms Techniques - Part 3: Recursion

An overview of recursive algorithms.

A recursive algorithm is an algorithm that calls itself repeatedly until a certain condition is met. For problem solving, it means that we can apply the same algorithm multiple times to a smaller subset of the original input until we find a solution.

Imagine you have a glass full of M&M’s and you want to empty the glass, but you can only remove one M&M at the time. It would work like this:

Is the glass empty? No, remove 1 M&M.
Is the glass empty? No, remove 1 M&M.
Is the glass empty? No, remove 1 M&M.
… Is the glass empty? Yes, stop.

Using pseudo-code:

function empty_glass(int n):
    if n equals 0:
        // Do nothing
    else:
        empty_glass(n - 1)

This is a very simple example that could’ve been solved using a simple for loop, but recursion is still the best (or at least more elegant) approach for some classes of problems.

Fibonacci

A classic example of a problem that can be solved using recursion is calculating a Fibonacci number. Fibonacci numbers form a sequence starting with 1 and 1 where each number is the sum of the previous 2 numbers:
1, 1, 2, 3, 5, 8, …

And we have the following Fibonacci numbers:
The 1st number is 1
The 2nd number is 1
The 3rd number is 2
The 4th number is 3
The 5th number is 5
The 6th number is 8
… and so on

Being n the Fibonacci number you want, this can be expressed as:

F(n) = F(n - 1) + F(n - 2)

Let’s see the implementation in Go:

package main

import "fmt"

func Fb(n int) int {
    // If n is 0 or 1, return it
    if n < 2 {
        return n
    }

    return Fb(n-1) + Fb(n-2)
}

func fibonacci() {
    for n := 1; n <= 6; n++ {
        fib := Fb(n)
        fmt.Printf("Fibonnacci (%d): %d\n", n, fib)
    }
}

Running this will produce:

Fibonnacci (1): 1
Fibonnacci (2): 1
Fibonnacci (3): 2
Fibonnacci (4): 3
Fibonnacci (5): 5
Fibonnacci (6): 8

The good and the bad

Recursion has its pros and cons. For some problems, like traversing a tree, recursion provides an easier to understand and somewhat more elegant solution. However, it can be slower, especially if the recursion is too deep.

Running a quick benchmark on the code above will show us that the speed decreases the deeper the recursion goes:

package main

import "testing"

// This is the actual test
func benchmarkFb(i int, b *testing.B) {
    for n := 0; n < b.N; n++ {
        Fb(i)
    }
}

// The functions below are different benchmarks, each with a different input
// to our Fibonacci function.

func BenchmarkFb1(b *testing.B) {
    benchmarkFb(1, b)
}

func BenchmarkFb2(b *testing.B) {
    benchmarkFb(2, b)
}

func BenchmarkFb3(b *testing.B) {
    benchmarkFb(3, b)
}

func BenchmarkFb10(b *testing.B) {
    benchmarkFb(10, b)
}

func BenchmarkFb25(b *testing.B) {
    benchmarkFb(25, b)
}

func BenchmarkFb45(b *testing.B) {
    benchmarkFb(45, b)
}

We can see that in the output:

BenchmarkFb1-4                  434873206                2.55 ns/op
BenchmarkFb2-4                  174979096                6.76 ns/op
BenchmarkFb3-4                  100525826               11.8 ns/op
BenchmarkFb10-4                  2466976               457 ns/op
BenchmarkFb25-4                     1856            613773 ns/op
BenchmarkFb45-4                        1        9282143600 ns/op

Cover picture by Simon Hurry via Unsplash