�
Abstract: A method of building recursive functions in systems that don't have a data stack is presented. We illustrate its use with a factorial function, the towers of hanoi puzzle and a recursive line drawing routine which we believe is presented here for the first time. We reduce beautiful recursive code to unintelligible spaghetti code that uses less memory and sometimes is faster. This method may speed up simple functions but mostly it helps us to understand the nature of recursion and provides a method of deriving code. We also present a method that uses no return stack or data stack and we derive a simple line drawing function using the information presented herein. All of the code presented here is available by anonymous ftp from olympus.net in pub/sites/7seas under the name recurse.cpp .
Introduction: In the mid seventies I was working on the MicroData Reality computer and operating system. This sported what would now be considered a primitive BASIC, but at that time was relatively sophisticated. It was a compiled BASIC and like many BASICs both then and now, it did not support recursive function calls. In that system it was possible for a routine to call itself but all variables passed were global because there was no data stack in the system.
I mentioned casually to a fellow system analyst that it was easy to write a factorial routine recursively on the system without emulating a data stack. He expressed doubt that this was possible. I won a fifty cent bet with the following routine. The following routine does depend on there being a return stack in the system. Since assembly language systems provide return stacks, this kind of routine works well in assembly language. The following routine is written in C code with C++ comments. We do not pass a parameter to the factorial routine, we set the parameter x as a global value. We then call factorial() to calculate x factorial.
/* STACKLESS FACTORIAL */
int x; . . //Set x to the value you wish to find the factorial of. . int factorial() //Pass x as Global No data Stack { int prod; x = x-1; //A function if(x+1 < = 0) prod = 1; else prod = (x+1) * factorial(); //The recursive call x = x+1; //A function inverse return prod; }
Generalization: We can generalize this technique and apply it to other recursive functions.
Note that we have commented the lines x+1 and x-1 as "A function" and "A function inverse" . Using functions and there inverses is a key to doing this kind of recursion. Note that the sequence of statements x = x-1 and x = x+1 executed in that order leave the value of x unchanged. The function i(x) = x+1 is the inverse of the function f(x) = x-1 . This is the key to data stackless recursion and is helpful in understanding regular recursion as well. The purpose of a stack in recursion is to create an inverse for any function by keying in time and space. If we have a function that is naturally invertible, that is if f() is a function and there exists a function i() that is its inverse, ( for all x, i(f(x)) = x ) and this function is used to alter the value of a passed variable in a recursive call, we can use the function and its inverse instead of a data stack. For example: given a f() and its inverse i() we can generate a sequence of x's . x1 = f(x), x2 = f(x1), x3 = f(x2) etc. We can either go backwards or forwards through the xi's . in other words x2 = i(x3), x1 = i(i(x3)), x = i(i(i(x3))) etc. We use this fact to generate a virtual data stack to recover old values as we exit each recursion level.
If a recursive routine of a single variable is of the following form where f() is an invertible function with the inverse i() over the range of x , then it can be translated into a stack free recursive function.
/*** THIS FORM OF ROUTINE CAN BE CHANGED TO STACK FREE RECURSION ***/
/* line 1 */ function stackfree(x)
/* line 2 */ {
/* line 3 */ .
/* line 4 */ . //Anything goes here (except x = ...)
/* line 5 */ .
/* line 6 */ .... stackfree(f(x)) // An expression containing a recursive call.
/* line 7 */ .
/* line 8 */ . //Anything here also
/* line 9 */ .
/* line 10 */ return somevalue;
/* line 11 */ }
Do the following:
Now the routine above becomes:
/* line 1 */ function stackfree()
/* line 2 */ {
/* line 3 */ .
/* line 4 */ . //Anything goes here
/* line 5 */ .
/* line 6 */ x = f(x);
/* line 7 (was line 6) */ .... stackfree() // An expression containing a recursive call
/* line 8 */ x = i(x)
/* line 9 */ .
/* line 10 */ . //Anything here also
/* line 11 */ return somevalue;
/* line 12 */ }
Example: Convert the following routine for factorial x .
int factorial(x)
{
int prod;
if(x <= 0) prod = 1;
else prod = x * factorial( x-1 );
return prod;
}
The new routine is then:
int x;
.
. //Set x to the value you wish to find the factorial of.
.
int factorial() //Pass x as Global No data Stack
{
int prod;
x = x-1; //A function
if(x+1 < = 0) prod = 1; //The statement here is two lines long
else prod = (x+1) * factorial(); //The recursive call
x = x+1; //A function inverse
return prod;
}
It is easy to generalize this to functions of several variables. In this case every variable passed in the recursive call must have a unique inverse. As is traditional, "this is left as an exercise for the reader." This is supposed to be a short article and we want to cover three more subjects. First, we want to show how to completely corrupt a beautiful recursive routine and make it into spaghetti code that uses NO stack, either data or return. Second, We wish to apply this technique to the "Towers of Hanoi" puzzle. Third we wish to give an example of the derivation of a fast line drawing routine using these techniques.
In the simple factorial routine given above, the only purpose of the return stack is to keep track of the number of times we have entered and exited the recursion. We could use a variable to count our level of recursion, but all we really need is an indication of when we get back to the outermost level. In this case we can simply save the value of x itself and use it to detect when we are through with the recursion.
The following is the routine rewritten using goto's and using no stacks!
int factorial(x) // This entry is used once. It is not a recursive entry.
{ // Note that within this routine we treat x as a global.
int prod; // Same as in routine above
int ox = x; // Original x
recursive_entry: //A label we will return too
x = x-1; //A function as above
if( x < =0 ){ prod = 1; }
else { goto recursive_entry; return_entry: prod = (x+1) * prod; }
x = x+1; //Inverse
if( x != ox ) goto return_entry;
return prod;
}
Simply by looking we can see ways to optimize this routine. We get the following which is surprisingly short and efficient. It is not quite as good as a factorial routine done with a simple loop because we have to decrement x all the way to zero before we can start doing the multiplies, but it was derived from a true recursive routine through a series of simple reductions. The code is not obvious. Would you like to see it on a test with the question "What does this code do?".
int factorial(x) //Not recursive entry
{
int prod;
int ox = x;
recursive_entry: //Recursive entry
x = x--;
if( x<=0 ){ prod = 1; x++; }
else { goto recursive_entry; return_entry: prod = (x++) * prod; }
if( x != ox ) goto return_entry;
return prod;
}
To give an idea of the elegant solutions available with this approach consider the famous "Towers of Hanoi" puzzle. Briefly stated, there are three posts. There is a group of disks. Each disk has a hole in it so that it can be put over a post. All of the disks are of different sizes. No two disks are the same size. In the beginning of the game the disks are arranged in a pyramid on one of the posts so that the smaller disks only rest on larger ones. The problem is to move the disks one at a time from post to post until all the disks have been moved to a new post, but with the constraint that it is never a legal move to put a larger disk on a smaller one. The game is very old an steeped in lore. Tradition has it that in one of the continuing simulations of Armageddon at the pentagon, an algorithm similar to the one presented below is used to determine the exact time of the explosion that ends it all.
There is an elegant recursive way to define a function that will solve this problem. In natural language the solution might be stated as follows. There are three towers: tower one, tower two and tower three. Seven disks are on tower one. If we know how to solve the problem of moving 6 disks from tower one to tower three, then we can solve the problem of moving seven disks from tower one to tower two. First we move the six disks from tower one to tower three. We take the remaining largest disk and move it from tower one to tower two. Now if we can move six disks from tower one to tower three, we can use the same algorithm to move the six disks from tower three to tower two. We have reduced the problem of moving seven disks to one of moving six disks. Similarly we can reduce the problem of moving six disks to moving five disks. We continue in this way until we reduce the problem of moving two disks to that of moving one disk. Moving one disk is trivial. Footnote:
We can now move any number of disks, it merely becomes a matter of bookkeeping. Computers are notoriously good at bookkeeping so here is some C++ code for the towers of Hanoi.
void Hanoi(int Number_of_Disks, char * fromTower, char * toTower, char * otherTower)
{
if( Number_of_Disks > 0 )
{
Hanoi( Number_of_Disks-1, fromTower, otherTower, toTower);
cout < < " MOVE 1 disk from " < < fromTower < < " TO " < < toTower;
Hanoi( Number_of_Disks-1, otherTower, toTower, fromTower);
}
}
We invoke this function Hanoi(7,"Tower 1","Tower 2","Tower 3") and it prints out the instructions for moving seven disks from Tower 1 , to Tower 2 .
Not satisfied with this elegant recursive code, we decide to write this routine without using the data stack.
First eliminate the Number_of_Disks variable:
int Number_of_Disks; //Now a global value!!
.
.
.
void Hanoi(char * fromTower, char * toTower, char * otherTower)
{
if( Number_of_Disks > 0 )
{
Number_of_Disks = Number_of_Disks-1;
Hanoi(fromTower, otherTower, toTower);
cout < < " MOVE 1 disk from " < < fromTower < < " TO " < < toTower;
Hanoi(otherTower, toTower, fromTower);
Number_of_Disks = Number_of_Disks+1;
}
}
Then eliminate the other variables, notice that the function simply exchanges pointers to strings. The inverse is simply exchanging them back. We use a temporary variable to do this.
int Number_of_Disks; //Now a global value!!
char * fromTower, toTower, otherTower;
.
.
.
void Hanoi()
{
char * TEMP;
if( Number_of_Disks > 0 )
{
Number_of_Disks = Number_of_Disks-1;
TEMP = otherTower; //These three lines are there own inverse
otherTower = toTower;
toTower = TEMP;
Hanoi();
TEMP = otherTower; //See above
otherTower = toTower;
toTower = TEMP;
cout < < " MOVE 1 disk from " < < fromTower < < " TO " < < toTower;
TEMP = otherTower;
otherTower = fromTower;
fromTower = TEMP;
Hanoi();
TEMP = otherTower;
otherTower = fromTower;
fromTower = TEMP;
Number_of_Disks = Number_of_Disks+1;
}
}
We have succeeded in reducing elegant recursive code to a combination of spaghetti and recursion. We have succeeded in making this code non-data stack dependant and thereby reduced the space needed in the system. This code can be further reduced but we will not do so in this paper.
Let us derive a line drawing routine using these techniques. To simplify the problem let us assume we are starting at pixel (0,0) and drawing to some point (x,y) where x and y are both positive integers. A line is then a set of connected points (either adjacent or on a diagonal) that connects (0,0) and (x,y) . We will assume that (0,0) and (x,y) will both be included in the set of points in the line. The technique we will use I have never seen anywhere else. It is NOT a recommended technique for most applications, although it is fast. The lines do not meet some of the most obvious criteria for good lines but they appear relatively straight for most applications. They were used in an early 7Seas software product and no one ever complained or pointed out they were not generated with Bresenhams algorithm which for many applications is more suitable.
The technique is recursive and simple. We invoke the line draw routine with two points (a,b) and (c,d) . We guarantee that a < c and b < d . Our first invocation is with a = 0, b = 0, c = x and d = y . Line_Draw(0,0,x,y) is how we invoke the function.
Then the algorithm for Line_Draw(a,b,c,d) is:
if( a==c && b==d ){ color(a,b); return; }
w = a+c > > 1 x = b+d > > 1 y = a+c+1 > > 1 z = b+d+1 > > 1
Line_Draw(a,b,c,d)
{
if( (a==c ) && ( b==d ) )
{
color(a,b);
}
else
{
Line_Draw( a, b, a+c > > 1, b+d > > 1);
Line_Draw(a+c+1 > > 1, b+d+1 > > 1, c, d );
}
return;
}
If we wish to eliminate the data stack we need to find an inverse for a+c > > 1, b+d > > 1, a+c+1 > > 1 and b+d+1 > > 1 . The problem is that these functions do not have an inverse. In order to find an inverse we will cheat and introduce our own data stack that is one bit wide and quite short. One 32 bit unsigned integer provides enough room for a screen that is 64K by 64K pixels. Here is a code fragment and its inverse used to implement a+c > > 1 and its inverse.
/* Code Fragment */ c = a+c stack = stack < < 1; //Times 2 if( c & 1 ) stack = stack + 1; //Check least significant bit c = c > > 1; //Divide by 2 /* Code Fragment Inverse */ c = c < < 1; //Times by 2 if( stack & 1 ) c = c + 1 stack = stack > > 1; //Divide by 2 c = c - a
In order to make this easier to read, we will do our shifts using a function and its inverse called SR(x) and SL(x) . We could put all of the functions and inverses inline, but the code would not be as readable. Although we do make calls to SR() and SL() with arguments none of the functions needs to be recursive. The complete implementation is then:
unsigned long stack; //These are all global values
int a, b, c, d;
.
.
. //Set initial values of a, b, c, d here.
.
.
int SR(X)
{
stack = stack < < 1;
if( X & 1 ) stack = stack + 1;
return X > > 1;
}
int SL(X)
{
X = X < < 1;
if( stack & 1 ) X=X+1;
stack = stack > > 1;
return X;
}
Line_Draw()
{
if( (a==c ) && ( b==d )
{
color(a,b);
}
else
{
d = SR(b+d);
c = SR(a+c);
Line_Draw(a, b, c, d);
c = SL(c) - a;
d = SL(d) - b;
b = SR(b+d+1);
a = SR(a+c+1);
Line_Draw(a, b, c, d);
a = SL(a)-c-1;
b = SL(b)-d-1;
}
return;
}
These routines can be further reduced and improved for speed by so doing. For instance, SR and SL are essentially the same routine and could easily be combined. This particular form of a line is also easily expressed with a grammar. Anyone interested in the other work I have done on this kind of plotting routine should contact me. The above routine produces a remarkably symmetrical line.
It is possible to take some beautiful recursive routines and convert them to a form that doesn't use the data stack. This results in a longer, more difficult to read routine that makes more efficient use of memory. It is sometimes possible through further reductions to remove the return stack making for efficient use of memory at the expense of creating true spaghetti code.
Comments, complaints, flames and complements should be directed to Otto
Footnote: Trivial, unless you are a Tibetan monk playing with giant pieces made out of granite. The largest piece in one such game is 20 feet wide and three feet high. The smallest piece in the same game is the size of a large washer. When they finally move the biggest piece, it will probably be trivial. Return to place in document.