Go script to demonstrate the benefits of cachine when used to recursively compute elements of the Fibonacci sequence.

Home   »   Go script to demonstrate the benefits of cachine when used to recursively compute elements of the Fibonacci sequence.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	rd := bufio.NewScanner(os.Stdin)

	for rd.Scan() {
		n, _ := strconv.ParseUint(rd.Text(), 10, 64)
		fmt.Printf("%5d = %d\n", n, fib(n))
	}
}

var cache = make(map[uint64]uint64)

func fib(n uint64) (v uint64) {
	defer func() {
		cache[n] = v
	}()

	// check if in cache
	for cN, cV := range cache {
		if n == cN {
			return cV
		}
	}

	// if not
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return fib(n - 2) + fib(n - 1)
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *