Showing posts from October, 2015

Generic process to unroll any recursive algorithm

In computer programming, you run into recursive algorithms when dealing with a problem that exhibits similar substructure. Recursion will apply the exact algorithm to a subset of the problem and then combine the result in some way with the remainder of the problem. Using recursion can be very readable and elegant. You are not likely to come across a contrived usage of a recursive algorithm.

Recursion uses a finite resource, stack space, and requires an assumption that the algorithm -- with expected inputs -- will not exhaust this resource. If this assumptions fails, then you will need to "unroll" the algorithm to make it not recursive, or reconsider your approach altogether. It is always possible to rewrite a recursive algorithm as unrolled.

Here I will demonstrate a generic way to unroll any recursive algorithm. Of course, for your specific algorithm, you can surely do better.

Our example is finding tree depth, from Eric Lippert at Microsoft:

int depth(node *tree) {
  if (!tr…