Thread: tail recursion

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002

    tail recursion

    I recently read in a book about tail recursion and how most good compilers do it. The problem is that it gave a very poor definition of what exactly tail recursion was. Depending on where I've read, its either the ability of recursion to simulate iteration, or the ability of a recursive function to perform on the second half of say a vector even though it wasn't told to! Now you can see why I'm confused! Can anyone help me grasp what this means possibly with a small example?

  2. #2
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    <programming> When the last thing a function (or procedure) does is to call itself. Such a function is called tail recursive. A function may make several recursive calls but a call is only tail-recursive if the caller returns immediately after it. E.g.

    f n = if n < 2 then 1 else f (f (n-2) + 1)

    Here the both calls to fib are {recursive} but only the outer one is tail recursive.

    See {tail recursion optimisation}, and, if you aren't sick of them already, {recursion}, {tail recursion}.

    [{Jargon File}]


    Tail Recursion Optimisation
    (TRO) When the last thing a function or procedure does is to call itself, it is not necessary to retain the calling environment. This is important when a procedure calls itself {recursive}ly many times for, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the last call terminated.

    Tail recursion optimisation is a special case of {last call optimisation} but it allows the further optimisation that some arguments may be passed in situ, possibly in {register}s. It allows recursive functions to be compiled into {iterative} loops. See also {conversion to iteration}, {tail recursion modulo cons}.

  3. #3
    Join Date
    Aug 2001
    I think it was Steele who said that "tail recursive functions
    are like gotos but with parameters". The scheme language
    has no loop primatives and requires an implementation to
    use tail recursion. For c compilers it's not to much of
    a problem since most people don't write code like this
    in c

    void f(int n)
          if (n != 0) 
                 printf("n = %d\n", n);
          f(n - 1);

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Okay, that makes a lot more sense now. Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  3. reading from files
    By recluse in forum C Programming
    Replies: 25
    Last Post: 12-26-2004, 10:33 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. change stack to a queue
    By sballew in forum C Programming
    Replies: 12
    Last Post: 12-03-2001, 11:16 PM