In the last section, we looked at the function \(f(n) = \sum_^n i\) , and proved using induction that \(f(n) = \frac
We can represent this idea more precisely as the following algebraic statement: for all \(k \in \N\) , \(f(k + 1) = f(k) + (k + 1)\) . This relationship gives us a different way of defining \(f\) , without using either a summation or the formula \(\frac
We say that this is a recursive definition, meaning that \(f\) is defined in terms of itself. Another name for this is a self-referential definition. It is this recursive definition that formed the basis of our induction proof in the previous section: we were able to manipulate the equation \(f(k + 1) = f(k) + (k + 1)\) to prove the inductive step.
Much earlier in these notes, we discussed how we can turn mathematical expressions involving summations into Python expressions using the built-in sum function. It turns out that we can do the same with recursively-defined functions, and that this translation is a very natural one. Here is how we could represent our above function \(f\) in Python:
def f(n: int) -> int: """Return the sum of the numbers between 0 and n, inclusive. Preconditions: - n >= 0 >>> f(4) 10 """ if n == 0: return 0 else: return f(n - 1) + nNow, this implementation certainly isn’t the most efficient way of representing this function, e.g., return n * (n + 1) // 2 but it does illustrate that Python functions can be also defined recursively.
More formally, let f be a Python function. We say that f is a recursively-defined function (or recursive function for short) when it contains a call to itself in its body. We use the term recursive call to describe this inner f(n - 1) call. And finally, we use the term recursion to describe the programming technique of defining recursive functions to perform computations and solve problems.
We use labels for the different parts of this if statement, as the structure is common for most recursive functions:
These labels are deliberately parallel to the ones we used for a proof by induction in the previous section. In both an induction proof and recursive function, the base case is the component that does not require any additional “breaking down” of the problem. Similarly, both the induction step of a proof and the recursive case of a function require the problem to be broken down into an instance of a smaller size, either by using the induction hypothesis or by making a recursive call.
Just like induction, recursion can feel a bit like magic when we first see it. We tend to reason about our code step by step, line by line. In the case of a recursive call— f(n - 1) in the above example—you might wonder, how can we call a function when we haven’t finished defining it yet?
There are two ways of reasoning about recursive functions. We’ll start with the one that follows what the Python interpreter does, which is analogous to the “domino-style chain of reasoning” for induction:
In a proof by induction, we found that the induction step meant that \(P(0)\) implied \(P(1)\) , which implied \(P(2)\) , which implied \(P(3)\) , etc. In the same way for our recursive function, f(2) calls f(1) , which calls f(0) , etc.
However, this “chain of reasoning” is a very long-winded way of tracing the execution of a recursive function call! Suppose we want to reason about the call f(100) : we’d be sitting here long time writing statements of the form “When we call f(_) , the recursive call f(_) …” as above. This type of literal tracing is what the Python interpreter does, but it’s also extremely time-consuming and error-prone for humans to do.
The second (and better) way for humans to reason about recursive functions is the inductive approach: we assume that the recursive call f(n - 1) returns the correct result, based on the function’s specification, and without relying on having explicitly traced that call. This is the exact analog of the induction hypothesis in a proof by induction!
For example, here’s how we we would reason inductively about the call f(100) :
If you’re feeling a bit uncomfortable with making the assumption that f(99) returns 4950 , think back to our proof by induction. We assumed \(P(k)\) and used that to prove \(P(k + 1)\) , knowing that as long as \(k\) was arbitrary we would be able to fall back on our “chain of reasoning” to get to the base case. In the same way here, we can assume f(99) is correct to justify the correctness of f(100) , knowing that if we wanted to we could trace all the different calls f(99) , f(98) , …, f(1) , f(0) , but would end up with the same result.
Recall that all the way back in Section 7.3, we studied the Euclidean algorithm for calculating the greatest common divisor of two numbers. This relied on the mathematical fact that for all \(a, b \in \Z\) with \(b \neq 0\) , \(\gcd(a, b) = \gcd(b, a ~\%~ b)\) . Here is our implementation of the Euclidean algorithm, using a while loop:
def euclidean_gcd(a: int, b: int) -> int: """Return the gcd of a and b. Preconditions: - a >= 0 and b >= 0 """ x = a y = b while y != 0: r = x % y x = y y = r return xThere is another way of implementing the Euclidean algorithm in Python that uses recursion. Take another look at the key mathematical equation that makes the Euclidean algorithm work: \(\gcd(a, b) = \gcd(b, a ~\%~ b)\) . This equation, and the fact that \(\gcd(a, 0) = a\) for all \(a \in \N\) , is actually all we need to write an alternate, recursive definition of the \(\gcd\) function over the natural numbers:
Compare this definition to the one we wrote at the start of this section. This is also a recursive definition, but now the recursive part doesn’t just decrease a number by 1. Instead, the second argument decreases from \(b\) to \(a ~\%~ b\) —and the value of the latter could be anything between \(0\) and \(b - 1.\) This example shows the flexibility of recursive definitions: we aren’t just limited to going “from \(n\) to \(n - 1\) ”, or even unary functions. A recursive definition is valid as long as it always uses “smaller” argument values to the function in the recursive call. We’ll define what we mean by “smaller” more precisely in a future section.
With this in mind, we’ll complete our example by translating this \(\gcd\) definition directly into Python code. Notice once again how naturally the above definition translates into Python:
def euclidean_gcd_rec(a: int, b: int) -> int: """Return the gcd of a and b (using recursion!). Preconditions: - a >= 0 and b >= 0 """ if b == 0: return a else: return euclidean_gcd_rec(b, a % b)