DenkzeitWiki

Recursion

• TailCallOptimization (TCO)
• ProperTailRecursion (PTR)
• ProperTailCall (PTC)
• TailCallElimination (TCE)
• TailRecursionElimination (TRE)

Tail Recursion

• Wikipedia:Tail_recursion

Tail recursion is interesting because it is form of recursion that can be implemented much more efficiently than general recursion. In general, a recursive call requires the compiler to allocate storage on the stack at run-time for every call that has not yet returned. This memory consumption makes recursion unacceptably inefficient for representing repetitive algorithms having large or unbounded size. Tail recursion is the special case of recursion that is semantically equivalent to the iteration constructs normally used to represent repetition in programs. Because tail recursion is equivalent to iteration, tail-recursive programs can be compiled as efficiently as iterative programs. [1]

A compiler is said to implement TailRecursion if it recognizes this case and replaces the caller in place with the callee, so that instead of nesting the stack deeper, the current stack frame is reused.[2]

Tail Call Optimization

• re-use stack, because stack is limited

• http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
  • Limited stack space - If you're a functional programmer, or coding in a similar style, this is not very appealing - one can never be sure if, or when, recursive functions will mysteriously fail.

• TrampolineStyle, Clojure
  • http://lambda-the-ultimate.org/node/3106#comment-45321
    • Some confusion: trampolining is an implementation technique. You need not ever see it. Clojure makes it optional and visible, but it can be invisible and automatic as well.

• see PythonIdioms
  
• http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html
• http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html
  
• http://souja.net/2009/04/on-tail-recursion-elimination.html

• Why Object-Oriented Languages Need Tail Calls by GuySteele
• http://lambda-the-ultimate.org/node/3702

Object-oriented programming in languages that don't require tail-call optimizations makes no sense. MatthiasFelleisen

• http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html
• http://funcall.blogspot.com/2009/04/you-knew-id-say-something-part-ii.html
• http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iii.html
• http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html
• http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-v.html
  
  
• http://www.tbray.org/ongoing/When/200x/2009/10/27/Recur (ala Clojure)
  
  
• Tail recursion in object systems from comp.compilers
  
  
• good examples where ProperTailRecursion is elegant
  • Finite State Machines
    • http://blogs.adobe.com/fcheng/2008/02/proper_tail_calls_and_state_ma.html
    • Finite state machines in JavaScript
  • Message Passing
    
  
  
• http://stackoverflow.com/questions/1483405/is-erlangs-recursive-functions-not-just-a-goto