21

Possible Duplicate:
Are there problems that cannot be written using tail recursion?

From my understanding, tail recursion is an optimization you can use when a recursive call does not need information from the recursive calls that it will spam.

Is it possible then to implement all recursive functions using tail-recursion? What about something like DFS, where you need the innermost child to return before the parent can?

nbro
  • 15,395
  • 32
  • 113
  • 196
aerain
  • 1,149
  • 3
  • 12
  • 17

7 Answers7

15

It depends on exactly what you are asking.

If you want to keep all functions as functions (no mutable state) with the same signatures, then no. The most obvious example is the quicksort, where both calls can't be tail calls.

If you can modify the function in various ways, then yes. Sometimes a local modification is sufficient - often you can add an "accumulator" that builds some expression that is returned, although, if the result involves non-commutative operations, then you need to be careful (for example, when naively constructing linked lists, the order is reversed) or you can add a stack.

Alternatively, you can do a global modification of the entire program, in which each function takes as an extra argument the function that contains future actions. This is the continuation passing that Pete is talking about.

if you are working by hand then the local modification is often fairly easy. but if you're doing automated rewriting (in a compiler for example) then it's simpler to take the global approach (it requires less "smarts").

nbro
  • 15,395
  • 32
  • 113
  • 196
andrew cooke
  • 45,717
  • 10
  • 93
  • 143
  • quicksort can be programmed tail-recursively, maintaining additional explicit stack of positions of the second half, for later processing. – Will Ness Aug 05 '12 at 23:08
  • you don't have to call the continuation itself that you receive, in the tail position. you can call whatever function you want in the tail position, in CPS. you'd just pass that continuation, as-was or modified, to that tail call. – Will Ness Aug 05 '12 at 23:20
  • a stack would be mutable state. i've tried to correct the cps description. – andrew cooke Aug 06 '12 at 00:03
  • no it's not. you push and pop as you pass it along. and array itself in quicksort is mutable, or else it is not a quicksort, because partition can't be done that way otherwise. Jerry Coffin's answer is plainly wrong. – Will Ness Aug 06 '12 at 00:05
  • then it's changing the signature. the part where i discuss quicksort says withiut mutation and keeping the same signature (i agree with you on the argument that quicksort as whole should be mutable, but we both lost that argument a long time ago - everyone else and their dog calls that kind of functional recursive sort quicksort). – andrew cooke Aug 06 '12 at 00:21
  • there's a great entry on reddit somewhere about how that functional version is actually a de-forested treesort. If you want, I'll look it up for you tomorrow. about signature, why not change it? The OP does not demand anything about signatures, he explicitly asks for *re-writes*. Re-writes are bound to change signature, they change functions after all. :) No, it is clear - anything hidden on the call stack, spread among call frames, can be made explicit and maintained on heap. turning every call into tail call. – Will Ness Aug 06 '12 at 00:28
  • i've added mention of the stack after the accumulator. i'm not making any value call on whether or not you should alter the signature - i'm just stating that given condition X you get Y etc etc. – andrew cooke Aug 06 '12 at 00:35
  • here's [that link i promised you](http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell). – Will Ness Aug 06 '12 at 00:44
  • If you can implement a tail-recursive version of F by changing the signature, you can implement it with the original signature by having it call the tail-recursive one. – Ben May 13 '13 at 00:44
5

Yes and no.

Yes, used in conjunction with other control flow mechanisms (e.g., continuation passing) you can express any arbitrary control flow as tail recursion.

