Fibonacci numbers are present in nature, and nowadays they’re often used in schools and interviews to test recursion. They can, however, provide us a greater insight into core computer science topics. I’m most fascinated by how they offer an important example of a powerful principle: We can make recursive functions run at almost the same time as their iterative counterparts.
Don’t believe me? Let’s attempt to solve the following problem:
A Fibonacci number is the sum of its previous two neighbors, starting at 0
0 1 1 2 3 5 8 13 21 34 .. i[n-2] + i[n-1] = i[n]
Given an integer n, write a function to compute the nth Fibonacci number. Determine the Big O time complexity of your solutionExpected Output:
fibonacci(1) //=> 1
fibonacci(4) //=> 3
fibonacci(12) //=> 144
fibonacci(40) //=> 102334155
And here is the naive solution:
To find the 4th Fibonacci number (input of 4), we get multiple returned recursive results when we run the function.
