Any idea why Go seems to be relatively slow on a recursive fibonacci?

The reason is a combinatorial explosion of recursive computations. In Algorithms 101 they usually explain why Dru Jensen's recursive algorithm is the terrible way to calculate the Fibonacci numbers: http://www.cs.toronto.edu/~gfb/csc104/2016W/Lectures/CSC104.2016W.Week-7.Lecture.Fibonacci.I.pdf. The fib procedure calls itself twice each time it is invoked. By design, Go doesn't have tail recursion: Tail call. By design, Go starts with a very small stack for each goroutine, which it has to grow explosively. No Go programmer would want to use this algorithm, which is around 382,358,169 times slower than the next slowest and 18,593,103,127 times slower than the fastest, so optimization, which would sacrifice performance elsewhere, is pointless.

Here are some Go benchmark results:

$ go test fib_test.go -bench=.
BenchmarkDruJensen-8             1    9482482595 ns/op
BenchmarkPeterSO1-8       50000000            24.8 ns/op
BenchmarkPeterSO2-8     2000000000             0.51 ns/op

fib_test.go:

package main

import (
    "fmt"
    "testing"
)

// Dru Jensen: https://github.com/drujensen/fib
func fib(n uint64) uint64 {
    if n <= 1 {
        return 1
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func BenchmarkDruJensen(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fib(46)
    }
}

// PeterSO
func fibonacci1(n int) uint64 {
    f := uint64(0)
    a, b := uint64(0), uint64(1)
    for i := 0; i < n; i++ {
        f, a, b = a, b, a+b
        if a > b {
            break
        }
    }
    return f
}

func BenchmarkPeterSO1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fibonacci1(46)
    }
}

var fibonaccis = []uint64{
    0,
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
    2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
    317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
    14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
    267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073,
    4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
    53316291173, 86267571272, 139583862445, 225851433717, 365435296162,
    591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881,
    6557470319842, 10610209857723, 17167680177565, 27777890035288,
    44945570212853, 72723460248141, 117669030460994, 190392490709135,
    308061521170129, 498454011879264, 806515533049393, 1304969544928657,
    2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464,
    14472334024676221, 23416728348467685, 37889062373143906,
    61305790721611591, 99194853094755497, 160500643816367088,
    259695496911122585, 420196140727489673, 679891637638612258,
    1100087778366101931, 1779979416004714189, 2880067194370816120,
    4660046610375530309, 7540113804746346429, 12200160415121876738,
}

// PeterSO
func fibonacci2(n int) uint64 {
    return fibonaccis[n]
}

func BenchmarkPeterSO2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fibonacci2(46)
    }
}

TL;DR My conclusion up to now is, that we probably should avoid recursion in favour of iterative algorithms principally, as long as there is no tail call optimisation in Go. If not using recursion, Go seems to be insanely fast :-)

Out of curiosity I compared another (simpler) iterative algorithm to Peter's version (BTW, you need to change i < n to i <= n to get the correct Fibonacci of 46). Interestingly, in main.go order matters, if not using the compiled variant. The second function call is the faster. We need to use the benchmark to get objective results, that are like this:

go test -bench .
BenchmarkFibIt-4        100000000               18.5 ns/op
BenchmarkFibP-4         50000000                29.1 ns/op
BenchmarkFib-4                 1        12008314197 ns/op

By not using variable f but directly using x, it gets a bit faster ;-) To my surprise, the uncompiled variant of running main.go is nearly as fast as the compiled one, sometimes it's even faster!

My conclusion up to now is, that we probably should avoid recursion in favour of iterative algorithms principally, as long as there is no tail call optimisation in Go.

main.go:

package main

import (
    "fmt"
    "log"
    "time"
)

func fib(n int) uint64 {
    if n <= 1 {
        return 1
    }
    return fib(n-1) + fib(n-2)
}

func fibIt(n int) uint64 {
    var x, y uint64
    x, y = 0, 1
    for i := 0; i < n; i++ {
        // c <- x
        x, y = y, x+y
    }
    return x
}

func fibP(n int) uint64 {
    f := uint64(0)
    a, b := uint64(0), uint64(1)
    for i := 0; i <= n; i++ {
        f, a, b = a, b, a+b
        if a > b {
            break
        }
    }
    return f
}

func main() {
    var start time.Time
    var elapsed time.Duration

    start = time.Now()
    fibIt(46)
    elapsed = time.Since(start)
    fmt.Println("Iterative Fibonacci of 46 took", elapsed)

    start = time.Now()
    fibP(46)
    elapsed = time.Since(start)
    fmt.Println("Peter's Iterative Fibonacci of 46 took", elapsed)

    start = time.Now()
    fib(46)
    elapsed = time.Since(start)
    fmt.Println("Recursive Fibonacci of 46 took", elapsed)
}

main_test.go:

package main

import (
    "testing"
)

func BenchmarkFibIt(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fibIt(46)
    }
}

func BenchmarkFibP(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fibP(46)
    }
}

func BenchmarkFib(b *testing.B) {
    for i := 0; i < b.N; i++ {
        fib(46)
    }
}