Recursion Removal

As we have seen, recursion is very useful for problems of a recursive nature and all programming languages accept recursive algorithm but this was not always true and programmers needed to remove recursion when implementing their algorithms. We will see how to do this, not in case we need to deal with an old programming language but because to fully understand recursion we need to understand how to get rid of it!

General algorithm to remove recursion:

Let's say that a method "A" calls a method "B" and "B" calls a method "C". We can think this is being executed as follows:
"A" starts running, when the call to "B" is reached, "A" waits while "B" is running and when inside "B" the call to "C" is reached "B" waits for "C" to finish. As soon as "C" is done, "B" resumes and as soon as "B" is done "A" will resume. So how is this done? I mean, how is this managed at low level?
It's important to note that the last method to be called is the first to finish and vice versa: the first method to start running, end last. "Last in, First out"! In this case "A" starts first and finishes last. "C" starts last and finishes first. This is the nature of a stack data type! When the call to "B" is reached, "A" state is pushed into a stack, when the call to "C" is reached, "B" state is pushed into the stack. When "C" finishes, a pop operation on the stack will restore "B" execution and so on when "B" finishes a pop operation will restore "A" execution. Of course, this can be done with many levels as stack capacity we have, not only three!
In the case of recursion the same thing is going on, we can think of is as a special case where "A", "B" and "C" are just the same method! So to implement recursion, all we need is a Stack! That stupid data type that seems to be so useless turned out to by quite powerful and useful, since is just what we needed!

Let's go back to our Hanoi example:

hanoi(disks, ini, temp, end){

	//Base case check
	if (disks > 0) {

		hanoi(disks - 1, ini, end, temp);

		print("Move disk: " + disks + " from " + ini + " to " + end + ".");        

		hanoi(disks - 1, temp, ini, end);
	}

}
Before we start, let me warn you that this is not an easy thing to do, so don't get upset if you find it hard!

Let's try to write it using a stack, we are going to need goto statements. Oops, we usually try to avoid them because they make our code hard to read or follow but this time the benefit is big and we are willing to pay the price! Oops but we don't have them in Java! Once again good programmers like us are limited by a language thought from a commercial point of view where is acceptable to add constraints in order to keep the language able to be used by dummies! Let me mention here something that Bjarne Stroustrup said and I think it applies to this case:
"The connection between the language in which we think/program and the problems and solutions we can imagine is very close. For this reason, restricting language features with the intent of eliminating programmer errors is at best dangerous. As with natural languages, there are great benefits from being at least bilingual. A language provides a programmer with a set of conceptual tools; if these are inadequate for a task, they will simply be ignored. Good design and the absence of errors cannot be guaranteed merely by the presence or the absence of specific language features."
Anyway since as we always do with hard problems, we will start with seudocode where gotos are allowed! Later we will simulate the gotos with a switch construction. The only problem will be that in this case the resulting code without gotos end up to be uglier than the gotos version!

Let's put a mark or label to the first instruction of our recursive algorithm. Why? Because every time a recursive call is made, we need to simulate that we start again from the beginning (We all agree that when a method is called, it will start from the beginning).
Okay, let's now continue writing our code as it's in the recursive version until we hit a recursive call! What should we do now? Kernel Panic... We are about to be postponed, we are about to be pushed into the stack. So let's push the current state (skip global variables, if any) and also let's consider some return address as part of the state to be pushed. This is, we need to know from where to resume when the time comes! And we need to resume exactly from the next instruction after the recursive call, so we create another label to the next instruction (if there is no next instruction, we are in a returning point (also we can take advantage of this, we will see how later)). One more important detail: between the push and the next instruction we need to change the state to be the one as it is in the recursive call, since we start from the beginning with the new values:
disk= disk-1;
ini= ini; (no change here)
temp and end values swapped.
We now continue this way until we reach a return statement or the end of the recursive version which ,off course, is a implicit return statement. At this point we close the open brace and continue with what was left in the stack! So if the stack is empty is time to finish our execution (we return) otherwise we pop from the stack, we restore the state and we go to given return address. That's it! We are done!!

We will end up with something like this:

hanoi(disks, ini, temp, end) {


Ini: // Marks the start of the recursive version

	if(disks > 0) {

		// save the current state:
		state= new State(disk, ini, temp, end, FirstCall);
		push(state);

		// set the state to be as in the recursive call:
		disk--;
		swap(end, temp);
		
		// go to the beginning:
		goto Ini;

FirstCall: // Marks the returning point from the first recursive call.

		print("Move disk: " + disks + " from " + ini + " to " + end + ".");        

		// save the current state:
		state= new State(disk, ini, temp, end, SecondCall);
		push(state);

		// set the state to be as in the recursive call:
		disk--;
		swap(ini, temp);
		
		// go to the beginning:
		goto Ini;

	}

SecondCall: // Marks the returning point from the second recursive call.

	if(stack is empty) {
		return;
	}

	state= pop();

	disk= state.disk;
	ini= state.ini;
	temp= state.temp;
	end= state.end;

	goto state.returnAddress;

}

