Hi Everybody,
Here's the paper about stack free recursion. I'm e-mailing it to the list
partly because I sometimes delete e-mail without meaning to delete it.
This way, I won't risk losing your letters.
Warm wishes,
Bill
(C)opyright 1995, Otto J. A. Smith (206) 385-1956 [EMAIL PROTECTED]
�
�
Stack Free Recursion
Otto J. A. Smith
Sept 29, 1995
�
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 facto
rial 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 rec
ursive call.
/* line 7 */ .
/* line 8 */ . //Anything here also
/* line 9 */ .
/* line 10 */ return somevalue;
/* line 11 */ }
Do the following:
1. Insert x = f(x) before the statement containing the recursive call
(before line 6)
2. Insert x = i(x) after the statement containing the recursive call
(after line 6)
3. Replace stackfree(f(x)) in line 6 with stackfree() .
4. Replace all other occurrences of x in the line containing the
recursive call (line 6) with i(x)
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 contai
ning 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 facto
rial 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 entr
y.
{ // Note that within this routine we treat x as a glob
al.
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;
}
STACKLESS TOWERS OF HANOI
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 * otherT
ower)
{
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.
A LINE DRAWING ROUTINE
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:
1. If (a,b) and (c,d) are the same point, then we color (a,b) and
return, this is the termination condition. That is:
if( a==c && b==d ){ color(a,b); return; }
2. if (a,b) and (c,d) are not the same point we draw two new lines.
Line_Draw(a,b,w,x) and Line_Draw(y,z,c,d). w,x,y and z are
calculated as follows where the symbol > > represents shift right,
that is divide by 2:
w = a+c > > 1
x = b+d > > 1
y = a+c+1 > > 1
z = b+d+1 > > 1
The least significant bit is lost in the shift right operation.
The recursive line drawing routine is then:
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 a
n inverse
we will cheat and introduce our own data stack that is one bit wide and quite s
hort.
One 32 bit unsigned integer provides enough room for a screen that is 64K by 64
K pixels.
Here is a code fragment and its inverse used to implement a+c > > 1 and its i
nverse.
/* 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 argume
nts
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 ot
her work I have done
on this kind of plotting routine should contact me.
The above routine produces a remarkably symmetrical line.
CONCLUSION:
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
[EMAIL PROTECTED]
Footnote: Trivial, unless you are a Tibetan monk playing with giant pieces mad
e out of granite.
The largest piece in one such game is 20 feet wide and three feet high. The sm
allest 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.
__________________________________________________________________________
To MathVision Inc., (formerly 7seas software) Corporate page.
