Recursive Category: Calculations

In the previous section, we discussed the first category of recursive functions—those whose job it is to repeatedly execute a task. For the remainder of this chapter, I’ll elaborate on a second general category: performing a calculation based on a subproblem.

The goal of many functions is to perform a calculation. A function that returns the sum of two numbers, or a function that finds the greatest value within an array, are examples. These functions receive some sort of input and return the result of calculations involving that input.

In Chapter 10, , we found that one area in which recursion shines is where we need to act on a problem that has an arbitrary number of levels of depth. A second area in which recursion shines is where it is able to make a calculation based on a subproblem of the problem at hand.

Before I define what a subproblem is, let’s refer back to the factorial problem of the previous chapter. As you learned, the factorial of 6 is as follows:

6 * 5 * 4 * 3 * 2 * 1

To write a function that calculates the factorial of a number, we could use a classic loop that starts with the 1 and builds up from there. That is, we’d multiply the 2 by the 1, and then multiply 3 by the result, and then 4, and so on until we reach 6.

Such a function may look like this:

However, we could approach the problem differently: we could calculate the factorial based on its subproblem.

A subproblem is a version of the very same problem applied to a smaller input. Let’s apply this to our case.

If you think about it, factorial(6) will be 6 multiplied by whatever the result of factorial(5) is.

Since factorial(6) is:

6 * 5 * 4 * 3 * 2 * 1

and factorial(5) is:

5 * 4 * 3 * 2 * 1

we can conclude that factorial(6) is equivalent to:

6 * factorial(5).

That is, once we have the result of factorial(5), we can simply multiply that result by 6 to get the answer to factorial(6).

Since factorial(5) is the smaller problem that can be used to compute the result for the bigger problem, we call factorial(5) a subproblem of factorial(6).

Here’s the implementation of this from the last chapter:

Again, the key line here is return number * factorial(number - 1), in which we compute the result as number multiplied by our subproblem, which is factorial(number - 1).

Two Approaches to Calculations

We’ve seen that when writing a function that makes a calculation, there are two potential approaches: we can try to build the solution from the “bottom-up,” or we can attack the problem going “top-down” by making the calculation based on the problem’s subproblem. Indeed, computer science literature refers to the terms bottom-up and top-down in regard to recursion strategies.

The truth is that both approaches can be achieved through recursion. We previously saw the bottom-up approach using a classic loop; we can also use recursion to implement the bottom-up strategy.

To do this, we need to use our trick of passing extra parameters, as follows:

In this implementation, we have three parameters. n, as before, is the number whose factorial we’re computing. i is a simple variable that starts at 1 and increments by one in each successive call until it reaches n. Finally, product is the variable in which we store the calculation as we keep multiplying each successive number. We keep passing the product to the successive call so we can keep track of it as we go.

While we can use recursion in this way to achieve the bottom-up approach, it’s not particularly elegant and doesn’t add much value over using a classic loop.

When going bottom-up, we’re employing the same strategy for making the calculation whether we’re using a loop or recursion. The computational approach is the same.

But to go top-down, we need recursion. And because recursion is the only way to achieve a top-down strategy, it’s one of the key factors that makes recursion a powerful tool.