Recursion

Imagine you want to watch a sorting algorithm work instead of only reading its output. A list of colors arrives in a random order, and over several seconds you see the colors move into place one step at a time. Each change on screen corresponds to a real step inside the algorithm. This article is about that situation: an animation that shows a recursive algorithm while it runs.

Keep one question in mind as you read. The algorithm is recursive, so it calls itself repeatedly, and the screen must be refreshed many times during that process. Where should the code that updates the screen live, and what work does the thread have to do to keep the algorithm and the display moving together? The rest of this article works toward answering that question, and then turns to a second kind of recursion that appears when you read grammar rules.

A recursive algorithm solves a problem by having a method call itself on smaller pieces of the problem. The call stack grows and shrinks as the work proceeds, and the order of steps is determined by those nested calls. In the animation case, the program is sorting an array of colors with a recursive QuickSort, and the goal is to arrange the colors into a standard spectrum running from red to violet. The colors begin in a randomized order.

The reason to use a separate thread is that the recursive work gets its own flow of control. The thread can carry the entire recursion from start to finish while the rest of the program keeps responding. Each time the algorithm reaches a point where something visible has changed, the program can update the display. Because the recursion runs in the thread, these redraws happen as part of the sorting process rather than on a separate schedule that must somehow keep up with it.

In words, the diagram says this: once the user starts the sort, the thread takes over and runs a recursive QuickSort. Each pass through the recursion can change the arrangement of colors, and the display is refreshed as those changes happen. The arrow from the thread back to itself stands for the recursion continuing. The diagram is a simplified picture of the control flow and does not show every internal call that QuickSort makes. The Start button becomes a Finish button during the sort, which lets the user abort before the sort finishes on its own.

A tempting alternative is to drive the animation with a timer that fires at regular intervals. Each tick would advance the algorithm by one step and then redraw. The difficulty is that a recursive algorithm is not organized as a list of separate, equally sized steps waiting to be taken one at a time. Its natural structure is a single method that keeps calling itself until the job is done.

To see why, consider what a timer tick would have to do. The recursion is in the middle of nested calls, each waiting on the ones inside it. To resume after a tick, the program would need to know exactly where it was in that nested structure and what work remained pending. Forcing the recursion into fixed timer steps means splitting one connected process into many disconnected pieces, and the pieces have to be reassembled correctly each time. A single recursive call inside a thread avoids this, because the recursion keeps its own place in its flow of control while the thread runs.

The second half of this article moves from algorithms to grammars. Consider a short question: how would you tell a computer which word sequences count as well-formed English sentences? You cannot list every sentence, because there are infinitely many. Backus-Naur Form, usually called BNF, answers this with a small set of rules. Each rule describes one kind of phrase in terms of other kinds of phrase, and some rules end up describing themselves.

The word 'can be' is chosen deliberately. A symbol may have several rules, each giving one possible form, so a rule describes an option rather than a single fixed shape. The next rule shows the idea in a form you can read directly. A noun-phrase can be a common-noun, optionally followed by the literal word 'that' and a verb-phrase. Alternatively, it can be a common-noun followed by zero or more prepositional-phrases.

The rule can also be read as a recipe. To produce a noun-phrase by this alternative, produce a common-noun, then the literal word 'that', then produce a verb-phrase after it. The rule does not say how to produce a common-noun or a verb-phrase. Those symbols must be defined by other BNF rules, so a grammar is a collection of rules that refer to one another until every symbol has a definition.

A rule is recursive when it defines a symbol partly in terms of the same symbol, either directly or through other rules. Rules like the noun-phrase rule can describe quite complicated structures, but the more important feature is that a rule may refer back to a symbol it helped define. Recursion lets a small grammar describe phrases of unlimited depth. The two forms of recursion differ in how many rules the loop passes through.

Recursion becomes concrete when you build a phrase step by step. Start with a noun-phrase that is a common-noun followed by 'that' and a verb-phrase. The verb-phrase can be 'ate the cheese', which gives the noun-phrase 'the rat that ate the cheese'. Now the loop can be used again. Put that whole noun-phrase inside a verb-phrase, and place that verb-phrase after a common-noun. The result is a larger noun-phrase.

Tracing works in the other direction too. To debug a failing derivation, trace from the outside in and identify the first rule where the expected word does not match. Consider the generated phrase 'the cat that caught the rat which ate the cheese'. The outer noun-phrase matches 'the cat that', and the verb-phrase begins with 'caught'. The verb-phrase then needs a noun-phrase, which begins with the common-noun 'rat'. The rule expects the literal 'that' next, but the input has 'which'. The first mismatch is therefore inside the inner noun-phrase rule, at the literal 'that'.

The tree shows the failure clearly. The derivation matched every part it could, from the outside in, and stopped at the literal 'that' inside the noun-phrase rule for 'rat'. That is the rule where the derivation fails to match the input. The fix is not to change the outer rules, which matched correctly, but to recognize that the phrase uses a different word than the grammar allows at that point.