Could I ask for physical analogies or metaphors for recursion?

Question

I am suddenly in a recursive language class (sml) and recursion is not yet physically sensible for me. I'm thinking about the way a floor of square tiles is sometimes a model or metaphor for integer multiplication, or Cuisenaire Rods are a model or analogue for addition and subtraction. Does anyone have any such models you could share?

Erythromycin

The Wikipedia article has some examples of geometric recursive structures – Kleenex

Answer 1

Imagine you're a real life magician, and can make a copy of yourself. You create your double a step closer to the goal and give him (or her) the same orders as you were given.

Your double does the same to his copy. He's a magician too, you see.

When the final copy finds itself created at the goal, it has nowhere more to go, so it reports back to its creator. Which does the same.

Eventually, you get your answer back – without having moved an inch – and can now create the final result from it, easily. You get to pretend not knowing about all those doubles doing the actual hard work for you. "Hmm," you're saying to yourself, "what if I were one step closer to the goal and already knew the result? Wouldn't it be easy to find the final answer then ?" ^(*)

Of course, if you were a double, you'd have to report your findings to your creator.

(also, I think I saw this "doubles" creation chain event here, though I'm not entirely sure).

---

^(*) and that is the essence of the recursion method of problem solving.

How do I know my procedure is right? If my simple little combination step produces a valid solution, under assumption it produced the correct solution for the smaller case, all I need is to make sure it works for the smallest case – the base case – and then by induction the validity is proven!

Another possibility is divide-and-conquer, where we split our problem in two halves, so will get to the base case much much faster. As long as the combination step is simple (and preserves validity of solution of course), it works. In our magician metaphor, I get to create two copies of myself, and combine their two answers into one when they are finished. Each of them creates two copies of themselves as well, so this creates a branching tree of magicians, instead of a simple line as before.

One such example is escaping a maze, or e.g. finding the shortest escape route's length. When arriving at a junction chamber, we simply send along copies of ourselves, one for each exit in front of us (the divide step). If the goal is to escape, at least one of the copies for at least one junction will indeed escape the maze, if the maze has an exit at all. And if the goal is finding the escape route's length, we simply listen to what each returning copy has to say to us, and then compose our report and pass it on to our maker (the conquer/combine step).

Another physical example is a Russian Matryoshka doll which is (an empty shell of) a doll that possibly contains a Matryoshka doll. The smallest innermost doll shell is empty.

More about recursion here (accumulators) and here (coin change).

---

Another, more conventional way to look at this is with only one worker who copies the execution recipes i.e. function definitions as needed, working along the input program.

In this analogy we are sitting at a desk, with an inexhaustible supply of empty sheets of paper at the side. We also have some execution recipes written each on its piece of paper, somewhere, accessible as needed, and one "main" recipe, the one for the "program" to be executed, on its sheet of paper.

Placing the program recipe in front of us, we follow it along, making notes at the margins as to the variables' values. Encountering a function call, we proceed to note the point of call at the margin, then copy that function's recipe onto a fresh empty sheet of paper and place that copy on top the current one in front of us, and follow it along from the top.

Thus a stack of sheets is forming in front of us. As we finish up with a recipe's execution, we note its return value, then discard the sheet of paper and write that value down at the place which is expecting it at the call site, then continue with the recipe currently in front of us. When there are no more recipes to follow, the execution stops.

One can immediately notice that it does not matter whether the recipe we're copying to the fresh blank sheet of paper is the same recipe we are currently following (recursion) or one which we have followed a few sheets down (mutual recursion). The new copy is fresh and new, independent of any other, with its own margins -- we do copy the original recipe, not any of its copies inside the stack.

---

Another example is the Sierpinski triangle which is a figure that is built from three quarter-sized Sierpinski triangles simply, by stacking them up at their corners.

Each of the three component triangles is built according to the same recipe.

Although it doesn't have the base case, and so the recursion is unbounded (bottomless; infinite), any finite representation of S.T. will presumably draw just a dot in place of the S.T. which is too small (serving as the base case, stopping the recursion).

There's a nice picture of it in the linked Wikipedia article.

Recursively drawing an S.T. without the size limit will never draw anything on screen! For mathematicians recursion may be great, engineers though should be more cautious about it. :)

Switching to corecursion ⁄ iteration (see the linked answer for that), we would first draw the outlines, and the interiors after that; so even without the size limit the picture would appear pretty quickly. The program would then be busy without any noticeable effect, but that's better than the empty screen.

Kieffer

Thank you very much! This is helpful, including the Sierpinski Triangle as an "unknowable by us" base case. – Erythromycin

Answer 2

I came across this piece from Edsger W. Dijkstra; he tells how his child grabbed recursions:

A few years later a five-year old son would show me how smoothly the idea of recursion comes to the unspoilt mind. Walking with me in the middle of town he suddenly remarked to me, Daddy, not every boat has a lifeboat, has it? I said How come? Well, the lifeboat could have a smaller lifeboat, but then that would be without one.

Parturition

Answer 3

I love this question and couldn't resist to add an answer...

Recursion is the russian doll of programming. The first example that come to my mind is closer to an example of mutual recursion :

Mutual recursion everyday example

