unroll-recursion.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
  int value;
  struct node *left;
  struct node *right;
} node;

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

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;
}

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;
}

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;
}

int main()
{
  node *myTree = calloc(1, sizeof(*myTree));
  for (int i = 1; i < 150; ++i) {
    node *newTree = calloc(1, sizeof(*newTree));
    newTree->left = myTree;
    myTree = newTree;
  }
  printf("%d\n", depth(myTree));
  printf("%d\n", depth2(myTree));
  printf("%d\n", depth3(myTree));
  printf("%d\n", depth4(myTree));

  return 0;
}