Recursion is a somewhat modern concept whose use, in the modern sense, originates in the 19th century. It's generally discussed in the contexts of math and computer programming but exists in many other domains as well. Topics of recursion can range from simple to highly complex. In the sections below, we'll focus on the simple topics, starting with a succinct definition of the word itself.
Definition of Recursion
Recursion is a behavior which is exhibited when an object or concept is defined in terms of itself.
This may sound strange at first, but by the end of this article, you will find the core concept of recursion to be simplicity itself. In the sections below, we'll introduce some real-world places where recursion occurs, showcase some pictures of recursion in action, then discuss recursion within different specific contexts.
Recursion in the Real World
There are many instances of natural and man-made instances of recursion in the real world. A few common and well known types are:
- Snowflakes: real-life snowflakes are recursive in nature. The "edges" of snowflakes follow the same shape-patterns as the snowflake itself.
- Picture in a Picture: pictures which contain themselves inside of themselves. An example may be: a person holding a picture of themselves, where the picture is a picture of them holding themselves, etc. This is known as the Droste Effect. Another example is shown in the images below
- Artwork: many artists, such as M.C. Escher, have creating paintings and other form of artwork with are recursive. An example paining is shown in the images below, where two hands appear to be drawing each other. It is not clear which hand, if any, came before the other.
- Mathematics: many sequences, such as the Fibonacci sequence, have their elements defined by previous elements. In the fibonacci sequence, any element, except for the first two, is the sum of the previous two elements. The first two elements are both "1".
- Programming: many programs use functions which invoke themselves to eventually calculate some data. For example, we can create a fibonacci function which will let the user figure out the nth term in the fibonacci sequence. The function can then invoke itself with n-1 and n-2 and add up the two results (or return 1 if its one of the first two terms).
- Fractals: a fractal is a pattern which, when "zoomed into", will still make the same pattern. Some fractals appear in nature, such as the patterns behind forest formation and river branching.
Visual Recursion
The images below are visual examples of recursion, some of which are examples of points previously discussed. You can make an image fullscreen by clicking on it. Some of the concepts below, such as surreal numbers, are not relevant themselves to this discussion but are worth including for their recursive visualization.
Types of Recursion
In terms of the continuity of a recursive process, there are two main "types" of recursion:
- Infinite Recursion: this is a type of recursion where the recursive process is repeated indefinitely. This applies mainly to mathematical concepts and computation theory.
- Finite Recursion: a type of recursion where a base case is eventually reached and the recursive process completes. This applies mainly to practical applications of mathematical concepts and actual computer programming.
Recursion in Math
In this section we'll briefly discuss some uses of recursion in mathematics. Expanding upon the point made in the previous section: recursion is sometimes used when defining sequences of numbers. In sequences, such as the Fibonacci sequence discussed above, recursion can be used to define how individual items of the sequence can be calculated. Not all sequences use recursion, and some sequences can be defined with recursion and also alterantively without it. For example, the sequence of Factorial numbers can be defined as follows:
- Definition without recursion: the nth factorial number is the product of all integers from 1...n.
- Definition with recursion: the nth factorial number is the number n multiplied by the (n-1)th factorial, with a base case of: when n = 1, the factorial is also 1.
In both definitions above, we achieve the same sequence of numbers.
The procedure for proving a mathematical statement can also be defined as a recursive process. In order to conclusively prove a mathematical statement (so conclusively that you get your PhD.), you will need to reduce your statement to other already-proven statements via mathematical rules and operations, or directly reduce it to the axioms of the system (axioms are rules which are "self-evident" and don't require further proof). If you reduce a statement to other proven statements, those proven statements will first need to have been proven by being reduced to other proven statement, etc., until the axioms are reached. The axioms would represent base cases in this context.
Fractal designs and artwork can be created by using mathematics to render the image recursively. This process can be applied to pure fractals or to artwork based in fractals. This three minute YouTube video elegantly demonstrates the recursive nature of fractals by continuously zooming in on a fractal set, and it has a nice visual to it.
Recursion in Programming
In this section we'll briefly discuss some uses of recursion in programming. Recursion in programming is similar to recursion in mathematics. For example, I could directly utilize the recursive definition of the Fibonacci sequence given above to calculate any particular fibonacci number. The list below covers some common use cases for recursion:
- Calculating items in a sequence: such as the fibonacci sequence.
- Finding something in a hierarchy: if we have something with parent-child relationships, such as an ancestry tree, we might need to find or operate on items even if we don't know how far back the tree goes. Recursive functions are a natural fit for this kind of scenario.
- Looking for a Link in a Chain: if we have some data "chained together", we might need to find something in that chain, even if we don't know how long the chain is. Recursion is a fit for this type of problem as well.
Recursion also plays a part in many scenarios not listed above, and also in the foundations of computation theory, the field of study which makes computers and software possible. For an outline on how to code recursive functions with examples, please visit our page on How to Write Recursive Functions.
More on Recursion
For more information on recursion, feel free to take a look at this article.