↓Skip to main content

Review of Algorithms In Go - Part 1 - Recursion

·1153 words·6 mins
Pangolin
Author
Pangolin

This is a basic review of recursion for Go programmers. It was originally written in a Go Jupyter Notebook.

Recursion - A function that calls itself. #

Recursive functions must have an exit clause, if they aren’t going to be an infinite loop. The exit clause is the condition in which case the function should return a value and not call itself. Without an exit clause, the function will just call itself forever.

Recursion has a few key use cases, where back tracking is important, but generally speaking, most things that can just be done with a for loop, should be done with a for loop - as we’ll see, recursion can often cause performance issues. One way to mitigate this is with a technique call memoization, we will also discuss here.

Here is a simple recursive function called factorial, as you may expected, it calculates the factorial of a positive number:

import "fmt"

func factorial(num uint) uint {
    if num == 1 {
        return num
    }
    return num * factorial(num - 1)
}

fmt.Sprintf("10! = %d", factorial(10))

10! = 3628800

Basic Fibonnaci Sequence #

Fibonnaci Sequences are classic examples of recursive functions. Here is the basic implementation of a fibonnaci sequence.

func fib(n uint) uint {
    if n == 0 || n == 1 {
        return n
    }
    return fib(n - 2) + fib(n - 1)
}


fib(12)

144

Memoization #

This function will work, but it is very inefficient. We will not be able to exit any call until fib(0) || fib(1) are called. Each time we run fib, we need to call fib 2 more times. This will end up calling our function 465 times for fib(12)!!

times_run := 0

func fib(n uint) uint {
    times_run++
    if n == 0 || n == 1 {
        return n
    }
    return fib(n - 2) + fib(n - 1)
}


fmt.Printf("fib(12) = %d\n", fib(12))
fmt.Sprintf("The fib function was run %d times!!!", times_run)

fib(12) = 144
The fib function was run 465 times!!!

In order to better understand this, lets run a modified function - with print statements for fib(6) - that equals 8 and should run 25 times:

i := 0

func fib(n uint) uint {
    i++
    fmt.Printf("%d: ENTERED fib(%d)\n", i, n)
    if n == 0 || n == 1 {
        fmt.Printf("\tCALLING fib(%d)\n", n)
        return n
    }
    fmt.Printf("\tCALLING fib(%d) and fib(%d)\n", n - 2, n - 1)
    ans := fib(n - 2) + fib(n - 1)
    return ans
}


result := fib(6)

1: ENTERED fib(6)
	CALLING fib(4) and fib(5)
2: ENTERED fib(4)
	CALLING fib(2) and fib(3)
3: ENTERED fib(2)
	CALLING fib(0) and fib(1)
4: ENTERED fib(0)
	CALLING fib(0)
5: ENTERED fib(1)
	CALLING fib(1)
6: ENTERED fib(3)
	CALLING fib(1) and fib(2)
7: ENTERED fib(1)
	CALLING fib(1)
8: ENTERED fib(2)
	CALLING fib(0) and fib(1)
9: ENTERED fib(0)
	CALLING fib(0)
10: ENTERED fib(1)
	CALLING fib(1)
11: ENTERED fib(5)
	CALLING fib(3) and fib(4)
12: ENTERED fib(3)
	CALLING fib(1) and fib(2)
13: ENTERED fib(1)
	CALLING fib(1)
14: ENTERED fib(2)
	CALLING fib(0) and fib(1)
15: ENTERED fib(0)
	CALLING fib(0)
16: ENTERED fib(1)
	CALLING fib(1)
17: ENTERED fib(4)
	CALLING fib(2) and fib(3)
18: ENTERED fib(2)
	CALLING fib(0) and fib(1)
19: ENTERED fib(0)
	CALLING fib(0)
20: ENTERED fib(1)
	CALLING fib(1)
21: ENTERED fib(3)
	CALLING fib(1) and fib(2)
22: ENTERED fib(1)
	CALLING fib(1)
23: ENTERED fib(2)
	CALLING fib(0) and fib(1)
24: ENTERED fib(0)
	CALLING fib(0)
25: ENTERED fib(1)
	CALLING fib(1)

This is very inefficient, for example, look how many times we calculate fib(0)!! We should only be doing that once!

