How Not to Teach Recursion

About Euclid’s Algorithm: I actually implemented several times at work, it is useful when you are dealing with periodic events, which is common in real time systems. The typical question is: a task has to do something every 20, 30 and 40ms, at which period should you schedule your task (minor cycle)? The answer is gcd(20,30,40)=10ms and it can be computed using the Euclid's Algorithm.

But in most languages, Euclid's Algorithm is actually better implemented with a loop, and it brings me to one thing I realized about recursion that isn't commonly taught.

At a low level, recursion is implemented with a stack, so if you have a stack, you don't actually need to call functions to implement a recursive algorithm, in fact, many recursive algorithms don't need a stack at all (tail recursion). A recursive function call just means "remember my position and all local variables" and a return means "go back to where I was".

One advantage of this "machine first" thinking that it can help with optimization. By thinking about the stack, you may realize that you don't need to remember all local variables, that the call is always made from the same place so you don't need to remember your position. You may even realize that a stack, which is the natural data structure of recursion is not actually the best, for example, an array might be better, which, by the way, is one of the basis of dynamic programming.

And if you get to functional programming later, understanding what the machine does behind the scenes can give you a better grasp of the idea.

> Another standard, time-honored pedagogic device is the dumb joke: “to understand recursion you must understand recursion”, and so on. These confuse recursion with cyclicality.

I thought most forms of this joke centered around the definition of recursion, which nicely mimics a definition of a function that references itself. I am not sure what the author is getting at.

MARTIN AND THE DRAGON

In ancient times, before computers were invented, alchemists studied the mystical properties of numbers. Lacking computers, they had to rely on dragons to do their work for them. The dragons were clever beasts, but also lazy and bad-tempered. The worst ones would sometimes burn their keeper to a crisp with a single fiery belch. But most dragons were merely uncooperative, as violence required too much energy. This is the story of how Martin, an alchemist’s apprentice, discovered recursion by outsmarting a lazy dragon.

One day the alchemist gave Martin a list of numbers and sent him down to the dungeon to ask the dragon if any were odd. Martin had never been to the dungeon before. He took a candle down with him, and in the furthest, darkest corner found an old dragon, none too friendly looking. Timidly, he stepped forward. He did not want to be burnt to a crisp. ‘‘What do you want?’’ grumped the dragon as it eyed Martin suspiciously.

‘‘Please, dragon, I have a list of numbers, and I need to know if any of them are odd’’ Martin began. ‘‘Here it is.’’ He wrote the list in the dirt with his finger:

(3142 5798 6550 8914)

The dragon was in a disagreeable mood that day. Being a dragon, it always was. ‘‘Sorry, boy’’ the dragon said. ‘‘I might be willing to tell you if the first number in that list is odd, but that’s the best I could possibly do. Anything else would be too complicated; probably not worth my trouble.’’

‘‘But I need to know if any number in the list is odd, not just the first number’’ Martin explained.

‘‘Too bad for you!’’ the dragon said. ‘‘I’m only going to look at the first number of the list. But I’ll look at as many lists as you like if you give them to me one at a time.’’

Martin thought for a while. There had to be a way around the dragon’s orneriness.

‘‘How about this first list then?’’ he asked, pointing to the one he had drawn on the ground:

(3142 5798 6550 8914)

‘‘The first number in that list is not odd,’’ said the dragon.

Martin then covered the first part of the list with his hand and drew a new left parenthesis, leaving and said ‘‘How about this list?’’

‘‘The first number in that list is not odd,’’ the dragon replied. Martin covered some more of the list. ‘‘How about this list then?’’

(6550 8914)

‘‘The first number in that list isn’t odd either,’’ said the dragon. It sounded bored, but at least it was cooperating.

‘‘And this one?’’ asked Martin.

‘‘Not odd.’’ ‘‘And this one?’’

(8914)

()

‘‘That’s the empty list!’’ the dragon snorted. ‘‘There can’t be an odd number in there, because there’s nothing in there.’’

‘‘Well,’’ said Martin, ‘‘I now know that not one of the numbers in the list the alchemist gave me is odd. They’re all even.’’

‘‘I NEVER said that!!!’’ bellowed the dragon. Martin smelled smoke. ‘‘I only told you about the first number in each list you showed me.’’

‘‘That’s true, Dragon. Shall I write down all of the lists you looked at?’’

‘‘If you wish,’’ the dragon replied. Martin wrote in the dirt:

  (3142 5798 6550 8914)
       (5798 6550 8914)
            (6550 8914)
                 (8914)
                     ()

‘‘Don’t you see?’’ Martin asked. ‘‘By telling me that the first element of each of those lists wasn’t odd, you told me that none of the elements in my original list was odd.’’

‘‘That’s pretty tricky,’’ the dragon said testily. ‘‘It looks liked you’ve discovered recursion. But don’t ask me what that means—you’ll have to figure it out for yourself.’’ And with that it closed its eyes and refused to utter another word.

Recursion, imaginary numbers and C pointers all seem like inflection points where no matter what you do a percentage of your audience is going to fall away.

Recursion is like a slingshot where you pull the rubber band until a certain point and then let go.