Fibonacci sequence shootout between C, Go, and Haskell.

fib.hs

import System.Environment

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

main = do
	args <- getArgs
	let n = read (args !! 0)
	print (fib n)

fib_loop.c

#include <inttypes.h>
#include <stdio.h>

uint64_t fib(int n) {
	if (n < 2) {
		return n;
	}
	int i;
	uint64_t i1 = fib(1);
	uint64_t i2 = fib(0);
	uint64_t tmp;
	for (i = 2; i < n; i++) {
		tmp = i1;
		i1 = i1+i2;
		i2 = tmp;
	}
	return i1 + i2;
}

int main(int argc, char *argv[]) {
	int n = atoi(argv[1]);
	printf("%" PRIu64 "\n", fib(n));
	return 0;
}

fib_loop.go

package main

import (
	"flag"
	"fmt"
	"strconv"
)

func fib(n int) int {
	if n < 2 {
		return n
	}
	i1, i2 := fib(1), fib(0)
	for i := 2; i < n; i++ {
		i1, i2 = i1+i2, i1
	}
	return i1 + i2
}

func main() {
	flag.Parse()
	n, _ := strconv.Atoi(flag.Arg(0))
	fmt.Println(fib(n))
}

fib_recurse.c

#include <inttypes.h>
#include <stdio.h>

uint64_t fib(int n) {
	if (n < 2) {
		return n;
	}
	return fib(n-1) + fib(n-2);
}

int main(int argc, char *argv[]) {
	int n = atoi(argv[1]);
	printf("%" PRIu64 "\n", fib(n));
	return 0;
}

fib_recurse.go

package main

import (
	"flag"
	"fmt"
	"strconv"
)

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

func main() {
	flag.Parse()
	n, _ := strconv.Atoi(flag.Arg(0))
	fmt.Println(fib(n))
}

fib_shootout.sh

#!/bin/bash

function measure {
	/usr/bin/time --format '%E sec, %M Kbytes' $@
}

echo "=== C (recursive) ==="
gcc -O2 fib_recurse.c
measure ./a.out $1

echo "=== C (loop) ==="
gcc -O2 fib_loop.c
measure ./a.out $1

echo "=== Go (recursive) ==="
go build fib_recurse.go
measure ./fib_recurse $1

echo "=== Go (loop) ==="
go build fib_loop.go
measure ./fib_loop $1

echo "=== Haskell ==="
ghc -O fib.hs
measure ./fib $1

results.txt

=== C (recursive) ===
12586269025
0:45.33 sec, 496 Kbytes
=== C (loop) ===
12586269025
0:00.00 sec, 496 Kbytes
=== Go (recursive) ===
12586269025
1:49.14 sec, 1244 Kbytes
=== Go (loop) ===
12586269025
0:00.00 sec, 1244 Kbytes
=== Haskell ===
12586269025
12:38.11 sec, 3604 Kbytes

FYI, with no type signature on the Haskell fib it is probably inferring type Integer which is much slower than Int64.