entries/vivkpatl/gofib.go


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
41

package main

import (
    "fmt"
)

func main() {
    var n int

    fmt.Printf("Gimme an int: ")

    _, err := fmt.Scanf("%d", &n)
    if err != nil {
        panic(err)
    }

    if n <= 0 {
        panic("n must be greater than 0!") 
    }

    cache := make([]int, n + 1)
    for i := 0; i <= n; i++ {
	cache[i] = -1;
    }

    fmt.Printf("fib(%d) = %d\n", n, fib(n, cache))
}

func fib(n int, cache []int) int {
    if n < 2 {
	return n
    }

    if (cache[n] != -1) {
	return cache[n]
    }

    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)

    return cache[n]
}