find the nth fibonacci number in go

To find the nth Fibonacci number in Go, we can use either recursion or dynamic programming approach.

1. Recursion

Recursion is a simple approach to find the nth Fibonacci number. We can write a function that calls itself repeatedly until it reaches the base case. The base case is when n is either 0 or 1, then we return n. Otherwise, we recursively call the function for n-1 and n-2, and return their sum.

main.go
func fibonacciRecursive(n int) int {
    if n == 0 || n == 1 {
        return n
    }
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
}
149 chars
7 lines

2. Dynamic Programming

Dynamic Programming is an efficient approach to find the nth Fibonacci number. We can store the previously calculated Fibonacci numbers in an array and use them to calculate the new number. We can initialize the first two Fibonacci numbers as 0 and 1, respectively, and then iterate from 2 to n, calculating the new Fibonacci number by adding the previous two.

main.go
func fibonacciDynamic(n int) int {
    if n == 0 || n == 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
228 chars
13 lines

Both approaches have a time complexity of O(n) and a space complexity of O(n) because we need to store the previously calculated Fibonacci numbers.