Talk:Tail recursion

From Wikipedia, the free encyclopedia

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start	rated as Start-Class on the assessment scale
Mid	rated as Mid-importance on the assessment scale

Contents 1 intro 2 Old question 3 code and pre formatting in firefox 4 Clarification? 5 C examples of tail recursion modulo cons 6 Additional con 7 bad example? 8 lack of mainstream compiler support 9 Another mechanism 10 Tail Recursion Distinctiveness Being Lost 11 Article Confuses Tail Recursion with Tail Calls 12 Opening Paragraph

[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)

[edit] Another mechanism

The article states 'When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete'.

Not necessarily - this is implementation dependent. Henry Baker somewhere discusses treating calls as a sort of dynamic macro, expanding each function token and pushing that onto an execution stack after popping the original occurrence of the function token. There is no explicit return at all, with the execution stack unravelling as it goes (until, presumably, it reaches a sentinel at the end). Even though there is apparently more overhead, Henry Baker suggested that if a language typically has small functions, with modern high speed caches this might be competitive. Also the overhead would obviously be immaterial for some user I/O bound scripting languages. P.M.Lawrence.

I've undone your edit. If you want this added, then find a comprehensible source or make an edit which properly explains how this works. --MarSch 10:24, 12 July 2007 (UTC)

So I notice. May I ask why you undid it, as opposed to clarifying it further yourself? As it now stands, it is false. You had the Henry Baker reference here to draw on. I decided to do no more than mention the existence of other ways for reasons of (a) relevance and (b) space. How do you suggest "explaining" it without defeating the object? "dynamic macro expansion" seemed to me to be a sufficient description. PML.

Here's something for you to work with, from Henry Baker's material at [1] (last paragraph before the conclusion). I have highlighted the part that conclusively demonstrates that the undo has made a false statement:

Since Forth is usually implemented on a traditional von Neumann machine, one thinks of the return stack as holding "return addresses". However, in these days of large instruction caches, in which entire cache lines are read from the main memory in one transaction, this view should be updated. It is well-known that non-scientific programs have a very high rate of conditional branches, with the mean number of instructions between branches being on the order of 10 or less. Forth programs are also very short, with "straight-line" (non-branching) sequences averaging 10 items or less. In these environments, it makes more sense to view the return stack itself as the instruction buffer cache! In other words, the return stack doesn't hold "return addresses" at all, but the instructions themselves! When a routine is entered, the entire routine is dumped onto the top of the return stack, and execution proceeds with the top item of this stack. Since routines are generally very short, the transfer of an entire routine is about the same amount of work as transferring a complete cache line in present architectures. Furthermore, an instruction stack-cache-buffer is normally accessed sequentially, and therefore can be implemented using shift register technology. Since a shift register can be shifted faster than a RAM can be accessed, the "access time" of this instruction stack-cache-buffer will not be a limiting factor in a machine's speed. Executing a loop in an instruction stack-cache-buffer is essentially the making of connections necessary to create a cyclic shift register which literally cycles the instructions of the loop around the cyclic shift register

I trust this is sufficient to make my point that the undo made an incorrect assertion and that a full demonstration would be long and off topic. PML.

You are talking about machine with an instuction and a data stack.

No, actually. If you can be bothered to follow the reference I gave, you will see that in the architecture Henry Baker was considering, this was a change to the return stack, and the data stack retained its former behaviour. That is why my wording referred to an execution stack. PML.

It simply starts executing on the data stack using the instruction at the top of the instruction stack. Instead of function calls it simply copies the instructions that define the called function to the top of the instruction stack and proceeds by executing them. It follows that there is no need to explicitly do a return instruction, since when all instructions of the called function are executed, automatically the next instruction on the stack is the one after the call. Still even if the return address is implicit like it is in this scenario, I don't think the current text:

When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete.

is false, even if the formulation is perhaps a bit biased towards register machines. Your own:

In a typical implementation, when a function is called the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete (this does not happen when calls are implemented by dynamic macro expansion to an execution stack).

is false instead, claiming the return address is not remembered.

If the continuation of a call is not stored in some way, then it is impossible to proceed with its execution after the call. It must be stored explicitly as a return address or implicitly in an instruction stack or some other way. --MarSch 18:02, 12 July 2007 (UTC)

