# 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*