Should I convert FORTRAN code to C?

[kenny at m.cs.uiuc.edu]

/* Written  1:42 pm  Jul  9, 1988 by wayne at dsndata.uucp in m.cs.uiuc.edu:comp.lang.c */

I used to think that recursion was unnecssary and very expensive, but
now i am not so sure.  what about the cases where you recurse from
more than one place?  can you do that without a stack of flags and
lots of ifs?  an example, how would you do something like this:
[example deleted]
/* End of text from m.cs.uiuc.edu:comp.lang.c */

You do it with a stack of state variables, true, but it's ideal to
encode the choice of return point into a single state variable, and
`switch' on it.  You wind up with code that's very similar in
appearance to Program 4 in my earlier posting, but possibly with more
states.

In any case, though, most `recursions from more than one place' wind
up being used in `divide and comquer' techniques, and the trick here
is that one of them is generally a tail recursion.  Tail recursions
can get folded out immediately (just change the parameter values and
branch to the top), leaving only the internal recursion to deal with.

For instance, consider the following procedure to print a tree, in
inorder:

struct node {
	struct node *left;
	struct node *right;
	char *content;
	};

ptree (n)
	struct node *n;
{
	if (n -> left) ptree (n -> left);
	printf ("%s\n", n -> content);
	if (n -> right) ptree (n -> right);
}

The first thing we do is eliminate the tail recursion, trivially:

ptree (n)
	struct node *n;
{
start:
	if (n -> left) ptree (n -> left);
	printf ("%s\n", n -> content);
	n = n -> right;
	if (n) goto start;
}

Now we use an explicit stack to attack the remaining recursion, and don't need a state variable for the return address:

ptree (n)
	struct node *n;
{
	struct node *stack [MAXDEPTH];
	int depth = 0;	
start:	if (n -> left) {
		stack [depth++] = n;
		n = n -> left;
		goto start;
finish:		n = stack [--depth];
		}
	printf ("%s\n", n -> content;
	n = n -> right;
	if (n) goto start;
	if (depth) goto finish;
	}

Now we untangle the spaghetti:

ptree (n)
	struct node *n;
{
	struct node *stack [MAXDEPTH];
	int depth = 0;	
	for (;;) {
		while (n -> left) {
			stack [depth++] = n;
			n = n -> left;
			}
		for (;;) {
			printf ("%s\n", n -> content);
			n = n -> right;
			if (n) break;
			if (depth == 0) return; /* 2-level break */
			n = stack [--depth];
			}
		} 
	}

I agree that the recursive formulation is *much* clearer, which is why
I contend that really good optimizing compilers shoud do this for you.
Those of us who work in Fortran have to do it by hand.

BTW, I know that there are clearer ways to write the procedure
non-recursively; I was illustrating the mechanical way that an
optimizer would get from here to there.