Notes on converting recursive code to 'while' loop.

Assume the existence of an object satisfying an "FIterator" interface with hasMore(), getFirst(), and getRest() methods.

Consider a simple function that adds up a list of numbers:

	int addFromIterator(FIterator i){
		if (i.hasMore())
			return i.getFirst() + addFromIterator(i.getRest());
		else
			return 0;
	}

How do we transform this into a 'while' loop?

STEP ONE:  MAKE SURE THERE ARE EXACTLY TWO CASES

While loops only work for recursive functions with exactly two cases. Fortunately, our datatype has exactly two cases.

STEP TWO: MAKE SURE EXACTLY ONE OF THE TWO CASES INVOLVES RECURSION

While loops only work for recursive functions where exactly one of the two branches involves recursion.  Again, we're all right here.

STEP THREE: MOVE THE RECURSIVE CALL TO THE OUTSIDE/END OF THE CLAUSE

That is, the clause that involves recursion must have exactly one recursive call, and it must be at the outside of the clause.  That means the procedure has to look like this:

	int myProcedure(arg ...){
		if (boolean_test) {
			...
			return myProcedure(...);
		}
		else {
			...
		}
	}

...
		<set up iterator i to contain numbers 13,14,16>
		assertEquals(43,addFromIterator(i));
...
	

Does our function look like this?  Not quite.  There's a "i.getFirst + ..." outside of the recursive call.  How can we fix this?

If the recursive call is at the outside of the clause, that must mean that the add-first stuff has to be _inside_ the recursive call somehow.  How can this be?  Well, if it's inside the recursive call, it must be an argument of some kind.

All right, I guess we'd better add an argument to the recursive call.  What should this argument be?  Well <flash of insight!>, what if we keep track of the sum of all numbers we've seen so far?

So now our procedure will begin like this:

	int addFromIterator(FIterator i, int soFar){
		...

This means that we have to change the places where we call addFromIterator.  First, we need to change our test case.  What should the initial value of numbers-so-far be?  How about <flash of insight!> zero?

So our test case becomes:

...
		assertEquals(43,addFromIterator(i,0));
...

and the recursive call?  well, we can write that clause as

...
			return addFromIterator(i.getRest(), soFar + i.getFirst());
...

... well, that looks kind of okay, but all our test cases are failing now!  We need one more change: <flash of insight!> let's replace the non-recursive result 0 with numbers-so-far.

So this is what we've got:

	int addFromIterator(FIterator i, int soFar){
		if (i.hasMore()) {
			return addFromIterator(i.getRest(), soFar + i.getFirst());
		}
		else {
			return soFar;
		}	
	}

The test case succeeds, and we've got step three finished.  Yes, okay, I snuck the curly braces in around the return.

STEP FOUR: GET RID OF ALL THE ARGUMENTS TO THE RECURSIVE CALL

What ?!?

That's right, we need to get rid of _all_ the arguments to the recursive call.  So our procedure must now look like this:

	int myProcedure(){
		if (boolean_test){
			...
			myProcedure();
		}
		else {
			...
		}
	}

But then how can we communicate the new values for the arguments to the recursive computation?

Well, we need to use some kind of non-local communication primitive.  That is, we need to communicate the new values of the recursive arguments to the recursive call.

Fortunately, Java gives us a non-local communication primitive, with the deceptively simple name of "=".  Whenever we use the "=" to change the value of a field or variable from one value to another, we're communicating with all the parts of the program that can see that value.  This kind of communication is hard to reason about, so we must use it sparingly.

With this in mind, let's create two new "boxes" that we can use to communicate the values of these arguments:

...
	FIterator i_box;
	int soFar_box;
...

And now, instead of passing these values to the procedure addFromIterator, we'll stick them in the boxes instead, and change the calls to the procedure to take no arguments.  And to get the arguments, we'll have to look in the boxes.

But be careful!  When we're using communication like this, we need to be careful; if we do the communication in the wrong order, we're in trouble.  For instance, if we update the i_box before the soFar_box, everything breaks.  Try it!  This is what makes programming using "=" so tricky.

...
	FIterator i_box;
	int soFar_box;
	
	int addFromIterator(){
		if (i_box.hasMore()) {
			soFar_box = soFar_box + i_box.getFirst();
			i_box = i_box.getRest();
			return addFromIterator();
		}
		else {
			return soFar_box;
		}	
	}
...

STEP FIVE: TURN IT INTO A WHILE LOOP

Now that we've got a recursive procedure that takes no arguments and has two clauses with exactly one that has recursion and that recursion occurs at the outside/end of the clause, we're ready to transform it into a while loop.

We do this by replacing the function header with the keyword "while", the test moves outward into a special slot after the keyword while, the recursive clause appears after this special slot, and the "else" clause appears after the whole while construct.  Like this

...
	AType AProcName(){
		if (AnExp) {
			ASequenceOfStatements
			return AProcName();
		}
		else {
			AnotherSequenceOfStatements
		}
	}
...
turns into:
...	
	while(AnExp){
		ASequenceOfStatements
	}
	
	AnotherSequenceOfStatements
...

Now, this new thing isn't a free-standing procedure, so we need to put it inside another procedure.  While we're at it, we can turn those "box" variables into arguments to this new procedure too.  Here's the final result:

	int addFromIteratorWhile(FIterator i_box, int soFar_box){
		
		while(i_box.hasMore()){
			soFar_box = soFar_box + i_box.getFirst();
			i_box = i_box.getRest();			
		}
		return soFar_box;
	}

And the test case looks semi-normal again:
...
		assertEquals(43,addFromIterator(i,0));
...

COMPARE THE RESULT.

Just for comparison, let's compare the final result with what we started with.  Here's the first definition of the procedure:

	int addFromIterator(FIterator i){
		if (i.hasMore())
			return i.getFirst() + addFromIterator(i.getRest());
		else
			return 0;
	}

So, how are they different?   Well, the one with the "while" loop is a little longer, but more importantly, it must be very careful about the order in which the two assignments are done.  The really tricky part of all this, though, were those <flash-of-insight>'s that we needed in order to move the recursive call into the right position.

If it's so darn hard, why would we ever convert our recursive procedures into while loops?  The answer, sadly, is that we have no choice.  The designers of Java made a funny decision: recursive procedures, like the one we started with, use up memory in a very wasteful way.  In fact, for a moderately large list of numbers, the recursive procedure will actually cause Java to run out of memory and halt.

Languages like this are called "not tail-calling," or "not tail-recursive".

The transformation we've shown above, turning a recursive procedure into a "while" loop, is a way of showing Java how to run the recursive procedure in less memory.  Java won't do this for us, so we must do it ourselves.

Sorry.


Hope this helps,

John Clements