To Understand Recursion One Must First Understand Recursion

To understand Recursion one must first understand Recursion - Stephen Hawkins

Oh no! Again something talking about itself. Haven't we had enough meta already for one blog? First of all. No, definitely not! But also, recursion is not meta, for the same reason meta is not recursion (did recursion again). They are not the same thing!

I have an entire article about the different meanings of meta, the cultural interpretation of meta and my interpretation of meta. When I first encountered the concept of Meta I had problems separating it from recursion, and as we have learned in my article about distinctivness, being able to separate concepts helps us to better understand them. So this is my attempt to separate it for my self in the hopes that this effort might help someone else.

Thought is both a recursive and meta-level object. Let's interpret it from both perspectives. We can think about thinking, which leads to meta-cognition. Or recursively, we could say that a thought is just a collection of thoughts, which each is a collection of thoughts. Think about it ;). To think a thought we first need to think about other thoughts, to be able to wrap them with a new thought.

So recursion is something that it is defined (formed or structured) in terms of itself (simpler forms of itself), which is also known as self-similarity. Meta on the other hand is when something exists in the lower level and higher level context, essentially creating a sense of self-reflection. Meta-cognition (to stick to the thought analogy) is the cognition about cognition, our ability to be aware of our thoughts enabling us to think about thinking.
A manager managing other managers, is a meta-managers. However it is not recursive. It doesn't imply that a manager is defined by being a manager. A mirror mirroring another mirror, which in terms mirrors the mirror mirroring it. Is both self-reflective (literally) aswell as self-similar.

In programming recursion is simply a function that calls itself to model an iterative undetermined algorithm, with a base case, usually to navigate recursive structures.
This can be done in the start or at the end of the execution flow. If it is done at the end, it is just like a do while construct. Essentially, if we think of a program as a linear flow of execution, we jump with our instruction pointer back to the start of that function passing it as arguments the result of the calculation. A loop. While in more imperative language this is not necessary, because inside of the loop we can access state outside of the loop, in some functional languages to accumulate state and iterate over it, recursion is the only option. This is also called Tail Recursion which is very efficient. As the operations are all resolved before entering the next recursive level. The opposite is true with Head Recursion which enters the recursive stack before evaluating the rest. Creating this unresolved point of tension. A bit like in the movie Inception where at a certain point in one dream they had to slow down time by entering yet another dream on the next recursive level. Another good example for recursion, and not meta. Meta would be a dream about dreams. Not a dream in which you have a dream. You see? The entry and exit point of the dream leads to exactly the same on the next level, self-similar. While a dream about a dream is a bit more subtle.

Like a painting of a painting. Or even more extreme. A painting of the same painting being painted.

Recursion in art on the other hand overlaps with recursion in geometry. When you have structures with self-similarity, it means that parts of the whole are composed in the same structure as the whole, meaning on every level of detail you will observe the same structure.
This is also known as a Fractal. We could turn the painting about the painting into recursive art, by turning it into a fractal. Where each painting contains the painter painting the painting from the exact same angle and each subsequent painting containing every part of the whole sequence (a painter, painting a painter, painting a painter painting a picture).

We have now been talking about recursion and meta, their distinction in programming and art, and to close the gap between them let's give two final examples in language. I will leave it up to the reader, as an exercise to understand which one is which.

Sentences in general are formed of phrases, and unlike this one can be very long

WOW = World of WOW