Recursion
Learning Objectives
At the end of this sub-unit, students should
- know how to reformulate problems recursively.
- know how to solve problems using recursion.
Self-Similar Subproblems
When we are thinking about a problem \(P\) in terms of subproblems \(P'\), we may realized that the subproblems \(P'\) is exactly the same problem \(P\) but with simpler inputs. The definition of simpler are typically based on common-sense but it should still be relevant to the problem. But the main thing is that since \(P'\) is the same as \(P\) but simpler, we say that \(P\) and \(P'\) are self-similar.
If we ever encounter the problem \(P\) that can be solved by first solving a simpler self-similar subproblem \(P'\), we have a nice way of formulating the solution. First, we say that the problem \(P\) can be solved by a function \(F(x)\). Since we have a simpler self-similar subproblem, it means we have a simpler input \(x'\) that we can actually solve with \(F(x')\). In other words, we can represent \(F\) as something like the following.
So \(F(x)\) is calling itself but with simpler input \(F(x')\). We say that such function \(F\) is a recursive function. If \(F(x)\) can be solved by first solving \(F(x')\), then it is logical that if we let \(y = x'\), then we have \(F(y)\). But \(F(y)\) has the same form as \(F(x)\) so by substitution, we expect that we can solve \(F(y)\) by first solving \(F(y')\). Substituting \(y = x'\) back but in the opposite direction, we get the following sequence.
Consider the sequence of function call to solve \(F(x)\). Since the above sequence can be repeated pretty much indefinitely, we have the following infinite call tree.
Unfortunately, following this idea, it means that we will never get an answer at all. This is because \(F\) keeps on calling itself.
So consider what happened at the problem itself. The problem \(P\) becomes the simpler \(P'\) and \(P'\) becomes the simpler \(P''\). At some point, we hopefully reach the case where the problem is so simple, the solution is trivial. Since the solution is trivial, we should not invoke \(F\) anymore. This will stop the chain and kickstart the return value processing. It does not matter for us how long this chain is, as long as we eventually reach this trivial solution, we will eventually get a return value.
So to recap, we want that for some value \(y\), we have \(F(y) = z\) without even calling \(F\) anymore. We can then write the original formulation as follows.
We can rewrite the chain horizontally too.
Terminologies
Given the formulation of \(F(x)\) above --reproduced below-- we can name some of the elements used.
| Terminology | Element | Description |
|---|---|---|
| Base Case | \(x = y\) | The condition to finish the chain |
| Base Value | \(z\) | The trivial solution |
| Recursive Case | \(x \neq y\) | The condition to continue simplifying the problem |
| Recursion | \(\cdots F(x')\) | We need \(x'\) to be simpler than \(x\) |
| Deferred Operation | \(F(x') \cdots\) | The operation to be performed after recursion (i.e., the \(\cdots\) after \(F(x')\)) |
Factorial
So to solve problem using recursion, we need to be able to rephrase the problem in terms of a simpler problem. If the problem is an arithmetic problem, we can manipulate the formula algebraically to represent the smaller problem in terms of simpler version of itself. The typical problem to introduce students to recursion is the factorial problem. We reproduce the formula below.
Consider the boxed part of the formula for factorial as shown below. Can we represent this boxed expression as factorial?
So we have satisfied the first requirement of solving factorial (i.e., \(F(n)\)) with a simpler factorial (i.e., \(F(n-1)\)). But we have not satisfied the second requirement to actually find the trivial solution. Looking at the formula on its own, we can obviously see that \(1!\) is trivial as it is simply \(1\). Of course we can also say that \(2!\) is trivial because it is simply \(2\). In fact, once we have the computation done once, we can also say that \(10! = 3628800\) is also trivial.
On the other hand, we can say that \(1!\) is more trivial than \(2!\) because by continuing the computation, we will eventually arrive at \(1!\) simply because \(2! = 2 \times 1!\). Often, the question will also specify what is trivial. By definition, \(0! = 1\). So this is more trivial than \(1!\) because we can represent this as \(1! = 1 \times 0!\). We will stick with this definition and represent \(n!\) as follows.
We use boxing, but we can also name \(\boxed{n!}\) as \(F(n)\). We then rewrite this again as follows.
Hopefully the translation to code is quite straightforward.
Recursive Factorial
Simpler ≠ Smaller
It should be noted that simpler is not necessarily smaller. It is often smaller, but consider the following algebraic manipulation of the factorial problem.
- \({\displaystyle n! = n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1}\)
- \({\displaystyle n! = \frac{(n + 1) \times n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1}{(n + 1)}}\)
- \({\displaystyle n! = \frac{\boxed{(n + 1) \times n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1}}{(n + 1)}}\)
- \({\displaystyle n! = \frac{\boxed{(n + 1)!}}{(n + 1)}}\)
In this case, notice how to solve \(n!\) we need to solve \((n + 1)!\). If we really want to solve it this way, then we need to find the largest value of \(n\) that we can solve. Say we want to use \(10! = 3628800\), then we write the recursive formula as follows.
The code is shown below. In the case of factorial, this is a bad practice because the value of \(n\) that we can compute is restricted to \(0 < n \leq 10\). For other cases, it might be the way to solve it.
Bad Practice Factorial
In short, simpler means easier to solve. This depends on the problem. We aim to have the simplest_ case as the base case so that we do not have to write all the base cases. Take the example of factorial again, if we feel the first 5 numbers are simple enough, our code is no longer as short as before.
Factorial with Too Many Base Cases
Digit Operation
So the idea of solving problems with recursion is to find a recursive formula. Once we have the recursive formula, the solution can be quite obvious. To get the recursive formula, we will need to do exploration. Unfortunately, there may not be a general programming pattern that can capture all potential recursion. In the case of counting digit, we have done some exploration and we may rephrase the problem into the following recursive formulation.
The code is then shown below.
Recursive Counting Digit
Another similar problem is the sum of digit, which we can also reformulate recursively as follows.
The code is then shown below.
Recursive Counting Digit
Connecting-the-Dots
In many cases, we can use connecting-the-dots to find recursive formula. The idea is simply to come up with the connecting formula. Consider the matchstick problem from before.
We came up with the following table on our working.
| n | matchsticks(n) | (n-1) ans + last row | last row |
|---|---|---|---|
| 1 | 3 | 0 + 3 = 3 | 3 |
| 2 | 9 | 3 + 6 = 9 | 6 |
| 3 | 18 | 9 + 9 = 18 | 9 |
| 4 | 30 | 18 + 12 = 30 | 12 |
| 5 | |||
| \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) |
| n | ? | \(p + 3n\) | \(3n\) |
The connecting formula is \(p + 3n\).
But remember, \(p\) is the answer from the previous row.
However, if we stop at the previous row, it means we are actually solving for n - 1.
This is exactly matchsticks(n - 1).
So now, we have formulated the recursive formula by replacing \(p\) with matchsticks(n - 1).
Recursive Matchsticks
Evaluation
Let us take a step back from problem solving and try to understand the solution a little bit more.
We have quite a number of recursive functions.
In factorial(n), we have a deferred operation n * written before the recursion factrorial(n - 1).
On the other hand, for digit_sum(n), the deferred operation + (n % 10) is done after the recursion digit_sum(n // 10).
During the recursion, we use the same parameter n.
How can this variable n has different values?
In our previous explanation, we mentioned that different function have their own scope.
But now we have the same function, albeit being called multiple times with different argument.
Luckily for us, the evaluation is still the same.
We can extend the scope into a single invocation of a function.
So if a function is invoked multiple times --even in a recursion-- the scope will still be different each time.
So each function call will have their own version of n.