Benchmark test for the SumRecursive function

Now that we know how long the imperative function SumLoop takes, let's write a benchmark test to see how long our recursive version, namely SumRecursive, would take:

func benchmarkSumRecursive(s []int, b *testing.B) {
       for n := 0; n < b.N; n++ {
              SumRecursive(s)
       }
}

func BenchmarkSumRecursive40(b *testing.B) { benchmarkSumRecursive([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }

Results: It took 178 ns/op.

Tail call recursion is faster in languages such as Prolog, Scheme, Lua, and Elixir, and the ECMAScript 6.0-compliant JavaScript engines embrace the pure functional style of programming. So, let's give it a shot:

func SumTailCall(vs []int) int {
       if len(vs) == 0 {
              return 0
       }
       return vs[0] + SumTailCall(vs[1:])
}

Results of the benchmark test: It took 192 ns/op.

TCO: A tail call is where the last statement of a function is a function call. An optimized tail call has been effectively replaced with a GoTo statement, which eliminates the work required to set up the call stack before the function call and restore it afterward.

We could even use GoTo statements to further speed up the tail call recursion, but it would still be three times slower than the imperative version.

Why? This is because Go does not provide pure FP support. For example, Go does not perform TCOs, nor does it provide immutable variables.