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 (!tree)
    return 0;
  return 1 + MAX(depth(tree->left), depth(tree->right));
}

STEP ONE:

Refactor your code to meet a few requirements:

1. All variables must be defined, without initialization, at the top of the function
2. Each recursion must be on its own line
3. Use a retval variable

int depth2(node *tree) {
  int retval;
  int l;
  int r;
  if (!tree) {
    retval = 0;
    return retval;
  }
  l = depth(tree->left);
  r = depth(tree->right);
  retval = 1 + (l > r ? l : r);
  return retval;
}

STEP TWO

Create a stack struct and move all variables there. Also include a parent pointer, a resume_point int, a retval, a returned_val and any function parameters. In the function, make a pointer to this stack entry and use the variables from there. Also initialize parent = NULL.

typedef struct depth_stack {
  int l;
  int r;
  node *tree;
  int resume_point;
  struct depth_stack *parent;
  int retval;
  int returned_val;
} depth_stack;

int depth3(node *tree) {
  depth_stack *pStack = malloc(sizeof(depth_stack));
  pStack->parent = NULL;
  pStack->tree = tree;

  if (!pStack->tree) {
    pStack->retval = 0;
    return pStack->retval;
  }
  pStack->l = depth(pStack->tree->left);
  pStack->r = depth(pStack->tree->right);
  pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r);
  return pStack->retval;
}

STEP THREE

Add a new variable tmp_stack for your opening variables, then push that into your stack. Replace each recursion call with code to push on the stack. At the end, include code the returns pops the stack and returns if empty. When pushing and popping, use a unique resume_point and goto (yes, really) to get back to that location.

int depth4(node *tree) {

  depth_stack *tmp_stack = malloc(sizeof(depth_stack));

  tmp_stack->tree = tree;

  depth_stack *pStack = NULL;

push:

  tmp_stack->parent = pStack;

  pStack = tmp_stack;

  if (!pStack->tree) {

    pStack->retval = 0;

    goto pop;

  }

  // Recurse left call

  pStack->resume_point = 1; // will pick up back here

  tmp_stack = malloc(sizeof(depth_stack));

  *tmp_stack = *pStack;

  tmp_stack->tree = pStack->tree->left;

  goto push;

recur1done:

  pStack->l = pStack->returned_val;

  // Recurse right call

  pStack->resume_point = 2; // will pick up back here

  tmp_stack = malloc(sizeof(depth_stack));

  *tmp_stack = *pStack;

  tmp_stack->tree = pStack->tree->right;

  goto push;

recur2done:

  pStack->r = pStack->returned_val;

  pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r);

  goto pop;

pop:

  if (pStack->parent) {

    tmp_stack = pStack;

    pStack = tmp_stack->parent;

    pStack->returned_val = tmp_stack->retval;

    free(tmp_stack);

    if (pStack->resume_point == 1) goto recur1done;

    if (pStack->resume_point == 2) goto recur2done;

  }

  return pStack->retval;

}

CONCLUSION

In step 3 we have implemented a deterministic way to translation a recursive functions to an unrolled one. Therefore, this exact technique applies to every recursive function. Of course in the real world you will probably find a better control flow than goto, but I hope this is a helpful starting point.

Full code Gist.