From recursion to dynamic programming

This blog is about dynamic programming, and more specifically, the steps required to convert a recursive algorithm into a dynamic programming algorithm. We show how to carry out this type of conversion for the specific example of computing Fibonacci numbers. We also discuss how we can do something similar for other recursive algorithms to which dynamic programming is applicable.

Before we start our discussion on dynamic programming and the steps required to convert a recursive algorithm into a dynamic programming algorithm, let’s recall the elements of a recursive algorithm.

Recursive algorithm#

A recursive algorithm (or a recursive function) is an algorithm that calls itself. In other words, the same definition needs to be applied again, recursively. This is usually referred to as the recursive part.

Because we do not want to continue with this self-reference indefinitely, some stopping conditions need to be defined. These conditions are called base cases.

Fibonacci numbers#

We use a simple example of computing Fibonacci numbers to exemplify the process through which we can convert a recursive algorithm into a dynamic programming algorithm (recursion with memoization).

• Memoization is a technique where we save the result of function calls in an array.

• Fibonacci numbers are a sequence of numbers in which the first two terms are $1$ and $1$. All the subsequent terms in this sequence are the sum of the previous two numbers.

If we represent the $n^{th}$ Fibonacci number by $Fib(n)$, then mathematically we can write the following equation:

The formula given above is the recursive part of the mathematical definition of Fibonacci numbers.

The first two numbers are fixed and are defined to be equal to $1$. They correspond to the base case of the recursive function.

This completes the recursive definition of the Fibonacci numbers. Let’s look at a recursive code snippet that computes the $n^{th}$ Fibonacci number before moving on.

In line 3, we define the function for the recursive function Fib. Line 4 checks for the base cases and returns $1$ for these cases. Line 7 is the recursive part, where the $n^{th}$ Fibonacci number is computed as Fib(n-1) + Fib(n-2). Finally, the $n^{th}$ Fibonacci number is calculated and printed in line 9.

Visualizing Fib(5) through the recursion tree#

The recursive calls can be visualized through the recursion tree. In any recursion tree, every function call is represented by a node. If the function Fib(x) calls the function Fib(y) recursively, then we add an edge from the node corresponding to Fib(x) to the node corresponding to Fib(y).
The argument passed to the recursive function is written inside its corresponding node.

Let’s look at the recursion tree of Fib(5) below:

• The function starts with the function argument $5$ labeled on the root node.

• The two edges of the root node lead to the nodes labeled with the arguments $4$ and $3$.

• In this recursion tree, we can see that there are two nodes with an argument of $3$. They correspond to the recursive call of Fib(3). This means that Fib(3) is computed twice.

• For a larger starting value, there will be more function calls with the same argument that will be computed multiple times.

• Also, the function Fib(3) will be computed even more times. This is because the recursion tree doesn’t keep track of the number of times the recursive calls with various arguments are computed, or whether a function call with a particular argument has already been computed or not—therefore the need to recompute the function with the same arguments several times.

Because we are needlessly recomputing some values multiple times, the algorithm will take more steps to complete its calculations, making it slow and inefficient. The obvious way to solve this issue of recomputation is to keep track of all the possible inputs to the recursive algorithm, and whether the result of the function calls with these arguments have been calculated or not. If they have been calculated, then their values should be saved.

Now, with this additional information, we don’t need to call the recursive algorithm blindly. All we need to do is to check whether a particular value has already been calculated or not. We can easily perform this check with the help of an array of boolean variables—one index for every argument to the function calls. For example, if we want to check whether the fifth Fibonacci number has been calculated or not, we’ll look at the fifth index of this boolean array. A true value at the fifth index will indicate that this value has already been calculated, and a false value will indicate otherwise.

Let’s list these changes down before we convert this strategy into code.

• If the value is already calculated, then return the value.

• If the value is not calculated, then do the following:

  • Calculate the value recursively.

  • Save the value.

  • Update the information that this value has been saved.

  • Return the value.

Additionally, we need to initialize these arrays with zeros.

We need the following three things in order to implement the above-mentioned strategy:

• We need a boolean array to save the information of whether a particular value is already computed or not. Let’s use 1 to represent the already computed value, and 0 otherwise. For the function with parameter $x$, this information will be saved at the index $x$.

• We need an array to save the value for each variable. The result of the function call with a parameter $x$ will be saved in the array at index $x$.

• We need a helper function (helper_function) that actually implements the strategy.

Over here, helper_function is a function that makes the necessary checks and returns the calculated values. Using this function will give us two advantages.

• For any recursive algorithm, its logic is kept separate and the logic of memoization is handled separately in helper_function.

• In order to implement this scheme, we just need to replace the recursive calls with helper_function with the same parameters.

Let’s look at how memoization works with the help of an example.

Suppose we want to calculate Fib(5).

We’ll create a boolean array is_calculated of size $5$ as follows:

We’ll also create an integer array—value—of size 5, as shown below. We only need to initialize it with the known values of the base cases.

Let’s define helper_function as described above.

In line 1, def helper_function(n): defines the helper function.

In line 2, if (is_calculated[n]==1) checks whether the function with parameter n (here, it is the $n^{th}$ Fibonacci number) is already calculated or not. If it is calculated, then the correct value, value[n], in line 3 is returned. Otherwise, in line 5, Fib(n) calculates the correct value and value[n] = Fib(n) saves it at its correct location. In line 7, is_calculated[n] = 1 updates the information that the $n^{th}$ value is now available. In line 8, return value[n] returns the $n^{th}$ value.

Now, let’s update the recursive algorithm of Fibonacci.

Let’s look at the complete code, with both the functions Fib and helper_function.

In line 1, the value of n is selected. Lines 3–8 are used for initializing the array. Here, we should note that we are initializing three values in lines 3–4 for the base cases, whereas the original function contains only two base cases. Because we store the first Fibonacci number at index $1$, we initialize the $0^{th}$ cell of both arrays with None. This value is never used.

The helper_function is defined in lines 10–17, and Fib is defined in lines 20–24. Finally, in line 26, Fib(n) calculates the $n^{th}$ Fibonacci number, and the result is printed.

In general, to memoize any other recursive function, say xyz, all recursive calls to xyz should be replaced by helper_function. Of course, if the function xyz contains a higher number of parameters, then helper_function will have the same parameters and the arrays is_calculated and value will have the same dimensions as the number of these parameters.

Recursion tree for the dynamic programming algorithm#

It will be interesting to have a look at the recursion tree with the dynamic programming approach. It is shown below:

Note that there are two nodes with the same number $3$. The one on the left, with the blue color, represents the function call Fib(3), which is called first. After its value is calculated and saved, we do not have to recalculate the value of the third Fibonacci number. This is why, when the function Fib(3)—represented by the node with the value $3$ in orange—is called again, it does not make recursive calls. Instead, it just returns the already saved value. Just to make the two function calls different, we have assigned them different colors.

For a large input value, the number of nodes and the number of recursive calls in both trees will be substantially different. Try drawing the recursion tree for both cases with $n = 8$.

Concluding remarks#

Converting a recursive algorithm into a dynamic programming algorithm (recursion with memoization) is a simple and straightforward process with a defined number of steps.

You can replace the value of n in the recursive code, as well as the dynamic programming code, to a large number—let’s say $100$—and compare the time it takes to compute the answer. This is just how fast dynamic programming algorithms are!

For more details regarding algorithms and dynamic programming, take a look at the following courses: