Understanding Recursion

This quote is from the great book about mathematics, logic and art: Gödel, Escher, Bach: An Eternal Golden Braid.

It’s a very elegant and easy to understand explanation of recursion which is one of the basic building blocks of programming. This explains more how a recursive function will traverse and branch out to different function calls, usually in a recursive function after hanging up on one person, you would return the data you learned from that call to the previous level which is missing in the example.

One of the most common ways in which recursion appears in daily life is when you postpone completing a task in favor of a simpler task, often of the same type. Here is a good example:

An executive has a fancy telephone and receives many calls on it. He is talking to A when B calls. To A he says, “Would you mind holding for a moment?” Of course he doesn’t really care if A minds; he just pushes a button and switches to B. Now C calls. The same deferment happens to B. This could go on indefinitely, but let us not get too bogged down in our enthusiasm. So let’s say the call with C terminates. Then our executive “pops” back up to B, and continues. Meanwhile A is sitting at the other end of the line, drumming his fingernails against some table, and listening to some horrible Muzak piped through the phone lines to placate him … Now the easiest case is if the call with B simply terminates, and the executive returns to A finally. But it could happen that after the conversation with B is resumed, a new caller – D – calls. B is once again pushed onto the stack of waiting callers, and D is taken care of. After D is done, back to B, then back to A.

Hofstadter, Douglas R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Basic Books, 1979.