What Links Here? (14 articles…)

Outbound Links (85 articles…)

Unbounded Recursion

(Alternatively see Recursion where you can learn about applying bounds to your recursion, or detecting cycles in referential data structures)

there is no general method to determine whether a given program will ever halt or will run forever; this is the undecidability of the halting problem. —source

Death by Unbounded Recursion

Unbounded recursion is not just something that can cause your computer to crash or your programs to freeze. Unbounded recursion can kill you. Particularly if you are an army ant.

Soldier ants are blind, and they follow the chemical trails (pheromone, scent) left by other ants. They also leave their own chemical trail, to help the army ants behind them to follow the same trail they are on.

If somehow the trail gets looped onto itself, then the ants can begin to follow an endless loop. They will continue to walk on such a path, over and over, until they literally die of exhaustion and starvation.

Unbounded Recursion in Children's Nursery Rhymes

The nursery rhyme there's a hole in my bucket is centered on an unbounded recursion that arises when attempting to repair a leaky bucket. The repair itself ultimately requires use of a bucket. The joke is only effective because of the convoluted nature of the recursion: the loop back takes 18 verses, or 9 steps, far more than our short term memory can readily hold.

The best nursery rhyme on the topic of infinite regress is clearly "The Siphonaptera"

Big fleas have little fleas,
Upon their backs to bite 'em,
And little fleas have lesser fleas,
and so, ad infinitum.

...though I fail to see how such a verse could ever help a child be lulled into sleep, it's more likely to lead to Invisible Biting Bug Syndrome, which cannot be fun. The seldom used second verse is very good too:

And the great fleas, themselves, in turn
Have greater fleas to go on;
While these again have greater still,
And greater still, and so on.

...while this variation is pleasing to any fans of fractal formations:

Big whorls have little whorls
That feed on their velocity;
And little whorls have lesser whorls
And so on to viscosity.

Early in "Slaughterhouse 5" we're introduced to the infinitely recursive song of Yon Yonson:

My name is Yon Yonson, I work in Wisconsin, I work in
a lumbermill there. The people I meet when I walk down
the street, They say, 'What is your name?' And I say
'My name is Yon Yonson, I work in Wisconson...

Note that even Yon's name is recursive. Yon Yonson, so named as Yon is the son of Yon. His son will presumably be named Yon Yonson and so on.

This category is incomplete without mentioning the extremely annoying "song that doesn't end" from the show Lamp Chop. Here's a 10 hour mix of it. The song that doesn't end

Turtles all the way down.

This quote is in the first few pages of 'A brief history of time,' a book which is one of the most widely purchased‐but rarely read—books in history. Most people, self included, have read about as far as this quote and no further.

A well-known scientist (some say it was Bertrand Russell) once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: "What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise." The scientist gave a superior smile before replying, "What is the tortoise standing on?" "You're very clever, young man, very clever," said the old lady. "But it's turtles all the way down!" —Hawking

This is not connected to the Tortoise Hare Algorithm which is useful for finding cycles in referential data structures.

Jokes Featuring Unbounded Recursion

You might hope that this section (Jokes about Unbounded recursion) will be a quick read. Sadly, you may find that it takes much longer than you anticipated.

The standard recursion joke is any variation on the following:

To understand recursion you must first understand recursion.

This is too simple to be particularly funny. On the plus side, it is a joke about unbounded recursion, so it is at least a little bit funny.

As far as standard recursion jokes go, they don't get more standard than the practice of having an index entry at the back of a printed book which says "Recursion, Page 251" where the index entry itself is on page 251. This is particularly funny because you know that the page number is not known at the time of writing, so it involves arduous toil and communication on the part of author and printer.

At this point, it's not so much a "joke" as a "convention".

The less funny variant of this joke, which is too simple to raise more than 1 out of 7 on the chucklemeter, is to have an index entry which simply states:

Recursion
See Recursion

Even Google get in on this joke:

But it's so simple a joke that no technical book is complete without it. It would be an error to write a technical book and to leave that joke out. Much as:

It is a syntax error to write FORTRAN while not wearing a blue tie.

...which is a joke that does not involve unbounded recursion and hence it does not exist in this section. If you see it here you are mistaken.

You can find that joke quote at this well regarded article on the history of computing: A Brief, Incomplete, and Mostly Wrong History of Programming Languages. It is actually a satirical tour, though I don't wish to spoil your enjoyment by telling you that before you've read it, although I probably did.

