I’m tired of seeing THIS as an example of recursion for new programmers.

Suppose you’re talking to a 5 year old. Let’s call him Faive.

  • “What’s recursion, Vermie?”
  • “Okay, Faive. What if I told you that if you want to understand recursion, you first need to understand…”
  • “What is it?!”
  • “-recursion!”
  • “That’s dumb.”
  • “Well, recursion requires using itself.”
  • “But then what is recursion?”
  • “Recursion!”
  • “…Oh! I get it! Recursion is when something loops forever! Thanks, Vermie!”
  • …and then Faive walks away. Faive is now misinformed.

We don’t want to give Faive and other people who are new to recursion a wrong impression.

How to understand recursion

There are 3 aspects:

  • Repetition
  • Continuation
  • Iteration vs. Recursion

Repetition

Let’s use an example: grocery shopping.

You want to buy 3 items: milk, bread, and a knife.

You have a simply buy procedure:

define buy = procedure(item):
   go to store;
   buy item;
   return home;

So if you have the 3 items: milk, bread, knife. So you have a list of procedures to do:

buy(milk);
buy(bread);
buy(knife);

Simply put, you have repeated buy over a set of items: milk, bread, knife. Simple. You have performed repetition in buying 3 different items.

Continuation

Suppose you want a way to express a procedure to take a list of items, and then buy them. Then you might say:

define shopping = procedure(items):
   for each (i) in (items):
       buy(i);

When you would carry out this computation, it might look something like this:

shopping({milk, bread, knife})

which would turn into:

for each (i) in ({milk, bread, knife}):
   buy(i);

and then:

buy(milk); then
buy(bread); then
buy(knife);

At each step, there is a next step: then: buy(next_item). This is what you call a continuation of a current step in a procedure: the next procedure after you’re done with stuff in the current procedure, as well as the context you’re going to do it in (e.g. after I’ve done buy(milk)

Usually, continuations are handled automatically or “invisibly” by higher-level control features. However, iteration and recursion both use them differently.

Iteration vs. Recursion

There are two primary ways of expressing repetition: iteration and recursion. I also like to call them explicit and implicit repetition (or looping).

Iteration

Iteration tells you:

  • What to start with
  • When to end
  • How to go to the next element from the start

For example, in C, there exists a for loop construct that expresses these three steps explicitly. Here is “semi-C” pseudocode:

for (
   start: item i = first_of(items); // start condition
   end: i is at END of (items);     // end condition
   next: i becomes the next item;   // next step setup
) {
   do something;
}

If we apply this to shopping({milk, bread, knife}), and expand the list of steps, this will become:

start: item i = milk;
buy(milk);
next: i = bread;
buy(bread);
next: i = knife;
buy(knife);
next: i = END;
stop: because end condition met;

Notice: there are “helper” steps to help define the repetition and the flow of execution. You can see that the list of steps is done for each item, and has clear boundaries for the start and end of the procedure.

The pattern of repetition is uniform and set:

  • Before each valid iteration, the end condition must not be met
  • The current list of iteration steps are done
  • The next action to get the next item to be done is performed

Recursion

Recursion gives you:

  • A rule: if some condition, then do something and then perform the continuation.
  • Other rules in terms of a rule.

Recursion’s repetition is implicit because some rules may lead back into the greater list of rules as a part of its flow of execution. Thus, recursion(x) may often make use of some other case of recursion(y).

In a way, recursion abuse that that the continuation of a procedure can be itself, making termination entirely dependent on whether:

  • There exists a rule to stop the computation
  • Whether other rules will always lead to a rule that stops the computation.

For example, in Scheme (Lisp), it is common to see recursion as a pattern. Here is some pseudocode for recursion:

recursion(x):
   if (condition1(x)) { then do something; then stop; }
   if (condition2(x)) { then recursion(x); }

Recursion does not give a special place to mark a start condition or a stop condition. It simply consists of a list of rules to decide what to do next. In other words, a recursive procedure defines what to do, and then what should be the continuation.

So, if shopping({milk, bread, knife}) were written in a recursive fashion:

define shopping(items):
   if (first(items) != END) {
       then buy(first(items));
       then continue with: shopping(rest(items))
   }
   if (first(items) == END) {
       then stop: because end condition met;
   }

Notice that there are two helper functions: first and rest. Here, we can think of items as an ordered list instead of just an unordered set of items. We take a look at the front of the list, perform an action, and then either continue to the next item or stop if there is no more items.

Why recursion can be harder and easier

Recursion can be harder because:

  • It requires the designer to understand whether they have covered all the cases
  • It is possible to make the control flow such that the recursion never ends.
  • Identifying the start and end conditions and how to phrase them can be harder.
  • Certain patterns of recursion can be harder to recognize and optimize.

Recursion can be easier because:

  • Recursion is suited for recursive data structures (such as trees and graphs)
  • Expressing some algorithms that are rule-driven are easier
  • It’s harder to get confused if you focus on simple rules to drive continuations versus creating a larger iterative piece of code that must keep track of many different intermediate variables.

Why iteration can be easier and harder

Iteration can be easier because:

  • People are sometime more naturally suited to think in a step-by-step manner.
  • It’s often easier to figure out the start, end, and continuation parts of the procedure.
  • There is often less need to repetitively go back through the list of rules when analyzing recursion

Iteration can be harder because:

  • Algorithms that are written step by step are often longer, and thus, probably take longer to read and analyze
  • Turning a recursive data structure into a view that can be used with iteration might take some extra work
  • Refactoring iterative code to handle additional cases may be bulky or burdensome, depending on language.

And so I hope this helps people explain recursion!

Advertisements