Recursion

recursion.jpg

At a high level, a recursive process is one whose result depends on the results of the same process applied to a different set of parameters. Perhaps the easiest visual explanation of recursion is what happens when you point two mirrors to each other, or a camera to the screen that shows the camera feed. The "infinite corridor" that gets created in the process is due to recursion.

To take a real world example, let's think of a middle schooler who wants to know what mitosis means, before their first Biology class. They look up the word mitosis in the dictionary, and find the following definition:

mitosis/ the usual process by which cells divide, producing two *cells* each with the same number of chromosomes as the original *cell*

They realize that they understand most words in the definition, but lack the two highlighted in red: cells and chromosomes, which makes them not fully understand what mitosis means. At this point, they look up what cell means, repeating the process of looking something up in the dictionary, with a different parameter (the word cell instead of the word mitosis.)

cell/ the smallest unit of living matter that can exist on its own.

Since they understand all words in the current definition, they move on to looking up chromosome:

chromosome/ one of the very small structures like thin strings in the nuclei (= central parts) of animal and plant cells.

Now, they need to repeat the process for nucleus. And so on, and so forth, until they reach a definition where they understand all the words. Once they reached the end of their series of searches, they will finally have an understanding of mitosis, completing the initial process.

Using a dictionary can be described as a recursive process. Most of the times when we look something up, we fully understand the definition, which means that the recursion stops at the first step. But every now and then, we need to "dig deeper", repeating the original process.

Another example of recursion can be found in mathematics, in the definition of natural numbers:

A natural number is either 1 or n+1, where n is a natural number.

This is a recursive definition — it refers to itself while explaining the concept it introduces, which makes it convey a significant amount of meaning (the entire infinite series of natural numbers) within a very short statement.

Of course, language and recursion are both funny things, and make it equally easy to say nothing within a very short statement:

To understand recursion, you must understand recursion.

Let's take a look at a simple application of recursion in code.