Ever had a difficulty converting recursive algorithms to non-recursive alternatives? I did, In this blog I will be showing a generalized way of converting (most of the) recursive algorithms to its non-recursive alternatives.

I discovered this technique not so long ago when I stumbled upon one of Tsoding's (Tsoding channel) videos. In this video, Zozen shows how to implement: Inverting a Binary Tree in Rust.

I will be showing solutions in Python (for my convenience) to demonstrate this method.

Idea 1: The CALL Stack

In most programming languages whenever a function is called, all the data required by the function is packed together and "pushed" onto something called - The CALL Stack (more on this here.). Recursive functions rely on this CALL stack to ensure mutual exclusivity of data between separate calls.

Idea 2: The RETURN Stack

The function returns values to the caller by using another stack, called the RETURN stack. Whenever the function execution is complete, it "pushes" the returned value onto the RETURN Stack. Then the caller just has to inspect the RETURN stack for the value.

As most programming languages have a limit on the size of these stacks, recursive solutions often face "Stack Overflow" errors when the recursive calls are too deep.

We can fix this by simply emulating this process by allocating our own stacks onto the HEAP storage.

It will be easier to show this by examples-

Example 1: Tower Of Hanoi

First I will implement tower of hanoi as recursive algorithm-

Code language not defined !

move_disc is just a helper function to format instruction for moving disk from top of frm tower to to tower as string.

Code language not defined !

If you see the recursive implementation, you can observe the following points-

Every recursive algorithm has a base case (in this case n = 0)

Every recursive algorithm make a recursive call to it self with shrinking size of input (it should "approach" the base case in some way)

With the recusive calls to itself, it also does something with the input (in this case printing move_disc(frm, to))

We can generalize these operations as CALL for recursive calls, and HANDLE for doing things with the input.

Following is the general structure of non-recursive alternative-

Code language not defined !

We define two constants CALL as 0 and HANDLE as 1. (they can be any two things, it just has to be different, we could have picked True and False for instance).

Then, we create a call_stack with initial input tagged with CALL value.

Then, we pop elements from call_stack and depending on the action we handle things differently. At the first pop the value of action will definitelty be a CALL

In CALL section, we append furthur actions - CALL and/ or HANDLE depending on the algorithm. CALL for the recursive call, and HANDLE if have to do something with the data (Note that these actions are not yet evaluated yet, we use the call_stack to delay the actions).

Also, we append CALL and/ or HANDLE action in reverse order of recursive solution. (Ponder upon this for a while)

Finally in the HANDLE section we do operations with the data

Non-recursive solution for tower of hanoi-

Code language not defined !

The above algorithm does not depend upon the Programming Language's call stack, hence theoretically is unbounded, and free from Stack Overflow errors.

Example 2: Fibonacci

So far we just printed the data to the console, what if we want to emulate returning values from functions. For that we use return_stack

So, the generalized structure changes a little-

Code language not defined !

We initialize return_stack as empty []

We add data to the return_stack in the CALL section, usually for the base case.

We consume data from return_stack in HANDLE section, and use that data to compute something, and push that something to return_stack for other HANDLE section to use.

At the end we just return the top-most element from the return_stack

Let's use this to solve the fibonacci problem

Recursive Fibonacci Algorithm-

Code language not defined !

Non-recursive Fibonacci Algorithm-

Code language not defined !

That's pretty much it. Let's solve other problems using this technique to solidify our understanding-

Example 3: Inverting a Binary Tree

Types to store binary tree data-

Code language not defined !

Recursive Algorithm-

Code language not defined !

Non-recursive alternative-

Code language not defined !

Example 4: Inorder traversal of tree

Types for Binary Tree data-

Code language not defined !

Recursive Algorithm-

Code language not defined !

Non-recusrive alternative-

Code language not defined !

Conclusion

There are many examples (including above) here.

True, the non-recursive alternative is longer and a little difficult to understand, but it's very easy to produce once you have a recursive solution, and CALL and HANDLE gives us a way to segregate and identify parts of our algorithm.

And with that, I will wrap this up. Thank you if you are still reading. Happy Coding & Keep Learning 😃