Now you are wriggling. With this implementation there is no remembering involved apart from that provided by a program counter (or instruction pointer, or whatever you wish to call it). As at the point where the "call" - dynamic macro expansion - occurs, that PC or IP is changed. There isn't even your wriggling "implicit" return address, as it cannot be distinguished from any other address later in the sequence. There is no requirement whatsoever to remember the value the PC had immediately previously, and no way to reconstruct it.

I suggest you reinstate the information I provided, or reword it. If you do not do so, you are wilfully adopting the view that if you don't like an edit, or don't understand it, even if there are authorities in support of it, you will remove it. That is pretty much what vandalism is, so if you do not do something constructive within a period of grace of three days I shall reinstate pretty much what I put before. If you persist in removing what I have now demonstrated is factually correct, I shall report it as vandalism.

N.B., further argument on the point is not constructive. Making suggestions for alternative phrasing is. I notice that you did not respond to my request that you explain "why you undid it, as opposed to clarifying it further yourself" (emphasis added). I have been inviting you to be constructive and you have signally ignored the option. P.M.Lawrence.

Please don't throw around epithets like "vandal" so carelessly. You may want to read Wikipedia:Assume good faith before picking up this discussion again. I don't believe MarSch was acting maliciously.

I have read it, and I was not being careless. I do suppose that up to this point he was acting in good faith, and I was pointing out that for him to proceed knowingly would make that become vandalism - hence the "giving plenty of rope". PML.

As a matter of fact, I agree with pretty much everything MarSch has written here. While I don't see much of anything wrong with the phrase "In typical implementations", your additional parenthetical comment "(this does not happen when calls are implemented by dynamic macro expansion to an execution stack)" is not only ungrammatical, it's beyond unclear.

I must accept your judgment on unclear, but it is actually grammatical. But then, that is precisely why I invited constructive rewording - instead of which MarSch failed and refused to provide any. That is a giveaway as to whether he is becoming malicious. And, of course, not having that bracketed part, just having the other change, makes the edit as a whole weasel-wordish; it's only the "typically..." part on its own that works badly that way. I was well aware of that problem and wanted to clarify it away with something brief in brackets. If I failed to make things clear, that is no reason for MarSch's insisting on making them false instead of helping constructively. PML.

It doesn't matter what you say Henry Baker said, on this talk page; what matters in the end is what's written in the article itself. That parenthetical made no sense, so MarSch removed it. Fine.

Fair enough on that part, except that he didn't want an improved version either - but, he also removed the main part, recreating a falsehood. I agree that Henry Baker's points are irelevant to the body of the article; I only provided them to humour MarSch since he asked for a cite. PML.

It may be possible to add a more clear footnote to that paragraph pointing at Baker's paper; that's also fine.

Except that MarSch has made it clear that he doesn't want clarifications. When I offered some here on the talk page, he just rubbished them, claiming all sorts of wriggling stuff about the original.

However — admittedly without reading Baker's paper — I don't see how Baker's clever idea would work if the called function was actually bigger than the instruction cache. Then you'd need to fall back on the usual call-stack idea... unless Baker's talking about some kind of architecture where the instruction cache is unbounded in size and there is no "PC", which sounds cool, but also extremely esoteric and I'm not totally sure whether it would work. (In particular, I don't see how you'd make a function containing local branches, unless you used continuation passing style for everything (which is not unheard of)).

Off the top of my head I see no problem with forward branches, and backward branches can be handled using recursion. That is, if the higher level language needs (say) iteration, then that can be handled using an iterator construct that is syntactic sugar, i.e. that construct is itself implemented recursively. Perhaps the proposed change should bring out that this instruction stack approach makes tail recursion problems go away? The underlying conceptual problem doesn't go away, but the implementation issues get engineered out. PML.

I'll read the paper and see how Baker deals with it. Assuming the idea is worth mentioning, still, esoterica belongs in footnotes, where it won't clog up the main flow of ideas. --Quuxplusone 06:36, 13 July 2007 (UTC)

