Quality of Data

A Helper to run recursive functions iteratively

Last night I wanted to write an iterative binary tree traversal algorithm. I first wrote it recursively, but I struggled to translate it to iterative! I was mentally exhausted. I had only 3 hours of sleep the previous night and I was up for more than 12 hours, so I decided to draw a tree to get some visual help. When I gazed to my tree, I realized nodes are doing marshal art! I eventually couldn’t come up with the right solution after half an hour of trying to convince my brain to get up. This morning when I woke up I thought about the problem again and I solved it in 10 seconds. I am not here to talk to you about how to make the tree traversal iterative, I want to tell you how to make many recursive functions iterative.

I decided to write a helper, such that next time I wanted to convert a recursive function to iterative even if I was sleep, be able do it with closed eyes. Although this helper may not work for all cases it works for many common ones.

Why do we want to make a recursive function iterative?

There are two answers to this question. First answer is simply performance. For simple solutions the iterative functions performs much better than the recursive one due to the overhead of function calls and stack operations. For more complex solutions though, this overhead can become negligible comparing to the actual work done at each recursive step.

Second reason for making a recursive call iterative is to avoid Stack Overflow. I am talking about the exception you get when the function call stack is full, not the website that you can ask programing questions.

I can’t help you with the first problem, but I can help you avoid stack overflow.

How to make it iterative?

There is an straightforward way to translate recursive functions to iterative ones using a stack. Basically by simulating what actually happens at machine level with an object which we call the RecursionHelper.

First divide your recursion code to subrecursive chunks. Generally a recursive function has three parts: Termination condition, recursive calls, and stuff to do on the current object. We have to divide the function into steps. For example consider recursively calculating sum of the items in an array:

int Sum(int index, int[] array)
{
 if (int >= array.Length) return 0;

var sumofrest = Sum(index+1, array);
 return array[index]+sumofrest;
}

Let us divide the above recursive function to its steps:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Now send all this steps to the Recursive Helper:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

First line creates a recursionHelper and passes in the termination condition. Here termination condition is if i>= ar.Length, and if the condition is true function i => 0 will execute and 0 is returned.
The next two lines are definition of the recursive function divided into steps: Recursive call, which calls the function recursively with i+1, and the result comes back as “rv” for the next step. The “Do” steps does some work and returns (or doesn’t return) some result which can be accessible by other parts of the function. In this case our function definition is finished.
The Execute methods starts the recursive call with initial value of 0.

Let us do this with the binary tree in-order traversal problem:

 void PrintTreeNodes(Node node)
 {
 if (node == null) return; //Termination condition
 PrintTreeNodes(node.Left); //Recursive call 1
 Console.WriteLn(node.Value); //Do stuff
 PrintTreeNodes(node.Right); //Recusive call 2
 }
 

With RecursionHelper:

 void PrintTreeNodes(Node root)
 {
 RecursionHelper<Node>.CreateSingular(n => n == null)
 .RecursiveCall((n, rv) => n.Left)
 .Do((n, o) => Console.Write("{0},", n))
 .RecursiveCall((n, o) => n.Right)
 .Execute(root);
 }
 

The first line sets up the termination condition (n==null). It does not return anything because it is a void function. Next three lines call recursive functions and do the job. Eventually execute runs the function with initial value of root.

You see it is pretty easy to convert any recursive function to iterative. You don’t have to change any code. You should only wrap each nonrecursive part in a Do method and change the recursive call with RecursiveCall method.

Here is the code for RecursionHelper<T>:

 public class RecursionHelper<T>
 {
 private readonly List<Tuple<Func<T, T, T>, bool>> _steps = new List<Tuple<Func<T, T, T>, bool>>();
 private readonly Stack<Tuple<T, int>> _stack = new Stack<Tuple<T, int>>();
 private Func<T, bool> _terminationCondition;
 private Func<T, T> _terminationOperation;

/// <summary>
 /// Creates a single stack recursion manager.
 /// </summary>
 /// <typeparam name="TR">Type of item to recurse for</typeparam>
 /// <param name="terminateCondition">The terminate condition.</param>
 /// <param name="terminationOperation">Operation to run in case termination was true.</param>
 /// <returns></returns>
 public static RecursionHelper<T> CreateSingular(Func<T, bool> terminateCondition, Func<T, T> terminationOperation = null)
 {
 var rv = new RecursionHelper<T>
 {
 _terminationCondition = terminateCondition,
 _terminationOperation = terminationOperation
 };
 return rv;
 }

public RecursionHelper<T> RecursiveCall(Func<T, T, T> func)
 {
 addStep(func, true);
 return this;
 }

public RecursionHelper<T> Do(Func<T, T, T> func)
 {
 addStep(func, false);
 return this;
 }

public RecursionHelper<T> Do(Action<T, T> action)
 {
 addStep((i, o) =>
 {
 action(i, o);
 return o;
 }, false);
 return this;
 }

private void addStep(Func<T, T, T> func, bool isRecursive)
 {
 _steps.Add(Tuple.Create(func, isRecursive));
 }

public T Execute(T initialItem)
 {
 var currentItem = initialItem;
 var currentResult = default(T);
 var currentStep = 0;
 while (true)
 {
 var recursiveContinue = false;
 if (currentStep == 0 && _terminationCondition(currentItem))
 {
 currentResult = _terminationOperation(currentItem);
 }
 else
 for (int index = currentStep; index < _steps.Count; index++)
 {
 var step = _steps[index];
 if (step.Item2) //Step is recursive
 {
 _stack.Push(Tuple.Create(currentItem, index + 1)); //Push the current position and value
 currentItem = step.Item1(currentItem, currentResult);
 recursiveContinue = true;
 break;
 }
 currentResult = step.Item1(currentItem, currentResult);
 recursiveContinue = false;
 }
 currentStep = 0;
 if (!recursiveContinue)
 {
 //Once a function has finished it works, pop the stack and continue from where it was before
 if (_stack.Count == 0)
 return currentResult;
 var stackPopped = _stack.Pop();
 currentItem = stackPopped.Item1;
 currentStep = stackPopped.Item2;
 }
 }
 }
 }
}