And it includes this mention of recursion in LISP:

LISP (now "Lisp" or sometimes "Arc") remains an influential language in "key algorithmic techniques such as recursion and condescension"

This is funny because "recursion" and "condescension" are two words that rhyme, and because the first part is blatantly true, while the second part, the swift dig at Lisp weenies, is cruel (i.e. slapstick) and arguably true. The violent accusation creates a sense of tension.

The juxtaposing of blatant truth with arguable truth creates a tension, the release of which is achieved through laughter.

The joke is particularly effective because the entire satirical turn exists in the final word. Replace that final word with a different word (such as 'encapsulation') and you have a perfectly serious sentence. The fact that it is so close to a serious statement pushes it into the "satirical" sub category.

The one downside of this joke is that although it mentions recursion it does not employ recursion, nor hint at unbounded recursion. So this joke also should not exist in this section. It originates from an article by a Verity Stob.

Onto better things:

There is an old story about computer pioneer Grace Murray Hopper, who read instructions on a bottle of shampoo telling her to " lather, rinse, repeat." As the story goes, she claims that she tried to follow the directions but that she ran out of shampoo. —Source

This is funny for four distinct reasons.

Firstly, it is funny because it is an example of literalism. Literalism is the way that computers take things literally.

Secondly, it is funny because it is a joke about unbounded recursion. Jokes that mention unbounded recursion automatically get a tick in the funny column.

Third, it is funny because it uses indirection. Rather than bluntly state that the instruction went on forever, she states that she ran out of shampoo. The listener then has to reason about the events which lead to this, and will thus detect the flaw in the instructions: they contain an unbounded recursion. This is funny because the extra level of indirection makes the joke occur inside the mind of the listener, where it is loudest and thus funniest.

Fourth, it is funny because it teaches us something about the nature of unbounded recursion. Instructions that create unbounded recursion don't simply run forever. They also exhaust resources: thus they cause the classic stack overflow, or they cause an out of memory problem, or they cause a printer to run out of paper, or, as in this case, they cause us to use up all of our shampoo. So Grace has cleverly enhancified the joke with a little lesson in there about the consequences of unbounded recursion. Ah Grace, you are very clever.

Another index-related example of infinite loops, is the "multi-step" chain. The longer the chain, the better.

Q: What does the "B" in Benoit B. Mandelbrot stand for?

A: Benoit B. Mandelbrot.

And:

Q: Why did the angry function exceed the callstack?

A: It got into an argument with itself.

Lastly:

See also, "Jokes Featuring Unbounded Recursion"

Cartoons Featuring Unbounded Recursion.

Jeremy Banx, @banxcartoons

John Atkinson, Wrong Hands

Jackie Jokers Issue#1

Russian Doll Sonogram by Paul Noth

And on the pedestal these words appear: "And on the pedestal these words appear: "And on the pedestal these words appear: "And ...
Ozymandias by XKCD

$puppet fractal$
'Like A Puppet On A String...' by DevilishlyCreative

Perhaps inspired by Einstein holding Einstein.

einstein holding einstein.jpg
Einstein holding puppet Einstein

Cover Art for 'The Third Policeman' a novel which deals with unbounded recursion

$pizza_fractal_201209061.png$
Pizza Frac'zas by kris straub of chainsawsuit

The Droste Effect

Below are various images displaying the Droste Effect.

The effect of including a smaller version of a picture inside a larger instance of a picture (and thus producing infinite regress) is known as the Droste Effect. Droste cocoa power is a major Dutch brand of cocoa powder. Boxes of their product include a picture of a nurse carrying a serving tray with a cup of hot chocolate and a box of Droste Cocoa Powder. The box that the nurse is carrying includes a picture of the nurse carrying a tray of hot chocolate and a box of Droste Cocoa Powder. The box that the nurse is carrying, help, includes a picture of the nurse carrying a tray of hot chocolate and a box of Droste Cocoa Powder. Stop me. The box that the nurse is carrying, kill me, includes a picture of the nurse carrying a tray, help me, of hot chocolate, stop me, and a box, kill me now, of Droste Cocoa Powder.

I could go on all day about that box that the nurse is carrying.

Which necessitates a showing of the cover art for the Pink Floyd Album, Umma Gumma. Bruce tells me that the Australian reproductions of this cover were so poor you couldn't see the innermost image. (Sometimes the innermost image is covered by a sticker)

