Recursion is a concept that fascinates people, even non-computer scientists. All the same, I’ve decided to stop teaching it in my introductory programming course. I’d rather wait until I can motivate it with self-similar data structures.
Nevertheless, recursion is pervasive. Who can’t help but wonder at the following phenomena?
The largest lake in the world is Lake Superior. The largest island in it Isle Royale. The largest lake on Isle Royale is Siskiwit Lake. The largest island in Siskiwit Lake is Ryan Island. The largest body of water on Ryan Island is an intermittent pond named Moose Pond. The largest island in this pond is Moose Boulder.
A friend told me today that his employer could not turn on vacation messaging because of the potential danger of overloading their mail server. He explained that if person A sent a message to person B, who was autoreplying with a vacation message, the autoreply would go to person A. If person A was also autoreplying, then A would autoreply to B, who in turn would autoreply to A, who in turn would autoreply to B, and so on. The replies would ring back and forth, flooding both mailboxes.
Recursion that never ends is especially intriguing to us.
This video shows what happens when you point a webcam at its own display. My laptop is grabbing images from the camera and showing them on its monitor. And what is the content of these images? Well, the camera is facing the monitor, so the images are of whatever the monitor is showing. But the monitor is showing what the camera sees. And so on.
If these two devices were modeled as functions, they’d have this form:
function getCameraImage() return getMonitorImage() function getMonitorImage() return getCameraImage()
Recursion which bounces back and forth between two entities like this is usually called mutual recursion. When mutual recursion happens amongst people, we call it co-dependence.