Using Fibonacci to Exemplify Recursion, Big O, and Memoization

Recursion in action! Photo by Ionut Necula on Unsplash

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.