Siemel Naran <
[email protected]> scribbled the following
Tail recursion is first doing the computation, then recursing. Head
recursion is the other way around.
There's a generally-accepted definition that pins it down more precisely
than this.
A "tail call" is a call to a function where the return value of that
function is returned directly from the calling function without any
further processing:
--------
int foo(int i)
{
int j;
j=do_nontail_call(i);
return do_tail_call(j);
}
--------
(Or even:
--------
int foo2(int i)
{
return do_tail_call(do_nontail_call(i));
}
--------
which when untangled does the exact same thing, but doing the untangling
may lead to a clearer idea of where exactly the boundary is.)
It's possible, in theory at least (though some parameter passing
mechanisms make it too difficult to be worth the effort), to remove
the invocation record for the function making the tail call from the
invocation-record stack and have the tail-called function return directly
to the function that made the last non-tail function call.
"Tail recursion" is recursion accomplished using tail calls. Note that
this is a property of the calls made and not simply of the function
itself, and it's possible to make a tail-recursive and non-tail-recursive
call to the same function:
--------
void untested_and_probably_buggy_quicksort(int *data,size_t n)
{
int middle_index;
/*Make sure the recursion terminates*/
if(n<2)
return;
/*Hand-waving to avoid having to do too much thinking*/
middle_index=untested_and_probably_buggy_partition(data,n);
/*Non-tail-recursive call*/
untested_and_probably_buggy_quicksort(data,middle_index-1);
/*Tail-recursive call*/
untested_and_probably_buggy_quicksort(data+middle_index+1,
n-middle_index-1);
/*Note that even though we're not actually returning anything,
we're not doing anything between when the tail call returns
and when we return.
*/
}
--------
The aforementioned invocation-record-stack optimization for tail calls
has the effect of converting tail recursion into iteration, so the above
is exactly equivalent (assuming this optimization does indeed occur) to:
--------
void untested_and_probably_buggy_quicksort(int *data,size_t n)
{
int middle_index;
/*A compiler may not be clever enough to convert the exit
condition from the if(...)return form to while(...) directly,
but a good optimizer should generate the same code for
both forms.
*/
while(n>1)
{
/*These are the same as the tail-recursive version*/
middle_index=untested_and_probably_buggy_partition(data,n);
untested_and_probably_buggy_quicksort(data,middle_index-1);
/*Here we're replacing the old parameters with the values
they'd have in the next (tail-recursive) invocation,
then going back to the top of the loop
*/
data=data+middle_index+1;
n=n-middle_index-1;
}
}
