Dynamic Programming in Golang
Recursion

One approach that’s likely to come to mind when faced with the Fibonacci sequence problem is to use recursion. Let’s take a look at the implementation of this approach and how efficient it is:

// the recursive function approach definition

func expensiveFib(n int) int {

if n < 2 {

return n

}



result := expensiveFib(n-1) + expensiveFib(n-2)



return result

}

Running the recursion solution with an input of 50 will result in 12586269025 with an execution time of roughly 1m and 6.413943065s . Why does it take so long? Simply put, it’s due to the recursive call of the function. We’re checking whether the input is less than 2. If so, we return the input and move to the next stack of the function calls. In this case, the returned input would be either 1 or 0. On the other hand, if 2 is not greater than the input, we call the function twice — once with the input 1 and the second time with the input 2, and sum the result of both calls. The image below depicts the process (using an input of 5):

Loop

Another approach is to use a loop. Let’s take a look at the implementation of this approach and how efficient it is:

// the loop approach definition

func fibByLoop(n int) int {

fibBox := []int{0, 1} for i := 0; i < n; i++ {

v := fibBox[i] + fibBox[i+1]

fibBox = append(fibBox, v)

} result := int(fibBox[n])

defer trackTime(time.Now(), result, "Loop")



return result

}

Running the Loop solution with an input of 50 will result in 12586269025 with an execution time of roughly 2.356µs . That seems much faster than the recursive approach — from 1m and 6.413943065s down to 1.428µs , impressive!

So, what’s the algorithm behind this solution? The answer is, we used an iterative approach. Let’s review the steps:
['Adeshina H. Hassan']
['Go', 'Programming', 'Software Development', 'Golang', 'Algorithms']