No, it is not possible to express all recursion as tail recursion unless you do supplement the tail recursion with other control flow mechanisms.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 5
    I'm curious, can't [all recursive algorithms be written using iteration](http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration), and can't all iterative algorithms be [expressed using tail-recursion](http://www.quora.com/Can-all-iterative-algorithms-be-modelled-recursively-and-vice-versa)? Perhaps it's more a matter of direct/indirect ways of expressing it, or perhaps it's possible just with side-effects? – aioobe Jul 30 '12 at 04:10
  • Yes, recursive function can be computed by using iteration and managing the (call) stack manually. If the function can be transformed into a tail-recursive representation you can eliminate the stack. That's what a certain form of tail-recursion optimization does: It reuses the stack frame from the current call for the next call. If you have an iteration which does not use a stack you can transform it into a tail-recursive function. If it uses a stack the stack remains, i.e. there is no upper bound on the memory use of the stack, which is the point in tail-recursion optimization. – Stefan Jul 30 '12 at 07:06
  • 1
    Sorry, this is simply false. It is a fact that all programs can be rewritten as tail calls using continuations. – Pete Kirkham Aug 01 '12 at 21:04
  • 2
    @PeteKirkham: Claiming that it's "simply false" is misleading at best (and probably the worst excuse for a downvote I've seen the whole time I've been on SO). Yes, tail recursion *in conjunction with* something else (of which continuations are only one well known possibility) can do the trick. Tail recursion by itself is rather a different story. – Jerry Coffin Aug 01 '12 at 21:14
  • @aioobe: All recursive algorithms can be *implemented* using iteration. However, the straightforward iterative implementation that is usually meat by this simply "simulates" the recursion by using an explicit "stack" for storing intermediate data. The fact that this "stack" has unlimited size (i.e. more than `O(1)`) immediately indicates that the algorithm remains recursive, even if it was implemented in superficially "cyclic" fashion. A true cyclic implementation would require only `O(1)` intermediate data. – AnT stands with Russia Aug 01 '12 at 22:39
  • @aioobe: If you can find an iterative version of your algorithm with `O(1)` intermediate data, then you can also make a tail-recursive version for it (after all, iteration and tail recursion are the same thing). But if your "iterative" implementation requires more then `O(1)` intermediate data then it is not truly iterative. And it cannot be turned into a meaningful tail-recursive implementation. – AnT stands with Russia Aug 01 '12 at 22:41
  • 1
    @AndreyT given you can implement a complete language (scheme), or perform optimisations in compilers by making the transformation to a tail call, what is not 'meaningful' about the transformation of a not tail recursive operation using O(f(N)) stack to a tail-recursive one using O(f(N)) heap? In the real world, it gives you certain desirable features, such as allowing you to operate using a single garbage collected allocation mechanism so storage for unreachable stack objects are reclaimed. – Pete Kirkham Aug 02 '12 at 11:09
  • **wrong**. all you need to do is maintain explicit stack of positions for the second half, while processing the first half in a loop. when the first half processing has ended, unwind the explicit stack of second halves, descending on their first halves in the similar manner in a loop. – Will Ness Aug 05 '12 at 23:04
  • as a matter of fact, [here's a tail-recursive quicksort in Haskell](http://stackoverflow.com/a/9550430/849891) that follows exactly that strategy, described in my comment above. – Will Ness Dec 05 '14 at 16:58
3

All programs can be rewritten as tail calls using continuation passing. Simply add one parameter to the tail call representing the continuation of the current execution.

Any Turning complete language perform the same transformation as continuation passing provides - create a Gödel number for a the program and input parameters that the non-tail call returns to, and pass that as a parameter to the tail call - though obviously environments where this is done for you with a continuation, co-routine or other first-class construct makes it much easier.

CPS is used as a compiler optimisation and I have previously written interpreters using continuation passing. The scheme programming language is designed to allow it to be implemented in such a fashion with requirements in the standard for tail call optimisation and first class continuations.

Pete Kirkham
  • 48,893
  • 5
  • 92
  • 171
  • 3
    Taken as an answer to the question, as asked, this is simply false. Yes, it's possible to use continuations to simulate essentially any flow control you wish. The question, however, was only about tail recursion, not continuations. – Jerry Coffin Aug 01 '12 at 21:19
  • @Pete Kirkham: If you can find a way to encode the continuation state using `O(1)` memory, then it will indeed constitute a valid way to turn recursive algorithm onto a tail-recursive or iterative one. But if your continuation requires non-constant amount of memory, then the approach does not qualify as *tail recursion* in the sense of the original question. – AnT stands with Russia Aug 01 '12 at 22:45
  • 1
    @JerryCoffin the question as asked makes not mention of O(1) memory. – Pete Kirkham Aug 02 '12 at 10:42
  • No, it doesn't -- and I haven't mentioned such a thing either. Although I can see @AndreyT's point in bringing it up, I disagree with his (apparent) precept -- even if you could limit the continuation to constant size, it wouldn't change the fact that you're using a continuation, not just tail recursion. – Jerry Coffin Aug 02 '12 at 14:15
  • 1
    @JerryCoffin that's not far off saying you're using an integer counter not just iteration. AFAIK, the only language which has a standard where there is a guarantee of tail call optimisation is scheme, which also provides continuations. The two fit together, just like having a stack with non-tail call recursion, or having a counter with iteration. – Pete Kirkham Aug 02 '12 at 14:53
  • I see no similarity at all. His question was about tail recursion. Not about optimization and not about continuations, just tail recursion. All the discussion in the world of how Scheme uses continuations won't change that. – Jerry Coffin Aug 02 '12 at 14:59
  • @JerryCoffin unless you are going to start arguing that Scheme is not Turning complete, the existence of Scheme (or any of the other compilers and interpreters which use CPS and tail calls to *implement* (not simulate) recursion and iteration) provides proof that you can implement any recursive function using just tail calls. Without further comment from the OP as to restricting the case to imperative languages not implemented using CPS compilers, it is completely relevant. – Pete Kirkham Aug 02 '12 at 15:06
  • Let me try to summarize in terms that don't prompt emotional responses. He asked: "Is A sufficient for X". You downvoted all the answers saying "No, A is not sufficient for X", then wrote a reply saying "A + B *is* sufficient for X". I then commented that this requires B, not just A. From there, you've continued to insist that the sufficiency of A + B argues for the sufficiency of A without B. – Jerry Coffin Aug 02 '12 at 15:32
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/14808/discussion-between-pete-kirkham-and-jerry-coffin) – Pete Kirkham Aug 02 '12 at 15:55
  • @JerryCoffin **CPS transformation leaves only tail calls in the program, after it is done. It is simply a fact of life.** Continuations used will grow and shrink but all calls will be tail calls. – Will Ness Aug 05 '12 at 23:37
  • @AndreyT why demand O(1) memory for the replacement of O(x) memory? Any non-tail recursive program will have *some* memory usage; the transformation ought to *preserve* it, i.e. not to add new complexity. But you simply can not demand it reduce complexity which is inherent to the algorithm, not its syntactic forms. Tail or not tail, is a matter of syntax. Whatever information is hidden on the call stack spread among call frames by the complex recursive function, can be made explicit, moved onto heap, maintained explicitly, enabling tail call re-write. – Will Ness Aug 06 '12 at 00:38
  • 1
    @AndreyT you say "a valid way to turn recursive algorithm onto a tail-recursive or iterative one" but the two concepts are not the same at all. you conflate tail recursion as a syntactic property of a code with the process described by that code being iterative or not. you're absolutely right, TR code can describe a recursive, i.e. no-iterative process. but the question was about re-writing of code. this re-write is syntactical, it does not change the nature of the algorithm at hand. double-rec fibonacci can be made linear, but that is *algorithmic* change, rearranging the information flow. – Will Ness Aug 06 '12 at 07:38
