Fibonacci Sequence

1. Problem Description

Given an integer n, output the nth item of the Fibonacci sequence (starting from 0, where the 0th item is 0 and the 1st item is 1).

2. Approach

• Recursion
  • 
• Memoization to eliminate repeated calculations
• Dynamic programming
  • 

3. Implementation

3.1. Recursion

// Calculate top-down: recursion
// Time complexity: O(2^n)
// Space complexity: recursion stack space
func Fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return Fibonacci(n-1) + Fibonacci(n-2)
}

3.2. Memoization

// To avoid repeated calculations, use a cache
// Time complexity: O(n), with no repeated calculations
// Space complexity: O(n) plus recursion stack space
var cache = make(map[int]int, 0)

func Fibonacci2(n int) int {
	val, ok := cache[n]
	if ok {
		return val
	}

	if n <= 1 {
		return n
	}
	res := Fibonacci2(n-1) + Fibonacci2(n-2)
	cache[n] = res
	return res
}

3.3. Dynamic Programming

// Calculate bottom-up using dynamic programming
// Time complexity: O(n)
// Space complexity: O(1)
func Fibonacci3(n int) int {
	if n <= 1 {
		return n
	}

	a := 0
	b := 1
	res := a + b
	for i := 2; i < n; i++ {
		a = b
		b = res
		res = a + b
	}

	return res
}

4. References

• Fibonacci Sequence - NowCoder
• 509. Fibonacci Number - LeetCode