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.