3

Yes you can. The transformation usually involves maintaining the necessary information explicitly, which would otherwise be maintained for us implicitly spread among the execution stack's call frames during run time.

As simple as that. Whatever the run time system does during execution implicitly, we can do explicitly by ourselves. There's no big mystery here. PCs are made of silicon and copper and steel.

It is trivial to implement DFS as a loop with explicit queue of states/positions/nodes to process. It is in fact defined that way - DFS replaces the popped first entry in the queue with all the arcs coming from it; BFS adds these arcs to the end of the queue.

The continuation-passing style transformation leaves all the function calls in a program as tail calls after it is done. This is a simple fact of life. The continuations used will grow and shrink, but calls will all be tail calls.

We can further reify the state of process spread in continuations, as explicitly maintained data on the heap. What this achieves in the end, is explication and reification, moving implicit stuff on stack to the explicit stuff living in the heap, simplifying and demystifying the control flow.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Does this lose the optimizations the OP mentions? – Reinstate Monica Aug 06 '12 at 00:08
  • @WolframH what optimizations? he doesn't mention any. he says he thinks it is an optimization, and it is. it explicates things, moving implicit things hidden on the stack among call frames, into the open, on heap. This exactly makes explicit the information buildup which he mentions. i.e. when the information from recursive call down the chain is needed by the upper level calls, it is usually coded as non-tail recursive; but that information flow can be made explicit, and control flow turned into iterative. – Will Ness Aug 06 '12 at 00:14
