Talk:Tail recursion
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science. | |
| ??? | This article has not yet received a rating on the assessment scale. | |
| ??? | This article has not yet received an importance rating on the assessment scale. | |
Contents |
[edit] intro
my revision to the intro was because i thought the actual statement of what tail recursion really is had gotten a bit buried. Bgruber 04:52, 6 May 2006 (UTC)
[edit] Old question
Isn't the second point in the recursive definition backwards? Shouldn't
- 2. If (if E0 E1 E2) is a tail expression, then both E1 and E2 are tail expressions.
be rather
- 2. If E1 and E2 are both tail expressions, then (if E0 E1 E2) is a tail expression.
? --Mormegil 14:29, 13 Oct 2004 (UTC)
- No, this is correct. The statement is an expansion of the definition of tail expression. A tail expression here is an expression whose value is returned by the caller. This part of the definition simply states that, if the expression (if E0 E1 E2) is a tail expression, then both E1 and E2 are tail expressions - that is, if the value of (if E0 E1 E2) is directly returned by the caller, then, no matter which one of them is actually selected by the if operator, the value of E1 and E2 will be returned by the function that made the if call.
- Where you are confused can be answered by this: The state of being a tail expression is dependent upon location, not upon any intrinsic properties of the expression. Ari 08:28, 26 December 2005 (UTC)
[edit] code and pre formatting in firefox
Previous tail recursion edit and Tail recursion differ only by <pre> being replaces with <code> tags, yet in firefox 1.0 <pre> yields 6 boxes and <code> yields 11 boxes! -- Dbroadwell 20:10, 17 Feb 2005 (UTC)
[edit] Clarification?
Does this sound strange to anybody else? EmilioSilva 00:02, 15 September 2005 (UTC)
- "For normal, non-recursive function calls, this is usually a micro-optimization that saves little time and space, since there are not that many different functions available to call."
- It seems strangely-worded. Ari 08:28, 26 December 2005 (UTC)
[edit] C examples of tail recursion modulo cons
The section about tr modulo cons currently has examples in C, which I'm afraid not everyone may be able to read; esp. an expression like malloc(sizeof(list)) may be very confusing. I've rewritten the first example in pseudocode (below), but I'm not sure how to express &(*p); are there conventions for working with pointers in pseudocode?
function f(input : List) returns List
if input = nil
return nil
else
var n = new Link
n.value = 1
n.next = f(input.next)
return n
Qwertyus 13:08, 15 April 2006 (UTC)
[edit] Additional con
On newer microprocessor architectures hardware the branch predictor cannot predict function calls which isn't paired with returns. The performance hit can usually be triggered up in the call stack after the code has finished executing and returned, in completely unrelated code which does not mess with the stack.
[edit] bad example?
I'm confused by:
In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.
I think this is trying to say either for efficiency reasons, some functions are re-written to use mutation, or if you have shared data, then operations like filter may want to mutate their inputs? I'm unsure. Either way, this is nothing specific to tail recursion. --Ian Barland Not-just-yeti 14:31, 14 December 2006 (UTC)not-just-yeti
[edit] lack of mainstream compiler support
I just checked, and gcc, g++ and Java all fail to optimize a one-line tail-recursive function. Why? It might be nice have a paragraph trying to justify this. The only explanation I currently see is "making a complete call graph is a daunting task for a compiler". And in general, mutual recursion (esp. across files) might be problematic. But why not just check for a function recurring on itself, and optimize that? (The reason I'm looking at this wikipedia page is because theEuclidean Algorithm page made a claim that tail-recursion is inherently inefficient, whereas I thought it was more of lazy compiler-writers :-) --Ian Barland Not-just-yeti 14:31, 14 December 2006 (UTC)not-just-yeti
- I'm pretty sure gcc and g++ both optimize tail recursive functions, but Java does not. At least that's what was taught in my programming languages class. 67.135.15.12 04:14, 6 February 2007 (UTC)
- The article Euclidean Algorithm says "or using iteration (more efficient with compilers that don't optimize tail recursion)" which is correct.
- For more info on what gcc does with tail calls look at http://home.in.tum.de/~baueran/thesis/baueran_thesis.pdf --MarSch 10:07, 6 February 2007 (UTC)
- Ah, that's a nice, easy-to-understand reference, thanks. (Been too long since I've worked with C; I'd forgotten just how easy and nasty pointer games are.) That thesis should probably be one of the references for the main article.
- Yeah, the Euclidean Algorithm page is correct now, but an earlier version had said tail-recursion could never be as efficient.
- FWIW, the thesis asserts that limited tail recursion has been implemented in gcc for a while, but using gcc 4.0.3, the shortest tail program I write still Seg faults when I start trying large numbers. Sigh. --Not-just-yeti 23:20, 6 February 2007 (UTC)
