A rather interesting topic in math (what a general way to start a post) is the matter of recursive functions. These are functions that are expressed in terms of themselves. A fairly traditional example would be factorial. n! is defined to be
Now, a nicely concise way to write this, not to mention computationally convenient, is to define the following
So, the operation is defined, effectively, with respect to itself.
There are a couple of points of interest when it comes to recursive functions. One is expressing common operations and calculations in terms of recursion – it’s often more elegant and much more natural, like the above definition of recursion. Then, there are some functions that can -only- be expressed in terms of recursion. Which is of special interest, since one of the nice things to do with recursively defined functions is to determine a formula for what that function is – and quite often, you just can’t.
It’s all very interesting.
There are a lot of operations that can be defined very nicely in this way. Consider the following, for example.
Calling f(2, 3) then, it unwraps to give
In general, it’s clear that f(x, n) returns n*x. In effect, this is a recursive definition of multiplication. So, many nice things can be expressed very nicely using recursion.
But, many interesting things can be expressed with recursion that can’t be expressed nicely otherwise. Consider, for example, the Ackermann Function, A(m, n) defined as
If m = 0:
If m > 0 and n = 0:
If m > 0 and n > 0:
A(m, n) has no non-recursive definition, no closed-form expression, or anything near as nice as the two recursive examples I already showed you have. The above is the best you’re going to get. Interestingly, it is the simplest function for which that is the case. The other point of interest about the Ackermann Function is how incredibly fast it grows, even for small m and n. In fact, A(4,2) has 19729 digits, which is far more than I am comfortable writing out here. The full number can be found here, if you’re interested. A very, very large number. In fact, at that magnitude, I’d argue that the full text of the number is next to meaningless, when compared with the much more concise description of the same number as merely A(4,2).
Alternately, there are things that are expressed very nicely with recursion, that become much less nice when unraveled. Take, for example, the Fibonacci Sequence. Starting with a 1 and a 1, the sequence is formed by taking the sum of the two previous terms. This produces 1, 1, 2, 3, 5, 8, … and so on. More concisely, it can be written as
A very clean and elegant description of the sequence. Unraveling the recursion, with all due care, it can be shown that the following definition is equivalent.
Hardly the most elegant of formulae. Somehow, the recursive definition captures the relationship between the terms of the sequence far better. However, and this becomes more clear with more complicated recursive definitions, it is increasingly difficult for humans to fully grasp the shape and form of the sequence – something that becomes much simpler even in the more complicated form. In that way, the goal of unraveling these recursive definitions is a markedly human endeavor. The whole of the sequence or function is defined through the recursion, and the act of unraveling it merely serves to make it understandable to us. To make the full implications of the levels of self reference clear. In many ways, I think this is indicative of the goals of mathematics as a whole. In general, you start with a concise set of axioms and assumptions, and tease out some conclusion or theorem from them. The conclusion or theorem of course already existed as truth, through the statement of the axioms, but the act of proof teased out a bit of comprehensible meaning that was otherwise unclear from the statement of the axioms themselves. The whole of math exists in the statement of the axioms – the point of math is to bring the full weight and import of those simple statements to a understandable level. As much as I am loathe to admit it … it’s all a very human enterprise.
But I digress. That is a topic for another time.
So, in general, given a recursive function or sequence, it’s an interesting mathematical question of whether the recursion can be unwrapped to give some form of closed-form, non-recursive description of the same function or sequence. In my next post, or something soon at least, I’ll discuss generating functions, a neat tool used to such ends.
