Is Plain Recursion Good Enough?

This lesson will argue for using dynamic programming instead of recursion to solve complex problems.

Recursion = brute force

We saw some examples of recursion earlier in this chapter. One recurring theme (pun intended) in all those problems was high time complexity. Why was that the case? Because all those problems required a brute force search. We had to search in the whole solution space to look for an answer. For example, in the permutation challenge, we had to find all the possible combinations of characters. In the N queens problem, we had to look at all possible placements of queens until we found an optimal one. So, recursion in most cases is an excellent brute force technique. But as the name also suggests, it is not a very elegant one; thus, we will be learning about techniques that make recursion more efficient.

Recursion’s inefficiency visualized

Let’s rerun this Fibonacci numbers algorithm given in the start of this chapter. This time, we have plotted the time taken by each Fibonacci number to compute. Try different values by updating the value of variable numbers:

Get hands-on with 1200+ tech skills courses.