This algorithm to translate recursive algorithms to "iterative" algorithms is quite general and can be applied to a big range of recursive algorithms.
But what about Global variables? Well, as I said before, just don't save them in the stack!
But what about Indirect Recursion? Well, all we have to do is to "merge" all the algorithms in just one direct recursive algorithm.
But what about a recursive algorithm that returns a value? Well, all we have to do is to adapt our recursive algorithm to use a global variable instead.

To implement our code in Java we still need to find a way to simulate the gotos. We can do it with a while and a switch as shown below:

package recursionremoval;

import java.util.Stack;

/**
 * Recursion removal of The Towers of Hanoi problem.
 *
 * @author Kriche
 *
 */
public class Main {

    public static void main(String[] args) {

        System.out.println("ITERATIVE Hanoi's Version!!!!\nKreache 2008:");

        if (args.length != 4) {
            System.out.println("Expecting \"disks ini temp end\" arguments!");
            return;
        }

        int disks;
        try {
            disks = Integer.parseInt(args[0]);
        } catch (NumberFormatException nfe) {
            System.out.println("disk must be a possitive integer or zero!");
            return;
        }

        if (disks < 0) {
            System.out.println("disk must be equal to or bigger than zero!");
            return;
        }

        hanoi(disks, args[1], args[2], args[3]);

    }

    /**
     * 
     * @param disks
     * @param ini
     * @param temp
     * @param end
     */
    private static void hanoi(int disks, String ini, String temp, String end) {

        Stack stack = new Stack();
        String auxi;

        ReturnAddress returnAddress = ReturnAddress.BEGINNING;

        while (true) {

            switch (returnAddress) {

                case BEGINNING: // Marks the start of the recursive version

                    if (disks > 0) {

                        stack.push(new Frame(disks, ini, temp, end, ReturnAddress.FIRST_CALL));

                        disks--;
                        auxi = temp;
                        temp = end;
                        end = auxi;

                        returnAddress = ReturnAddress.BEGINNING;

                    } else {
                        returnAddress = ReturnAddress.SECOND_CALL;
                    }

                    break;

                case FIRST_CALL: // Marks the returning point from the first recursive call

                    System.out.println("Move disk: " + disks + " from " + ini + " to " + end + ".");

                    stack.push(new Frame(disks, ini, temp, end, ReturnAddress.SECOND_CALL));

                    disks--;
                    auxi = temp;
                    temp = ini;
                    ini = auxi;

                    returnAddress = ReturnAddress.BEGINNING;

                    break;

                case SECOND_CALL: // Marks the returning point from the second recursive call

                    if (!stack.isEmpty()) {
                        Frame frame = stack.pop();
                        disks = frame.n;
                        ini = frame.ini;
                        temp = frame.temp;
                        end = frame.finish;
                        returnAddress = frame.returnAddress;
                    } else {
                        return;
                    }

                    break;

            }
        }

    }
}

enum ReturnAddress {

    BEGINNING, FIRST_CALL, SECOND_CALL
}

class Frame {

    public int n;
    public String ini, temp, finish;
    public ReturnAddress returnAddress;

    public Frame(int n, String ini, String temp, String finish,
            ReturnAddress returnAddress) {

        this.n = n;
        this.ini = ini;
        this.temp = temp;
        this.finish = finish;
        this.returnAddress = returnAddress;
    }
    
}

This code looks not as natural as the recursive solution and hard to understand! But it's the result of mechanically applying an algorithm to translate recursive algorithms in nonrecursive ones!

Tail recursion

We have done a lot of progress but still much more can be done! Let's look at the recursive version again: What about the last recursive call? When translating to nonrecursive, do we need to push a state that it will not be used?
Let's see: as far as we return from the second recursive call the algorithm does nothing and finish, this is, it returns to it caller. So we can do the same, but it's important to note that we still need to change the state to be as defined in the second recursive call and the "if" statement of the base condition will be transformed into a "while":
/**
 * 
 * @param disks
 * @param ini
 * @param temp
 * @param end
 */
static void hanoi(int disks, String ini, String temp, String end) {

    String auxi;

    while(disks>0){

        hanoi(disks-1, ini, end, temp);

        System.out.println("Move disk: " + disks + " from " + ini + " to " + end + ".");

        disks--;
        auxi = temp;
        temp = ini;
        ini = auxi;

    }

}

Now, we can remove recursion and since there is only one recursive call we don't need to save in the stack the returning address:

hanoi(disks, ini, temp, end) {

	BEGINNING:

	while(disks>0){

		// save the current state:
		state= new State(disks, ini, temp, end);
		push(state);

		// set the state to be as in the recursive call:
		disks--;
		swap(end, temp);
		
		goto BEGINNING;

		RETURN_POINT_FROM_RECURSIVE_CALL:

		print("Move disk: " + disks + " from " + ini + " to " + end + ".");

		disks--;
		swap(ini, temp);

	}

	if( stack.isEmpty()){
		return;
	}

	state= pop();
	ini= state.ini;
	temp= state.temp;
	end= state.end;

	goto RETURN_POINT_FROM_RECURSIVE_CALL;

}

This code can still be improved to remove the goto statement!
And there a still much better solutions to the hanoi towers that don't need a stack at all, there are math properties that can be used.
Later I will add some of them here!