Tail-Recursion in Go

Recursion (Recursion(..))

Recently I picked up the book “Learning Functional Programming In Go”. Whilst it is a decent book (I’d recommend starting with a more traditional FP language), the author mentions that one of the downsides of using Go for functional programming is that there’s no Tail-Call optimization, making recursive functions less appealing than they are in languages such as Haskell.

The author is correct in stating that there’s no Tail-Call optimization happening in the Go compiler (as of 1.13). But this does not stop us from writing Tail-Recursive functions in Go. It is true that in Haskell, you often will use functions that are tail-recursive without having to think about this, plus the language is lazily evaluated so how it deals with stackframes is quite different than Go for more reasons than TCO.

Recursion vs Tail-Recursion

Maybe the best way to explain the difference between the two of them is by showing the code snippets. Let’s take the traditional example of calculating a factorial.

The straightforward way of writing this recursively would look something like this:

func fact(n int) int {
   if n == 1 {
      return 1
   }
   return n * fact(n-1)
}

To turn this into a Tail-Recursive call, two things need to happen. First we need to introduce another function, the main calling function to which we provide our n. And next we need to define the function that will be called recursively.

The main difference between the two approaches will be in the way we perform the actual calculation.

func tailFact(n int) int {
   return factT(n-1, n)
}

func factT(n, current int) int {
   if n == 1 {
      return current
   }
   return factT(n-1, n * current)
}

Here, as you’ll notice, the last call of our factT function simply returns the next call to factT with the result (n*current) already evaluated.

To highlight the difference:

// recursive
return n * fact(n - 1)
// tail-recursive
return factT(n-1, n*current)

In the recursive way, our calling recursive function is not finished when we call the next step. This means that our recursive function is not ‘finished’ with all the calculations it should do until the deeper call returns.

In our tail-recursive way, the function has completed all the calculations (n*current) and passes that result on to the next function call.

Benchmarks

Using the following benchmark functions:

func BenchmarkFactorial(b *testing.B) {
   for i := 0; i < b.N; i++ {
      fact(20)
   }
}

func BenchmarkFactorialTail(b *testing.B) {
   for i := 0; i < b.N; i++ {
      tailFact(20)
   }
}

We get a result that looks somewhat like this:

BenchmarkFactorial-12           21109590                57.7 ns/op
BenchmarkFactorialTail-12       28621924                40.9 ns/op

So the FactorialTail function is faster than our normal recursive function.

Why is it faster?

In a normal recursive setting, each call to a recursive function needs to manage its own stackframe. Managing the stackframe (storing the variables, managing the instruction pointer for the CPU, ..) takes time. And because in a recursive setting, no function ever finishes until the deepest function returned, we need to manage all stackframes for intermediate calls.

In a tail-recursive call, each function finishes the evaluation entirely (our calculation of the factorial) and then calls the next function. Hence there is less overhead for managing stack frames. Our parent function does not do anything with the data it gets from the child function.

Anyway, this was just a quick sample of how you could do Tail-Recursion in Go, even though there’s no Tail-Call optimization that the compiler will do for you. This does not really take away from the author’s point that recursion in Go is simply less feasible than in Haskell though. 😃

If you enjoyed reading this, perhaps you would also enjoy my book “Functional Programming in Go”, which explores this topic and many more: https://www.amazon.ca/Functional-Programming-functional-testability-readability/dp/1801811164

If you liked this post consider following me here, on Medium, or alternatively on Twitter to get notified when I post another one. And if you liked this post specifically for Go, you might be interested in workwithgo.com where I aim to keep a curated list of Go vacancies from around the world.

📝 Read this story later in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.