2

I don't know if all recursive functions can be rewritten to be tail-recursive, but many of them can. One standard method of doing this is to use an accumulator. For example, the factorial function can be written (in Common Lisp) like so:

(defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (1- n)))))

This is recursive, but not tail recursive. It can be made tail-recursive by adding an accumulator argument:

(defun factorial-accum (accum n)
   (if (<= n 1)
       accum
       (factorial-accum (* n accum) (1- n))))

Factorials can be calculated by setting the accumulator to 1. For example, the factorial of 3 is:

(factorial-accum 1 3)

Whether all recursive functions can be rewritten as tail-recursive functions using methods like this isn't clear to me, though. But certainly many functions can be.

River
  • 1,504
  • 13
  • 21
  • the perceived problem is not with singly-recursive processes like the factorial calculation, but with doubly-recursive processes like binary tree traversal. Tail call or not is a feature of syntax, not of algorithm. – Will Ness Aug 05 '12 at 23:45
  • That interpretation of the question is in now way obvious. – River Aug 06 '12 at 06:17
  • did you mean to say "in no way obvious"? My interpretation of the question is straightforward. It asks, can any recursive code be written as tail-recursive code. TR code is a matter of syntax - whether all function calls it makes that can lead to it being called again are in tail position. TR code may not get optimized, if the implementation does not apply TCO. TR code with TCO applied can run in constant stack, that's all that is claimed about TCO. the re-write of singly-recursive code like `factorial` is simple, is what I meant, for doubly-recursive code it is more involved. – Will Ness Aug 06 '12 at 07:17
2

Recursive algorithm is an algorithm that implemented in accordance with Divide & Conquer strategy, where solving each intermediate sub-problem produces 0, 1 or more new smaller sub-problems. If these sub-problems are solved in LIFO order, you get a classic recursive algorithm.

Now, if your algorithm is known to produce only 0 or 1 sub-problem at each step, then this algorithm can be easily implemented through tail recursion. In fact, such algorithm can easily be rewritten as an iterative algorithm and implemented by a simple cycle. (Needless to add, tail recursion is just another less explicit way to implement iteration.)

A schoolbook example of such recursive algorithm would be recursive approach to factorial calculation: to calculate n! you need to calculate (n-1)! first, i.e. at each recursive step you discover only one smaller sub-problem. This is the property that makes it so easy to turn factorial computation algorithm into a truly iterative one (or tail-recursive one).

However, if you know that in general case the number of sub-problems generated at each step of your algorithm is more than 1, then your algorithm is substantially recursive. It cannot be rewritten as iterative algorithm, it cannot be implemented through tail recursion. Any attempts to implement such algorithm in iterative or tail-recursive fashion will require additional LIFO storage of non-constant size for storing "pending" sub-problems. Such implementation attempts would simply obfuscate the unavoidable recursive nature of the algorithm by implementing recursion manually.