Mutual recursion is a particular case of recursion (but sometimes it's easier to understand from a particular case than from a generic one) when we have two function A and B defined like A calls B and B calls A. You can experiment this very easily using a webcam (it also works with 2 mirrors):

1. display the webcam output on your screen with VLC, or any software that can do it.
2. Point your webcam to the screen.
3. The screen will progressively display an infinite "vortex" of screen.

What happens ?

• The webcam (A) capture the screen (B)
• The screen display the image captured by the webcam (the screen itself).
• The webcam capture the screen with a screen displayed on it.
• The screen display that image (now there are two screens displayed)
• And so on.

You finally end up with such an image (yes, my webcam is total crap):

"Simple" recursion is more or less the same except that there is only one actor (function) that calls itself (A calls A)

"Simple" Recursion

That's more or less the same answer as @WillNess but with a little code and some interactivity (using the js snippets of SO)

Let's say you are a very motivated gold-miner looking for gold, with a very tiny mine, so tiny that you can only look for gold vertically. And so you dig, and you check for gold. If you find some, you don't have to dig anymore, just take the gold and go. But if you don't, that means you have to dig deeper. So there are only two things that can stop you:

1. Finding some gold nugget.
2. The Earth's boiling kernel of melted iron.

So if you want to write this programmatically -using recursion-, that could be something like this :

// This function only generates a probability of 1/10
function checkForGold() {
  let rnd = Math.round(Math.random() * 10);
  return rnd === 1;
}

function digUntilYouFind() {
  if (checkForGold()) {
    return 1; // he found something, no need to dig deeper
  }
  // gold not found, digging deeper
  return digUntilYouFind();
}

let gold = digUntilYouFind();
console.log(`${gold} nugget found`);

Or with a little more interactivity :

// This function only generates a probability of 1/10
function checkForGold() {
  console.log("checking...");
  let rnd = Math.round(Math.random() * 10);
  return rnd === 1;
}

function digUntilYouFind() {
  if (checkForGold()) {
    console.log("OMG, I found something !")
    return 1;
  }
  try {
    console.log("digging...");
    return digUntilYouFind();
  } finally {
    console.log("climbing back...");
  }
}

let gold = digUntilYouFind();
console.log(`${gold} nugget found`);

If we don't find some gold, the digUntilYouFind function calls itself. When the miner "climbs back" from his mine it's actually the deepest child call to the function returning the gold nugget through all its parents (the call stack) until the value can be assigned to the gold variable.

Here the probability is high enough to avoid the miner to dig to the earth kernel. The earth kernel is to the miner what the stack size is to a program. When the miner comes to the kernel he dies in terrible pain, when the program exceed the stack size (causes a stack overflow), it crashes.

There are optimization that can be made by the compiler/interpreter to allow infinite level of recursion like tail-call optimization.

Myo

I like the "climbing back" line. That is often hidden when others describe recursion, but it is so important. – Erythromycin

came here to add something about the "Russian matryoshka doll" and found your answer that starts with it. :) will read later. :) --- the reason: Haskell's T = F T = F (F T) = F (F (F (F ... ))) I saw today in an answer. – Kieffer

Answer 4

Take fractals as being recursive: the same pattern get applied each time, yet each figure differs from another.

As natural phenomena with fractal features, Wikipedia presents:

• Moutain ranges
• Frost crystals
• DNA
• and, even, proteins.

Parturition

Not sure this answers the question. Fractals are (arguably) an example of mathematical recursion (like fibonacci) not a physical analog. – Gigantism

Wikipedia mentions as Natural phenomena with fractal features moutain ranges, frost crystals, DNA, and, even, proteins. – Parturition

I appreciate this pointer, because the article at Wikipedia has a stack of concrete examples. And it mentions self-similarity, which is a good criterion by which to search for physical cases – Erythromycin

Answer 5

This is odd, and not quite a physical example except insofar as dance-movement is physical. It occurred to me the other morning. I call it "Written in Latin, solved in Hebrew." Huh? Surely you are saying "Huh?"

By it I mean that encoding a recursion is usually done left-to-right, in the Latin alphabet style: "Def fac(n) = n*(fac(n-1))." The movement style is "outermost case to base case."

But (please check me on this) at least in this simple case, it seems the easiest way to evaluate it is right-to-left, in the Hebrew alphabet style: Start from the base case and move outward to the outermost case:

                                                   (fac(0) = 1)
                                      (fac(1) = 1)*(fac(0) = 1)
                             (fac(2))*(fac(1) = 1)*(fac(0) = 1)
       (fac(n)*(fac(n-1)*...*(fac(2))*(fac(1) = 1)*(fac(0) = 1)
(*  Easier order to calculate <<<<<<<<<<< is leftwards, 
    base outwards to outermost case;
    more difficult order to calculate >>>>>> is rightwards, 
    outermost case to base  *)

Then you do not have to suspend items on the left while awaiting the results of calculations further right. "Dance Leftwards" instead of "Dance rightwards"?

Erythromycin

very good! indeed there's a duality there, which I tried to explore in my linked "Prolog accumulators" answer; also hinted at in Wikipedia's "corecursion" article as "with 'time arrow' reversed, as it were". recursion goes to the base case first (i.e. your left-to-right), and then contracts back calculating the result on its way back, right-to-left. Iteration with accumulators just goes to the left from the right, starting from the recursion's base case. – Kieffer