From: martelli@cadlab.sublink.org (Alex Martelli)
Newsgroups: comp.lang.c
Subject: Re: To Recurse or NOT to recurse?
Date: 10 Nov 92 08:30:01 GMT
Organization: CAD.LAB S.p.A., Bologna, Italia

rickr+@CMU.EDU (Richard Dale Romero) writes:

:Excerpts from netnews.comp.lang.c: 6-Nov-92 To Recurse or NOT to
:recurse? Stephen Schow@netcom.com (577)
:
:> What is better to do when traversing a linked list..... SHould I use
:> recursion to search down through the list for the last node, or should I
:use a while loop?  What or the pro's and con's of each?
:
:Some compilers are really smart, and they will turn your code into (if
:it is tail recursion) into a while loop.  Others won't.  If it doesn't,
:are you wasting space?  Yes.  How much?  Well, you're using O(N) space
:when it can be done in O(1) space.  That's a lot as far as I'm
:concerned.  And speed?  Bit trickier, and dependent on the machine you
:use, but I'd lay odds on the while loop, say 10:1, that it'd be faster.

Right.  Tail recursion can be *mechanically* eliminated anyway; if you're
not sure that your target compilers will do it, do it yourself!  In the
general case, you can first put the tailrecursive function into the form:

returned_value_t
function(argument_vector)
{
    first_block_of_code;
    if(recurse_cond)
	return function(other_arguments);
    second_block_of_code;
    return something_else;
}

which is provably equivalent to:

returned_value_t
function(argument_vector)
{
    do {
	first_block_of_code;
    } while(recurse_cond && ((argument_vector=other_arguments),1));
    second_block_of_code;
    return something_else;
}

where the "vector assignment" to the arguments can be expressed as a
series of comma-operator-separated normal assignments to the arguments.
You can most often simplify further.
C is particularly well-suited to this transformation thanks to the
uniform value-passing-semantics of arguments; in Pascal, e.g., you would
have to account for "var" arguments which make it a bit more tricky from
a formal point of view - in C the indirectness implicit in the var arg.
is made explicit, simplifying things.

Let's apply this technique to "return pointer to last node of linked list".
Say we have the type:
struct node {
    whatever_t contents;
    struct node *next;
}

then the obvious find-last-node recursive implementation is:

struct node *
find_last_node(struct node *list_ptr)
{
    if(list_ptr && list_ptr->next)
	return find_last_node(list_ptr->next);
    return list_ptr;
}

Here both blocks of code are empty, so the recursion elimination gives:

struct node *
find_last_node(struct node *list_ptr)
{
    do {
    } while(list_ptr && list_ptr->next &&
		((list_ptr = list_ptr->next),1));
    return list_ptr;
}

The funny/fancy do-while with empty body and embedded assignment cries
out to be rewritten, of course, to give:

struct node *
find_last_node(struct node *list_ptr)
{
    while(list_ptr && list_ptr->next)
	list_ptr = list_ptr->next;
    return list_ptr;
}

Now the double-test in the while-condition stands out; each time except
the first, we are testing TWICE for non-NULL list_ptr (since each
time we test for non-NULL ->next, then we put ->next into list_ptr
and test for it again).  We can almost halve the work by only testing
for list_ptr itself at the beginning, and in the loop only for ->next:

struct node *
find_last_node(struct node *list_ptr)
{
    if(list_ptr)
        while(list_ptr->next)
	    list_ptr = list_ptr->next;
    return list_ptr;
}

One can of course build this cleanest and most effective solution in many
other ways (for example from reasoning backwards to the postcondition we
want, "!list_ptr || !(list_ptr->next)", and designing the if() and while()
to suit), but I find the way in which it springs from mechanical recursion
elimination and a little observation quite didactically enlightening...
-- 
Email: martelli@cadlab.sublink.org                   Phone: ++39 (51) 6130360
CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia   Fax: ++39 (51) 6130294