For example, such simple problem as traversal of a binary tree with parent->child links (and no child->parent links) is a substantially recursive problem. It cannot be done by tail-recursive algorithm, it cannot be done by an iterative algorithm.

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • You missed 'immutable' from the constraints for your binary tree traversal, otherwise it is possible using a well known approach http://stackoverflow.com/a/791378/1527 – Pete Kirkham Aug 02 '12 at 11:15
  • for *some*, tail recursion is *more* explicit and natural way to express iteration than countless varying loop constructs. :) – Will Ness Aug 05 '12 at 23:26
  • what's wrong with maintaining LIFO storage explicitly which would otherwise be maintained implicitly on call stack frames for us? Potato, potato. Complexity isn't added by that transformation, it is *inherent* to the algorithm at hand itself. And traversal of immutable binary tree is easily done ***in a loop*** with explicit stack of nodes-to-visit. – Will Ness Aug 05 '12 at 23:33
  • @Will Ness: There's nothing "wrong" with that. It is just that it doesn't produce an iterative algorithm. Just because you used a "loop" in your code, does not mean that you magically found an iterative algorithm. As long as your algorithm follows D&C strategy with additional storage for pending tasks, your algorithm is *recursive*, period. How you implement it doesn't really matter. A parent->child tree is a classic example of a *recursive* data structure, which is why any traversal algorithm will be *recursive*. There's no way around it. – AnT stands with Russia Aug 06 '12 at 05:21
  • 1
    Meanwhile, "tail recursion" is a term that refers to a specific optimization strategy, not just an algorithm that happen to invoke itself at the end. One of the requirements of that optimization strategy is static storage size. Dynamically sized continuation is a non-solution. – AnT stands with Russia Aug 06 '12 at 05:24
  • @AndreyT iterative *process* is one that can run indefinitely. but this was not the question. the question was about syntax: can any recursive code be re-written as tail-recursive code. the answer is still yes. TCO can be applied to any tail recursive code to make it run in constant *stack* space. It says nothing about data size, or the nature of the running process, whether it is iterative or not. a loop by definition runs in constant stack. – Will Ness Aug 06 '12 at 06:34
  • @AndreyT so we just read the question differently. you also read my comments differently than what I intended. I never claimed to reduce the complexity of the algorithm, I explicitly argue that it stays the same regardless. – Will Ness Aug 06 '12 at 06:41
  • Great point, a tail-recursive function is a fully iterative construct. It's really just a loop at that point, no stack is being used. But there's times where you need only a little more then the previous result, like maybe you only need the last two, not everyone of them, so you don't need a full stack, and it's a recursive solution, but pragmatically, you don't want a stackoverflow, and so you can sill use tail-recursion while carrying over just what is needed. – Didier A. Jun 11 '16 at 14:08
-1

No it can be done "naturally" only for calls with one recursive call. For two or more recursive calls you can of course mimic stack frame yourself. But it will be very ugly and will effectively won't be tail recursive, in the sense of optimizing memory.

The point with tail-recursion is you don't want to come back to parent stack. So simply pass on that information to child stack which can completely replace parent stack, instead of stack growing.

Fakrudeen
  • 5,778
  • 7
  • 44
  • 70
  • 2
    Sorry, this is simply false. It is a fact that all programs can be rewritten as tail calls using continuations. – Pete Kirkham Aug 01 '12 at 21:04
  • @Pete - while using constant memory? That's the question. – Fakrudeen Aug 02 '12 at 07:29
  • 1
    It wasn't the question asked. I've added a comment, but having written interpreters and compilers using CPS there is no problem using continuations to transform any recursive algorithm into a tail call one *with the same space requirements*. If your recursive algorithm was constant memory, then the CPS tail call version will be. If it consumed 'stack' space, the CPS tail call version will consume a similar amount of 'heap' space. – Pete Kirkham Aug 02 '12 at 10:51
  • @PeteKirkham - if it takes the same memory why bother? – Fakrudeen Aug 03 '12 at 06:14
  • 2
    In compilers, rewriting everything to tail calls means you only have to write your optimisations for one form of control flow. In actor based languages, having explicit continuations means you can create massive concurrency. In garbage collected environments, it means you don't have to treat the stack and heap differently, and can reclaim stack space as part of normal gc. In environments where the stack size is smaller than the heap, you can operate on more deeply nested constructs. – Pete Kirkham Aug 03 '12 at 09:50