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  
 
 [ 2 post ] 

 Relevant Pages 

1. RECURSION RECURSION RECURSION ... AAARRGGHHHH

2. OO, lexical scope, closure, tail-recursion, continuation

3. Lisp type list, recursion and tail call optimisation

4. Tail recursion ???

5. Tail recursion

6. Thanks for the tail recursion

7. How is tail-recursion optimized in Smalltalk?

8. Any Smalltalk supporting tail recursion optimization ?

9. Tail-optimized recursion

10. tail recursion analysis

11. tail recursion -- what's a good name

12. Recognising tail recursion

 

 
Powered by phpBB® Forum Software