## How to run most of the recursive functions iteratively!

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.

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)
{
return this;
}

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

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

private void addStep(Func<T, T, T> func, bool 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;
}
}
}
}
}

```

### 5 Responses to “How to run most of the recursive functions iteratively!”

1. Rich Says:

This is a great article. Do you think you could come up with a couple examples where this approach would not work, or when this approach might actually have worse performance than recursion? That might help readers (like me) to have a better idea of when and when not to use this type of helper. Thanks again for a very useful and informative article!!

2. […] for C# there is a little helper method here that turns your recursive function to iterative without requiring to change logic or make the code […]

3. […] for C# there is a little helper method here that turns your recursive function to iterative without requiring to change logic or make the code […]

4. WhyProgrammersSuckAtProgramming Says:

This really didn’t help at all.

You could at least provide a working example. You don’t even include the proper namespaces (using System, Linq, etc.)

Tuple also isn’t in pre-v4 framework, which is worth mentioning: http://stackoverflow.com/questions/4312218/error-with-tuple-in-c-sharp-2008

No explanation as to what the variables are you use (ex. “rv”).

Programmers who can understand this won’t need to know it. Those who don’t understand this because it’s so poorly explained, can’t use this. That leaves a very small niche of people who don’t yet know enough to do this themselves, but know exactly enough to understand everything here with little explanation.

This is a big reason why so many resources online are useless. Such poorly explained blogs which make them next to useless to all but those who don’t need to know this because they can solve the problem themselves in other ways they were already taught.

• WhyProgrammersSuckAtProgramming Says:

To be more specific: It is always good practice when explaining things to others, to stray from assuming they were taught programming from the same school of thought or same university as you. Many people are self-taught, and these abstract ideas are very hard for humans to understand. Using a style of coding that only other professionally taught programmers know does nothing to help others- especially the novice. Hell, there isn’t even a preface as to what you may need to know to use this helper class. It just assumes you can figure it out from the example. By that point- you could just do this yourself.

I hope I made myself clear enough in explaining this. I want the internet to be a better resource for users so we may all become better educated and program better.