fibonacci.go

// Recursion
func fibonacci(n int) int {
	if n <= 2 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

// Slice Append - Dynamic
func fibDynamic(n int) int {
    a := []int{1}
    if n == 1 {
        return 1
    }
    a = append(a, 1)
    if n == 2 {
        return 2
    }
    for i := 2; i < n; i++ {
        a = append(a, a[i-2]+a[i-1])
    }
    return a[len(a)-1]
}

// Memoization
func memoization(n int)int{
	_, ok := memo[n]
	
	if ok {

        return memo[n]

    }
	if n <= 2 {
		return 1
	}
	memo[n]= memoization(n-1) + memoization(n-2)
	return memo[n]
}

// Tabulation
func tabulation(n int)int{
	var result []int = make([]int, n+2)

	result[0] = 0
    	result[1] = 1


    for i := 0; i <= n-1; i++ {

        result[i+1] += result[i]

        result[i+2] += result[i]

    }


    return result[n]
}