SIDE NOTE: Another thing to notice is that while we seem to call fib(4) and fib(5) we only enter fib(4) - this is because we can’t enter to fib(5) until we finish fib(4). This is due to something called a call stack - which I will discuss more when I post about dynamic programming. ;)

fmt.Printf("fib(6) = %d\n", result)
fmt.Sprintf("Ran %d times!\n", i)

fib(6) = 8
Ran 25 times!

One method of reducing the amount of times the function is called is a method called memoization. Since the fibonacci of any given input number will always be the same, we don’t need to repeat it each time. We can just map the result we get to the input the first time. If we’ve already calculated the fibonacci of any number, we just pull it out of our hash map instead of calculating it again. Here we can reduce the number of fib(6) from 25 to just 11!

mi := 0

func fibInner(n uint, m map[uint]uint) uint {
        mi++
        fmt.Printf("%d) ENTERED fibInner(%d)\n", mi, n)
        if n == 0 || n == 1 {
            fmt.Printf("\t%d) CALLING fibInner(%d)\n", mi, n)
            return n
        }
        if m[n] == 0 {
            fmt.Printf("\tCALLING fibInner(%d) and fibInner(%d)\n", n-2, n-1)
            m[n] = fibInner(n-2, m) + fibInner(n-1, m)
        }
        return m[n]
    }

func mfib(n uint) uint {
    m := make(map[uint]uint);

    return fibInner(n, m)
}

mresult := mfib(6)

1) ENTERED fibInner(6)
	CALLING fibInner(4) and fibInner(5)
2) ENTERED fibInner(4)
	CALLING fibInner(2) and fibInner(3)
3) ENTERED fibInner(2)
	CALLING fibInner(0) and fibInner(1)
4) ENTERED fibInner(0)
	4) CALLING fibInner(0)
5) ENTERED fibInner(1)
	5) CALLING fibInner(1)
6) ENTERED fibInner(3)
	CALLING fibInner(1) and fibInner(2)
7) ENTERED fibInner(1)
	7) CALLING fibInner(1)
8) ENTERED fibInner(2)
9) ENTERED fibInner(5)
	CALLING fibInner(3) and fibInner(4)
10) ENTERED fibInner(3)
11) ENTERED fibInner(4)

``

fmt.Printf("mfib(6) = %d\n", mresult)
fmt.Sprintf("Ran %d times!\n", mi)

mfib(6) = 8
Ran 11 times!

For the case of fib(12) we can reduce it from 465 to just 23!

mi = 0

func fibInner(n uint, m map[uint]uint) uint {
        mi++
        if n == 0 || n == 1 {
            return n
        }
        if m[n] == 0 {
            m[n] = fibInner(n-2, m) + fibInner(n-1, m)
        }
        return m[n]
    }

func mfib(n uint) uint {
    m := make(map[uint]uint);

    return fibInner(n, m)
}

func fib(n uint) uint {
    if n == 0 || n == 1 {
        return n
    }
    return fib(n - 2) + fib(n - 1)
}


mresult := mfib(12)

fmt.Printf("mfib(12) = %d\n", mresult)
fmt.Sprintf("mfib ran %d times!\n", mi)

mfib(12) = 144
mfib ran 23 times!

if we remove the incrementer statements and just time how long it takes to finish each function, we can see how much more time it takes to fun a fibonacci sequence on a slightly higher number like 35

import "time"

func fibInner(n uint, m map[uint]uint) uint {
        if n == 0 || n == 1 {
            return n
        }
        if m[n] == 0 {
            m[n] = fibInner(n-2, m) + fibInner(n-1, m)
        }
        return m[n]
    }

func mfib(n uint) uint {
    m := make(map[uint]uint);

    return fibInner(n, m)
}

start := time.Now()
mfib(35)
end := time.Now()

executionTime := end.Sub(start)

fmt.Sprintf("Executed in %v", executionTime)

Executed in 366.694µs

Well that was rather fast with memoization! Let’s see how long it takes without memoization:

start := time.Now()
fib(35)
end := time.Now()

executionTime := end.Sub(start)

fmt.Sprintf("Executed in %v", executionTime)

Executed in 3.045922618s

Holy Moly!! That was over 3 seconds!!

My results indicate that with memoization, it is 8,306 times faster!!

Results may vary slightly.