# 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:

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

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;

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.

Subscribe to:
Post Comments
(
Atom
)

## No comments :

Post a Comment