Memoizing Fibonacci Numbers
Explore memoization techniques for Fibonacci numbers to optimize recursive code in C#. Understand how using lookup tables reduces redundant calculations and improves time complexity from exponential to linear.
We'll cover the following...
We'll cover the following...
Let’s memoize the code now and see where that leads us. The basic idea is to check if a list already contains the result of the Fibonacci number that we are trying to find before calculating it.
Memoized code
Have a look at the complete code in C#:
The method is very simple. It takes as input the following:
- The number
nthat represents the Fibonacci number that we want to find, which is6in our case. - A lookup table called
lookupTableof size