Tail recursion and complete recursion?
Author Message Tail recursion and complete recursion?

Can someone tell me what the difference is in tail recursion
and complete recursion?

Tue, 29 Oct 1996 13:08:23 GMT  Tail recursion and complete recursion?

Quote:

>Can someone tell me what the difference is in tail recursion
>and complete recursion?

Operationally, a tail-recursive call is a function/procedure call just
prior to a return from the function/procedure that did the call. The
reason this is interesting is that the stackframe of the calling
function/procedure is not needed anymore and can be overwritten by the
stackframe of the new function/procedure. Tail-recursive programs can
thus be implemented using constant size stackspace.

Syntactically, tail-recursive function/procedure calls must not be
embedded in any other function call, nor in arithmetic
expressions. They may be in the branches of conditionals and as the
last expression/statement in a sequence of expressions/statements.

Some examples (in C):

int factorial(n)
int n;
{
if (n==0) return(1);
else return(n*factorial(n-1));
}

is not tail recursive, as the call is embedded in an arithmetic
expression. On the other hand

int factorial(n)
int n;
{
return(fac_acc(n,1));
}

int fac_acc(n,f)
int n,f;
{
if (n==0) return(f);
else return(fac_acc(n-1,n*f));
}

is tail recursive. Tail recursive functions may have several recursive
calls, as long as they are in different branches of a conditional,
e.g.

int binsearch(a,v,i,j)
int a[],v,i,j;
{
if (a[i]==v) return(i);
else if (v<=a[(i+j)/2])
return(binsearch(a,v,i,(i+j)/2));
else
return(binsearch(a,v,(i+j)/2)+1,j);
}

In some functions, some of the calls may be tail-recursive whil other
are not. Such functions are not called tail-recursive. An example is

int ack(m,n)
int m,n;
{
if (m==0) return(n+1);
else if (n==0) return(ack(m-1,1));
else return(ack(m-1,ack(m,n-1)));
}

Here the innermost call in the last line isn't tail-recursive. The
function can't be made tail-recursive without introducing extra
variables.

Tue, 29 Oct 1996 16:48:04 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages