Glynn Clements wrote:
> For branched recursion, you can apply the same techniques that the
> paper describes to eliminate the need to store local variables on the
> stack. If you can deduce which occurrence of the recursive call you're
> returning from, you don't need to store the return address.
>
> I don't have an example to hand, but I will generate one.
OK, example generated.
The attached program demonstrates 3 approaches to traversing a binary
tree. The first approach is the `natural' one, using a recursive
definition.
The second approach eliminates the need for a data stack.
The third approach simulates the function calls, eliminating the need
for a return address stack.
It should be clear that in order for the last two approaches to work,
the tree nodes need to have `up' pointers. This should help to clarify
the type of algorithms to which stackless recursion can be applied,
and those to which it can't.
--
Glynn Clements <[EMAIL PROTECTED]>
#include <stdio.h>
typedef struct tree
{
char *data;
struct tree *left, *right, *up;
} tree;
static void print_tree_1(tree *t)
{
if (t->left)
print_tree_1(t->left);
puts(t->data);
if (t->right)
print_tree_1(t->right);
}
static tree *t;
static void print_tree_2(void)
{
if (t->left)
{
t = t->left;
print_tree_2();
t = t->up;
}
puts(t->data);
if (t->right)
{
t = t->right;
print_tree_2();
t = t->up;
}
}
static void print_tree_3(void)
{
call:
if (t->left)
{
t = t->left;
goto call;
}
return1:
puts(t->data);
if (t->right)
{
t = t->right;
goto call;
}
return2:
if (!t->up)
return;
if (t == t->up->left)
{
t = t->up;
goto return1;
}
else
{
t = t->up;
goto return2;
}
}
static tree data[7] = {
{"one", NULL, NULL, data + 1},
{"two", data+0, data+2, data + 3},
{"three", NULL, NULL, data + 1},
{"four", data+1, data+5, NULL},
{"five", NULL, NULL, data + 5},
{"six", data+4, data+6, data + 3},
{"seven", NULL, NULL, data + 5},
};
int main(void)
{
puts("First version");
puts("--------------");
print_tree_1(data + 3);
puts("--------------\n");
puts("Second version");
puts("--------------");
t = data + 3;
print_tree_2();
puts("--------------\n");
puts("Third version");
puts("--------------");
t = data + 3;
print_tree_3();
puts("--------------\n");
return 0;
}