The XKCD cartoon number 668 is a very fine example of the genre. (Full discussion here).

There is a Droste effect image in each of the "Treehouse" books by Andry Griffiths and Terry Denton. This marvelous example is from 'The 91 Storey Treehouse'

There are several Droste effect portraits in popular media.

Airplane

And here's the cover of the computer game The Stanley Parable:

The Stanley Parable cover, which shows the words The Stanley Parable above a vintage x86 desktop computer on the screen of which can be seen The Stanley Parable cover, which shows the words The Stanley Parable above a vintage x86 desktop computer on the screen of which can be seen... and so on.

Paradox

There are many paradoxes that arise when a statement refers to itself. In the cleverest of these, it is not obvious that a statement refers to itself, and you need to perform a sophisticated inquiry to see the way in which the statement is self-referential.

Time Travel paradoxes ("Temporal paradoxen") can include spontaneous creation (I travel back in time and give my younger self my favorite hat.... a hat which I have had since childhood... it was given to me by a wise old stranger), impossible destruction (I go back in time and shoot a young man... subsequent inquiries reveal him to be my own grand father), and worse. Attempts to unravel these conundrums can result in infinite regress.

Circular Reference

In any system utilizing "references", if upon following a reference, you pass a point A and later, while traversing the references of A you arrive back at point A, a "circular reference" has been observed. These suckers are nasty.

The most well known example of Circular References arise in spreadsheet programs such as Excel.

Here's a simple example where cell A1 contains a formula "=B1" and "B1" contains a formula "=A1"

This creates a paradox known as a "Live Lock".

A contrasting problem is the "Dead Lock".

Grid Lock

You are at an intesection, the light is green, do you go? Yes you do right? You check if any traffic is coming from the left or the right (just in case) and then you go. Simple.

NOT SO FAST BOJANGLES! You didn't check the traffic ahead: is the intersection clear? Is there enough room in the traffic that you won't end up stuck in the intersection when the light changes to red?

If you did move ahead with out checking, then I'm sorry to tell you, you are part of the problem.

It possible for traffic queue A to block queue B which blocks queue C which blocks queue A, etc.

Grid-locks in traffic are fascinating stuff. It's easy to see how they can occur. But how on earth do they get resolved, once they've set it?

The simplest thing to do would be to make a few cars evaporate.

This image is allegedly from the Red Hat office in Sao Paolo, Brazil.

I hate to ruin the fun, but the gridlock above would be solved if just one car could evaporate. I've highlighted it here:

If you enjoyed that game, let's play another round....

Which vehicle or vehicles need to be let through to make this one untangle itself?

Here's my spoiler for that one.... the silver bus needs to be let through by the ambulance. Which is very counter intuitive. If the ambulance wants to go, it needs to let the bus through.... the bus that is causing all the problems!

Oh, I've found some more about the one above, it's called "Warsaw Tetris"

Feedback Control Systems

In control systems theory there is an important concept of using 'feedback' as a mechanism to regulate behaviour of the system. This is a process whereby a measurement of the system's output is used as an input.

Consider the Nyquist stability criterion.

This explorable explanation "going critical" by Kevin Simler covers some related topics, including infection, immunity, transfer of ideas and knowledge, and much more.

The Trouble With Tribbles

The trouble with tribbles is that they consume all available materials as they reproduce at an unbounded exponential rate.

Perpetual Motion

A perpetual motion machine is a machine that uses its own motion to fuel its own motion, and also performs work (i.e. applying force to move mass a distance, any distance) as a byproduct of this motion performed by the machine that perpetually performs the motion performed by the machine.

Infinite Battle from EyesMaze

$john_lennon_shirt_fractal.png$

Books about recursion

The Recursive Book of Recursion - subtitle "Ace the Coding Interview with Python and JavaScript", a book by Al Sweigart
Recursion by Blake Crouch | Goodreads a 2019 Sci Fi Novel

Special mention for recursive books must go to If on a winter's night a traveler by Italo Calvino. It begins with an amazing recursive introduction:

You are about to begin reading Italo Calvino's new novel, If on a winter's night a traveller. Relax. Let the world around you fade.

... and it doesn't let up, delving deeper and deeper into the second-person narrative style where you the reader are the central character in a book about the book.

wiki.secretGeek