fibonacci

Documentation

Overview

Package fibonacci allows you to calculate which fibonacci number would be at a given index. Imagine the fibonacci sequence is represented in the form of a slice of ints, similar to the below example.

Fibonacci Sequence
[]int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...}

Index

• func Basic(n int) int
• func BottomUp(n int) int
• func Dynamic() func(n int) int

Examples

• Basic
• BottomUp
• Dynamic

Functions

func Basic

func Basic(n int) int

Basic function is simple implementation, that uses recursion. Runtime complexity O(n^2).

Example

package main

import (
	"fmt"

	"github.com/eng618/go-eng/algo/fibonacci"
)

func main() {
	// Fib example
	fmt.Println(fibonacci.Basic(10))

}

Output:

55

func BottomUp

func BottomUp(n int) int

BottomUp is a bottom up approach to finding the number. Runtime complexity O(n).

Example

package main

import (
	"fmt"

	"github.com/eng618/go-eng/algo/fibonacci"
)

func main() {
	// FibonacciBU example
	fmt.Println(fibonacci.BottomUp(10))

}

Output:

55

func Dynamic

func Dynamic() func(n int) int

Dynamic utilizes memoization and dynamic programming principles, to calculate the fibonacci number for a given index.

Example

package main

import (
	"fmt"

	"github.com/eng618/go-eng/algo/fibonacci"
)

func main() {
	// Fibonacci example
	fibO := fibonacci.Dynamic()
	fmt.Println(fibO(10))

}

Output:

55