30 lines
443 B
Go
30 lines
443 B
Go
package main
|
|
|
|
func Fibonacci(number int) int {
|
|
if number <= 2 {
|
|
return 1
|
|
}
|
|
|
|
return Fibonacci(number-1) + Fibonacci(number-2)
|
|
}
|
|
|
|
func FibonacciWithMemoization(number int) int {
|
|
cache := make([]int, number+1)
|
|
var impl func(number int) int
|
|
impl = func(n int) int {
|
|
if cache[n] != 0 {
|
|
return cache[n]
|
|
}
|
|
|
|
if number <= 2 {
|
|
return 1
|
|
} else {
|
|
cache[n] = impl(n-1) + impl(n-2)
|
|
}
|
|
|
|
return cache[n]
|
|
}
|
|
|
|
return impl(number)
|
|
}
|