Capstone Week 2: Recursion and Dynamic Programming

This past week was almost exclusively about top-down recursion with dynamic programming (i.e., with memoization). It was filled with struggle, both in terms of personal morale and in terms of pure intellectual fatigue.

That being said, the experience was, and continues to be, incredibly rewarding. No matter how difficult the problem, we are armed with the necessary techniques, resources, and expert instruction to solve it. I can explicitly see the differences in my mental models at the end of each day as a result of the exercises the instructor puts us through combined with the clarity of his lectures. We are constantly following a pattern of learn;practice;repeat… This was especially useful with the advanced topics we covered this week.

Recursion vs Iteration

I am used to solving problems iteratively. Given an input and an expected output, I construct a procedure to produce the output from any set of allowed input. First, a high level description of the solution and then a lower level implementation. Sometimes the solution involves declarative calls to packaged behaviors, making it easier to think about the problem as a whole. However, the solution is always bottom-up, step-by-step at its core.

That all changed this week.

From the morning of day one, we were instructed to solve all problems recursively. When the instructor said “We are going to be 100% recursive this week” I suspected slight hyperbole… I should have known better.

Bottom-Up V.S. Top-Down

Recursion itself is not necessarily difficult. Simple problems that call for a basic loop can be solved just as easily with recursion. Whenever you have an iteration-based traversal of a data set, you can replace it with a recursive traversal of that data set (though that isn’t necessarily a good idea if you care about performance…).

For example, summing up all elements in an array of numbers is simply a matter of keeping track of an accumulated sum as a loop iterates through each element of the array, updating the sum at every step. Implementing this behavior via recursion is very different than the style of recursive problem solving that we focused on this week. This is because the behavior just described is inherently bottom-up: the solution is built from simple to the complex. This is very different than a top-down approach. With the above approach, the recursive call serves the same function as a loop:

Recursive (bottom-up):

def sum_nums_recursive(arr, current_idx = 0, sum = 0)
  return sum if current_idx == arr.length
  sum += arr[current_idx]
  sum_nums_recursive(arr, current_idx + 1, sum)
end

Iterative:

def sum_nums(array)
  sum = 0
  array.each do |el|
    sum += el
  end
  sum
end

This type of recursive solution, called recursive traversal, is a bottom-up or iteration-flavored recursion.

A top-down approach takes a problem description and rephrases it as a general problem. It then constructs a solution by assuming the general problem is already solved and then redefining the solution in terms of solutions to smaller sub-problems.

This will make a lot more sense with an example. So, here is the top-down recursive approach to the summing problem above:

The specific problem: “Given an array of numbers, return the sum of the numbers in the array.”

The general problem: “Given an array of numbers, return the sum from 0 to some index n.”

Now, let’s assume we have been given an array and that we have already solved the general problem: we magically have the sum already. The question is: how can we define this sum — the solution to this problem — in terms of smaller solutions to the same problem/ in terms of multiple sub-problems (i.e., multiple subsets of sums)?

Defining the solution: “ The sum of numbers from index 0 to n is equivalent to the sum of numbers from index 0 to n-1 + n.”

In other words: sum(0..n) == sum(0..n-1) + n

That rule is called the “reduction” and it is a key part of recursive solutions. The reduction is what simplifies the input a little bit more during each recursive call until the input is so trivial that the solution can be returned immediately without further recursive calls.

To ensure that the solution is immediately returned when the input is trivial enough to not require further recursive calls, we need a “base case,” which is another key part of recursive solutions. The base case ensures that we do not infinitely recurse: it provides a terminating condition for the recursive calls.

The base case is supposed to be so simple that it is obvious what to return. In our problem, the base case is if the input array has 1 element in it, because we know for a fact that the sum of all numbers in an array which has one element is simply the value of the first element. Further, if an array has zero elements in it, then obviously the sum of the elements in the array also equals zero.

So, we now have a reduction and a base case for our top-down solution. Let’s code it up:

Recursive(top-down)

def sum_nums(array)
  if array.length == 1
    return array[0]
  end
  if array.length < 1
    return 0
  end
  
  return array[array.length - 1] + sum_nums(array[0..array.length - 2])
end

Notice that this solution does not keep track of state with a sum variable because it doesn’t need to: we started with the assumption that the problem is already solved and then redefined the solution in terms of solutions to slightly smaller sub-problems. We began from the solution rather than the problem.

It may appear that top-down recursion over-complicated the problem. Top-down recursion is useful for problems that are a lot more complex than the example above and can simplify the mental model when iteration/bottom-up problem solving just becomes too convoluted.

The above solution didn’t use dynamic programming, which involves identifying overlapping sub-problems and caching their solutions so that we don’t need to recompute the solutions every time we encounter them. It was trivial enough so as to not warrant memoization. However, you can view more coded examples of top-down recursion and dynamic programming here: https://github.com/WilfredTA/practice_problems_algorithms

I knew nothing of top-down recursion before this week. In fact, even a simple bottom-up recursive traversal would have made me uncomfortable. Yet, our cohort is spending the evening solving non-trivial problems with top-down dynamic programming (interspersed between readings on systems design). It is (pleasantly) surprising how much one can grow in an environment that demands 100% effort every single day.