Transforming recursion to iteration via coroutines

This blog post is adapted from my book The Tcl Programming Language.

Many programming tasks are very simply expressed and implemented through recursive algorithms, traversing a tree data structure being just one example. The primary reason recursion simplifies implementation is that the state of the computation is implicitly maintained, freeing the programmer from the burden of explicitly tracking the computational state of the program. For example, in a recursive tree walking implementation, the "current location" in the tree is implicitly tracked.

However, there are situations where a recursive model does not fit the needs of an application. For example, the application may want to traverse a tree in iterative fashion, retrieving one node at a time, operating on it and then potentially doing some unrelated computation before retrieving the next node at some unknown point in the future.

Here is where coroutines can bridge the impedance mismatch, presenting an iterative interface to a naturally recursive algorithm.