This approach treats the cache as a buffer, it doesn't need to get everything in at once. A virtual cache, if you will (and, if you want this for flexibility rather than efficiency, you can use batch files built around this - I've seen it, on old Datapoints). And yes, esoterica doesn't belong in the main stuff. I pointed thgat out myself. It's why I didn't provide any more than a terse piece of stuff in brackets. But if people insist that reasons be clarified and not just explained, then where are we? As things now are, MarSch has not only removed that, he has re-installed a fallacy. Specifically, it is not true that 'When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete' (emphasis added). P.M.Lawrence.

Did you know that you can type four tildes in a row — ~~~~ — to sign and date your posts? It's considered good form to sign and date comments on talk pages, so other readers can follow the chronology.

I've read Baker's paper now; it turns out that you quoted everything Baker had to say on the subject, so I wasn't able to satisfy my curiosity about the tricky bits of the idea. (I Googled up a post on the TUNES mailing list that gets about as detailed as Baker.) I was hoping to get back here before you called me on the "local branches" thing, though; I see now that in the "instruction stack" paradigm, one wouldn't have the concept of a "branch", but merely a lot of very small functions, mostly tail-recursive. However, I don't see what the idea buys you. You have to implement a hardware stack, which AFAICT is impossible to "get right"; either you make your expensive fast-memory "top of stack" buffer too big, in which case you waste resources, or you make it too small, in which case you lose efficiency. (Or you do something totally different and cool that we all missed.) Niklaus Wirth has a very interesting essay called "Good Ideas: Through the Looking Glass"[2] in which he says the same thing about register windows, which strike me as very similar to the "instruction stack" idea: in both cases we're taking something with a pretty decent "traditional" implementation (normal register set; normal instruction cache) and deciding that it would be more theoretically attractive if it were implemented using a hardware stack instead.

Anyway, as soon as your instruction stack gets too big, I think you have to start paging out the lower part into RAM. Which means you're constructing — albeit inefficiently — a stack growing somewhere in RAM, containing the next instructions to be executed when the current procedure returns. (You can make it more efficient by only storing those instructions' addresses in the stack, of course.) And then what do you have? A call stack!

If you can provide any evidence that this "instruction stack" idea actually works in hardware, in some way that is not dependent-on or in-the-worst-case-isomorphic-to the traditional "call stack" paradigm, then (1) it'll be worth including in the article, and (2) I'll be very intrigued. Until then, though, the claim that an "instruction stack" magically makes the call stack go away strikes me as an extraordinary claim requiring extraordinary evidence to support it. --Quuxplusone 06:49, 14 July 2007 (UTC)

I just thought I'd chime in to say that most of this discussion and indeed much of the article as it currently stands seems to focus on programming language design, compiler design and computer architecture, as opposed to the "pure computer science" concept of tail recursion. Surely these are important related topics, and there is ample room in the article to discuss how tail recursion impacts upon them, but I think the article would be best served by putting those parts in separate sections and labeling them appropriately. As for this particular debate, I think such a labeling would help to solve the problem: P.M. Lawrence is correct when he says that the "description" section is imprecise in that such statements about return addresses are implementation dependent, and others are correct in that a major reason why tail recursion is an important concept is that what i believe to be a vast majority of architectures utilize such an implementation. Perhaps to start with the "description" section should be renamed "tail call optimization." Looking around, I would say that the article Recursion (computer science) actually contains a better description of tail recursion than this article. Bgruber 01:05, 16 July 2007 (UTC)

[edit] Tail Recursion Distinctiveness Being Lost

IMHO The main point of distinction for tail recursion (as opposed to general recursion) is that it can be optimized. I know that Common Lisp and SCHEME optimize tail recursion intelligently. The wording of the intro suggests even tail recursion is always inefficient. I assume that is not intended. See Paradigms of Artificial Intelligence Programming by Peter Norvig page 63.

Also IMHO, the functional equivalence and mutual transformability of recursion and iteration is true and important. But it is confusing to mention it in an intro to tail recursion. Can this be put somewhere else?

BTW: AI employers often ask applicants if they know about the significance to efficiency of tail recursion. ClickStudent 14:35, 14 September 2007 (UTC)

I do not think your assertion in your edit to the article that general recursion can be transformed into tail-recursion is correct. But I would love to be proved wrong. Do you have a reference? --MarSch 15:27, 14 September 2007 (UTC)

