How dynamic programming rescues crashing recursive algorithms

Key takeaways:

• Recursive algorithms can lead to stack overflow or excessive recomputation, especially when solving problems like the Fibonacci sequence without optimization.

• Dynamic programming (DP) optimizes recursive algorithms by storing intermediate results, avoiding redundant calculations, and reducing time complexity.

• Memoization improves recursive algorithms by caching previously computed results, preventing redundant function calls and reducing time complexity.

• Unlike memoization, tabulation builds the solution iteratively from the bottom up, ensuring that all subproblems are solved once and in the right order.

In software development, recursive algorithms are fundamental due to their straightforward and elegant design, which simplifies complex problem-solving. Yet, this simplicity can lead to significant drawbacks, such as performance bottlenecks and program crashes from stack overflow errors. Dynamic programming (DP) offers a valuable solution to these challenges, enhancing the performance of recursive algorithms and preventing common issues like crashes.

What is the difference between dynamic programming and recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. It typically solves problems by breaking them down into subproblems, solving them, and combining the results. However, recursion can be inefficient due to repeated calculations for the same subproblems.

Dynamic programming (DP), on the other hand, optimizes recursion by storing the results of previously solved subproblems, preventing redundant calculations. It involves solving subproblems in a bottom-up or top-down manner, ensuring each subproblem is solved once and reused when needed.

Why do recursive algorithms crash?

Recursive algorithms break down a problem into smaller, manageable subproblems, solving each recursively until a base case is reached. This technique uses the stack, where each recursive call adds a new block to the stack with its execution context. However, recursive algorithms can crash, primarily due to stack overflow. This occurs when the recursion depth exceeds the stack’s capacity, as each recursive call consumes a portion of the stack’s limited space. Particularly in cases where the algorithm handles large inputs or lacks efficient base cases, the stack fills up rapidly, leading to crashes.

Let’s look into a problem to understand how a recursive algorithm crashes.

Example: Fibonacci number

Fibonacci numbers are a sequence of numbers where each is the sum of the two preceding numbers. The Fibonacci sequence is defined as follows:

A few starting terms of this sequence are as follows:

Our task is to find the$n^{th}$Fibonacci number.

Naive recursive approach

A naive approach to finding the $n^{th}$ Fibonacci number is by implementing the recurrence relation. At each iteration, the number will be $0$ for the zeroth term, $1$ for the first term, and the sum of the two preceding values for all the other terms in the sequence.

The visualization below shows a dry run of this algorithm.

It’s evident from the visualization above that the algorithm makes redundant recursive calls to compute the same results. For example, it calls fib(0) two times, fib(1) three times, and fib(2) two times. This inefficient way of making redundant recursive calls to compute the same values causes stack overflow, resulting in the naive recursive algorithm to crash.

The implementation of this recursive algorithm is given below:

The algorithm above is tested on five test cases: $0$, $5$, $7$, $10$, and $14$. The solution runs fine on these test cases. Let’s test it on a larger value e.g., $60$, by uncommenting that test case in the code. We observe that the algorithm keeps on running and finally times out, indicating that the recursive algorithm crashed due to stack overflow caused by too many recursive calls.

Time complexity

This algorithm has exponential time complexity, specifically $O(2^n)$. This is because we take the sum of the two preceding values every time.

Space complexity

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Dynamic programming to the rescue

Dynamic programming rescues crashing recursive algorithms by optimizing their performance and managing memory use. It achieves this through the following techniques:

1. Top-down technique such as memoization

2. Bottom-up technique such as tabulation

DP stores the results of subproblems, thus avoiding the repetitive computation that exacerbates stack overflow in pure recursion. By ensuring that each subproblem is solved only once and reusing these precomputed answers, DP reduces the number of recursive calls and the depth of the call stack. This approach not only prevents crashes but also significantly speeds up the execution by transforming exponential time complexity into a more manageable polynomial complexity. For a deeper understanding of dynamic programming, check out this blog.

The applicability of dynamic programming depends upon the following two properties:

1. Optimal substructure: This property means that an optimal solution to a problem can be effectively constructed from optimal solutions of its subproblems. In dynamic programming, this property is crucial because it ensures that the problem can be broken down into smaller, manageable parts, and by solving each part optimally, the solution to the overall problem can be derived.

2. Overlapping subproblems: This property is present when the recursive algorithms revisit the same problems repeatedly. Dynamic programming uses this property by storing the results of these subproblems in a table. Once a subproblem has been solved, its result is stored and reused (thus avoiding the work of re-solving it), which drastically reduces the computational cost and prevents redundant calculations that could lead to a stack overflow in naive recursion.

Let’s see how DP rescues the crashing recursive algorithms using memoization and tabulation.

Top-down technique: Memoization

The top-down solution, commonly known as the memoization technique, enhances the recursive solution. It overcomes the problem of calculating redundant solutions repeatedly by storing them in an array.

The basic idea is to check if the array already contains the result of the Fibonacci number we are trying to find before calculating it. This way, we will reduce the number of recursive calls by using the already-stored result in the array.

The solution of the Fibonacci number problem using memoization is given below:

We’ve already uncommented the large test case ($60$), and the code runs fine, indicating the efficacy of dynamic programming. A worth-mentioning point here is that although memoization is also a recursive technique, it doesn’t crash because it stores and reuses the results.

Time complexity

The new recursion tree approximately grows to a depth of$n$, and each node has two children. This means that there are a total of $2n$ nodes, so the time complexity is $O(n)$.

Space complexity

The space required in memory will remain $O(n)$.

Bottom-up technique: Tabulation

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic problems. The tabulation approach is like filling up a table from the start. Let’s now find the$n^{th}$ Fibonacci number using the bottom-up method.

First, we will initialize a lookup table and set the first two values, followed by setting the values of the rest of the Fibonacci numbers by summing up the previous two values.

Have a look at the visualization below for a clearer picture of what is going on for finding the$5^{th}$ Fibonacci number:

The solution of the Fibonacci number problem using tabulation is given below:

Again, we’ve already uncommented the large test case ($60$), and the code gives the desired output.

Time complexity

The time complexity of this code is $O(n)$, since that is the equivalent of the number of iterations of the for loop.

Space complexity

The above solution occupies $O(n)$ space in the memory.

A quick comparison

The table below provides a quick comparison of the three approaches—naive, memoization, and tabulation—highlighting their time and space complexities.

Conclusion

Dynamic programming offers a powerful solution to the common pitfalls of recursive algorithms, such as excessive recomputation and inefficient memory use. By storing intermediate results, techniques like memoization and tabulation can transform a slow, crash-prone recursive approach into an efficient solution.