Recursion
The amount of nonsense being said about recursion is an illustration of how much bullshit we have out there.
The right understanding is that it is a captured generalization of a spiral-shaped process, when at each step it is being decided to stop and “return” (“unwind”) or to continue (to go on) without returning.
A recursive function has two aspects.
It calls itself, just like an imperative while loop “loops back”
The best metaphor is to check is the “result” so far (whatever it may be) is good-enough.
Just like an imperative loop, it always has a “termination test”, wich is traditionally called “the base case” (of a recursion).
This captures the exactly same notion as an imperative “while-not loop” does.
Unlike an imperative loop, there could be arbitrary many “base cases” (conditions on which not to call itself again and return a result).
It calls itself with a smaller (reduced) state-space (version of the same problem)
This is analogous to the notion of mathematical induction, where they rely on
the fact, that Natural Numbers are defined with and closed under the +1
operation and, as a direct consequence, are totally ordered.
General recursion assumes that the individual steps of a process are closed, totally ordered and, in addition, have at least one base case, captured directly in the recursive function (which defies a spiral-shaped process, which actually grows and then shrinks (unwinds)).
So, schematically, it is a fork on a graph – a “node” either calls itself or to returns. Imagine looking at a shrinking spiral from its “base” – this is the process “before a base case is reached”.
After the base case is reached, the “unwinding part of the process” is backtracking (this is not an arbitrary coincidence), returning from all these nested (and “pending”) calls to itself.
The metaphor is going back from the summit of a mountain, but also doing something with the result (if it is not a tail-call, which means nothing more to do - just go back down).
Just imagine that one goes not in a straight line, but in a spiral, which are, in may senses, the same thing, being in a different shape.
Where are all these notions came from
Unlike mathematicians, who does not thing of care about actual representation or even existence of their abstraction, we have not only to think about the actual resulting processes (which our programs cause and invoke), but also about the shapes of such processes, which are not just linear sequences.
Well, they have to be linear sequences, where all the branching expressions and recursive function applications (also expressions) are properly nested, to form an implicit sequence, which may turn out to, just like the proteins, be in various shapes (of an invoked process).
This analogy is not arbitrary too. The Universe “runs” the proteins and enzymes (literally!), which are all sequential structures with unique emergent properties (protein folding).
Enzymes are made out of proteins, just like (ideal) LISP programs from List structures.