Inefficient Recursion: Fibonacci Numbers
Explore how naive recursion calculates Fibonacci numbers inefficiently due to repeated function calls. Learn to recognize the exponential growth of redundant calculations and its impact on performance when applying recursion to this classic series.
We'll cover the following...
We'll cover the following...
Inefficient recursion
Here is another classic example of recursion – calculating the Fibonacci number. It turns out that this is hopelessly inefficient using pure recursion, but we will also look at a useful technique to alleviate the problem.
If you are not familiar with the Fibonacci series, it is an infinite series of numbers defined as follows:
= 0
= 1
= + ...