Apologies for my wording but you are absolutely correct (as far as I know). The reason I left in the half truth is that this wording seemed to me to have a better chance of avoiding removal, given the apparent preference of the original writer for iteration universally. Sadly, truth is often politics. I have seen that in far too many wiki entries. Feel free to modify as you see fit. You obviously understand. BTW: This is my first wiki edit. It seemed presumptuous to start right out with modifying an intro. (afterthought: many could be replaced with tail recursion, but I don't want to do the Turing proof.) Apologies again. ClickStudent 13:33, 16 September 2007 (UTC)

Please don't feel presumptuous about editing any part of any article. Taking action is encouraged (WP:BOLD).--MarSch 09:37, 17 September 2007 (UTC)

Second afterthought...Any recursion CAN be transformed to a tail recursion. But you need to use another stack. Proofs about recursion generally get handled with the Pumping Lemma (see any computational theory textbook, e.g. Sipser). 'course, using another stack is probably cheating for purposes of our discussion. 17:35, 16 September 2007 (UTC) —Preceding unsigned comment added by ClickStudent (talk • contribs)

Right, the possibility of using an extra stack had slipped my mind. Anyway, general recursion is off-topic in this article, since this article is specifically about tail recursion. So even though your edit did not introduce any errors it does remove a simplified characterizaton of what tail recursion is. I will revert you for now, but don't let that discourage you from fixing any other issues that you perceive. --MarSch 09:37, 17 September 2007 (UTC)

One more thought. Perhaps the use of "iterative process" and "recursive process" (as also used in SICP) would clarify this article. --MarSch 09:41, 17 September 2007 (UTC)

OK, your points are well taken. I've given it a second try at simplification. (BTW: I'm reluctant to introduce the word "process" in an intro.) It seems to capture the essence of what tail recursion is good for, as far as I know. I hope you consider it to be accurate and concise. ClickStudent 11:44, 19 September 2007 (UTC)

I've edited your version. I hope you're starting to like the intro better. --MarSch 15:03, 19 September 2007 (UTC)

This version is extremely confusing. It sounds like tail recursion always returns immediately to the function that isn't part of the recursion. ClickStudent 20:21, 19 September 2007 (UTC)

[edit] Article Confuses Tail Recursion with Tail Calls

This article starts by talking about tail recursion and then gets lost in talking about tail call optimization.

A tail call is the general case where a procedure calls a procedure as its last action and does not need to do further processing of the result. A tail recursion is a special case of a tail call where the procedure calls itself. Tail recursion is much easier to optimize than general tail calls. All it requires is that your target instruction set/language have an equivalent of jmp or goto.

In particular, that means that for the most common compiler targets - C, virtually any machine code, and several virtual machines (JVM and CLR) - tail recursion can be done with little effort. The compiler can just emit an imperative loop with a jmp/goto from the bottom of the procedure to the top (note, on the JVM Java does not do this optimization but Scala does).

The more general tail call case is what may require all the more advanced stuff this article talks about such as trampolining, garbage collected stack frames, etc.

Second, the article says that Scheme requires tail recursion optimization. That's true, but not the real story. Scheme (along with Haskell) requires full blown tail call optimization. Of course, that implies tail recursion optimization as well because a tail recursive call is just a special case of a tail call. —Preceding unsigned comment added by 149.63.92.58 (talk) 16:47, 17 October 2007 (UTC)

[edit] Opening Paragraph

Some reasons why I attempted the minor changes to the opening:

• "tail recursion is recursion where the last operation is a recursive call" -- need to clarify that there is no additional (non-tail) call as well.

• minor: "the function" is suddenly introduced mid-sentence, even though recursion is about algorithms, not just functions.

• The phrasing "such recursions can be translated ..." seems awkard. Every English speaker I know would say "such recursive calls can be translated ...". Admittedly, this could be a difference between US English usage and other English usage.

• "...with iteration, manually or automatically," still scans poorly to me; while 'either' adds one word it is worth the clarity.

A bigger problem with the opening paragraph is that recursion is about algorithms, whereas tail-recursion-optimization is about implementation (as the previous section alludes to). not-just-yeti (talk) 14:44, 15 May 2008 (UTC)