2.01. Introduction to Recursion
Introduction
As I said in the review article for section 1, before we start discussing the tools for making REALLY big numbers, we need to learn what exactly recursion is. That will be the main step for preparing us for the journey towards the truly gargantuan. So in this page, we'll learn what recursion is, and why it is important for making large numbers.
What is recursion?
Now, recursion is really a simple concept. In a general sense, recursion refers to repeatedly applying a process to an object in a way that is self-similar. A simple example of this would be two mirrors facing each other. The image of the one mirror appears in the image of the other, whose image itself appears in the image of the one mirror, and so on. With that effect, a mirror would end up looking something like this:
This image is pretty clearly recursive, with the walking man infinitely copied into the mirror.
Recursion can be applied to numbers as well, by repeatedly applying a function to a number. This is not a complicated concept at all. In fact, counting is a recursive process. When you count, you repeatedly apply the successor function (i.e. adding 1) to a number. For example, to count from 3 up to 8, you repeatedly apply the successor function to 3 until you get to 8, giving the sequence of numbers 3, 4, 5, 6, 7, 8.
When you add two numbers A and B, you apply the successor function to A, B times. Therefore addition is itself a recursive function! The same can be said for multiplication, where you add A to 0, B times, and exponentiation, where you multiply 1 by A, B times. Those are themselves also recursive functions. As you can see, recursion is really part of the very base of mathematics itself!
How is recursion useful for making large numbers?
You may wonder: how is recursion useful in googology, the study of large numbers? It might already be straightforward why, as the foundations of googology are the foundations of math itself, and there is no getting around that. But you may object, how exactly can recursion be used specifically to devise large numbers? Well, as it turns out recursion is a vital component of devising large numbers, and one people use to make large numbers without even thinking about it!!!
The way you create large numbers with recursion is by repeatedly applying a powerful function to a number. That is not counter-intuitive at all. After all, what better way is there to make use of a large number function (the factorial for instance) than to repeatedly apply it to a number? Using recursion to make large numbers is not only logical and comprehensible, it's also simple. That is itself part of the essence of googology: looking for large numbers with simple definitions! This is in contrast to salad numbers, naive attempts to name the biggest number you can by making a sloppy mishmash of completely random numbers and functions. Salad numbers are frowned upon by googologists both because they're inelegant and because in their definitions, one function almost always dominates while the rest don't meaningfully affect the number's size. But let's not get ahead of ourselves, and return to the idea of recursion.
To see the effect of recursion in action, let's make a fast-growing function F(n), and define it as 10^10^10^10 ... ^10 with n tens. Then we'll repeatedly apply F(n) to 10, to get a feel of how useful recursion is. With that we can make the fast-growing sequence:
10
10^10^10^10^10^10^10^10^10^10 (already absurdly huge!)
10^10^10^10^ ... ... ... ... ... ^10 with 10^10^10^10^10^10^10^10^10^10 10s (UTTERLY INSANE!)
10^10^10^10^ ... ... ... ... ... ^10 with N 10s, where N is the previous 10^10^10^10^ ... ... ... ... ... ^10 number (SUPER YIKES!!!)
and so on.
Now what if we continued to the 100th member of the sequence? Or the googolplexth member of the sequence? Or the 10^10^10^10^10^10^10^10^10^10th member of the sequence?! Or the Nth member of the sequence where N is the 100th member of the sequence?!? We can go on like this as far as we want. For instance, what if you made a new function G(n) and defined it as the nth member of the sequence described above, and repeatedly applied it to a number, say, G(100) times to G(100)? That idea is itself recursive in nature. Are you starting to see a pattern? If so, then that's good. Hopefully by now you're convinced that recursion is completely vital in making large numbers.
Conclusion
Now that we are finished with discussing what recursion is, we are now ready to examine some ways to make large numbers using recursion, and THAT is where the fun begins. Are you ready to look at some REALLY big numbers? If you are, then let's proceed to some notations for large numbers, starting with Knuth's up-arrow notation.