5
$\begingroup$

Can any method that uses recursion be written as tail-recursion?

$\endgroup$
  • 5
    $\begingroup$ Could you make your question more precise? Are you asking if every program can be rewritten so all recursive calls are tail recursions? If so, yes: you can rewrite the program so there are no recursions at all. Are you asking if every instance of recursion can be implemented by the compiler as tail recursion? If so, no: only recursive calls that are the last thing a function does before returning can be implemented as tail calls. $\endgroup$ – David Richerby Apr 23 '15 at 20:50
  • $\begingroup$ @DavidRicherby Doesn’t saying no to“ every instance of recursion can be implemented by the compiler as tail recursion” contradict “every program can be rewritten so all recursive calls are tail recursions”? Can you give an example to “only recursive calls that are the last thing a function does before returning can be implemented as tail calls”? $\endgroup$ – Glide Apr 23 '15 at 22:07
  • 1
    $\begingroup$ My understanding of @DavidRicherby is that when there is no recursion at all, all recusive call are tail recursive, and also painted blue with a straw hat. Regarding the other statement, one cannot give an example of something that is not possible ... well, except with higher order functions as used in denotational semantics, which is what Wandering Logic is proposing. But can it really be called compiling without any stretch of the imagination? And he would not do it exactly the same for a tail call anyway. $\endgroup$ – babou Apr 23 '15 at 22:21
  • 1
    $\begingroup$ Do you know how recursion is actually implemented, what kind of code is produced by the compiler, and how memory is managed? If you do not, that is the first thing you should worry about ... and learn. When you understand that, the issue will become much clearer to you. I do give you in my answer the basic reason that distinguishes tail recursion from other recursion, when compiling. But it is related to memory management on a stack, to preserve local variables of each call (until it returns), which is the foundation of the story. $\endgroup$ – babou Apr 23 '15 at 22:30
  • $\begingroup$ @babou: I learned denotational semantics once, about 20 years ago, and then promptly forgot it. What I was describing was how the Scheme compilers I've worked with actually work. The analysis and transformation rules for cps are also pretty similar to the way that the C compilers I've worked with make return addresses explicit on the stack. I called it "compiling" because, in my experience, it is "what compilers do." $\endgroup$ – Wandering Logic Apr 23 '15 at 22:54
5
$\begingroup$

You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call is a tail call (just not necessarily a tail recursive call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point. Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point. Continuation-passing style essentially makes the stack explicit. Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

Example

procedure depth_first(t):
  if not-null(t):
    l = depth_first(t->left)
    r = depth_first(t->right)
    return l + r + 1
  else:
    return 0

The first step is to make every procedure take an extra parameter, k which is a continuation procedure (a procedure which you return to by calling it with the return value as its parameter). Then you turn the procedure "inside out":

procedure depth_first(t, k):
  if not-null(t):
    depth_first(t->left,
       lambda(l):
         depth_first(t->right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)

Should you do it? Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes. Otherwise probably not. One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand. Let the compiler do what it's best at and concentrate on writing maintainable code.

$\endgroup$
  • $\begingroup$ How come recursive calls can't be written as tail recursive calls? Also, are you suggesting you shouldn't rewrite a recursive call to tail recursive because tail recursive calls are worse in readability? $\endgroup$ – Glide Apr 23 '15 at 22:16
  • $\begingroup$ If your algorithm needs a stack it needs a stack. "tail recursion" usually refers to the circumstance that you can do the call without growing the stack. cps makes recursive calls be "the last call", but does that by pushing a bunch of lambdas on the stack. Also I did not say anything about the readability of tail recursive calls. I said something about the readability of code written in continuation-passing style. $\endgroup$ – Wandering Logic Apr 23 '15 at 22:20
-1
$\begingroup$

Good practice, however understood, does have various style implications, and encourages some programming paradigms over others, but I do not know that using tail recursion is part of it. Some people do prefer recursive style for various reasons, and that may result in a lot of tail recursion. That used to be very common in languages like Lisp or Scheme, and their programmers were probably the first to notice the issue below.

Tail recursion was identified originally (afaik) as a situation where compilers could speed up execution by replacing them by a loop, and saving on stack management. It is only what the name says: a tail recursion, i.e. a recursive call that is the last thing done by the function before returning.

It is a property of the source code. Object code does not have recursion (other than possibly for high level virtual machines, not for tangible hardware), only loops and memory management. Thus no implementation of anything is written as recursion of any kind, including tail recursion.

If that sentence was supposed to ask whether a non-tail recursion can be compiled in the same way as a tail recursion is compiled, the answer is no because non-tail recursion requires preserving existing execution environments (so-called activation blocks) on the stack (usually), for whatever code remains to be executed on return. Only tail recursion can avoid that, since it will not have anything to do on return (well, it is the general idea, some details are skipped).

Of course, all recursions can be transformed into loops with some effort. That is precisely what the compiler does, since object code has no recursion. Then the program has no recursions that are not tail recursions, not having any at all (as David Richerby remarked). Furthermore, translating back in a language rich enough, a loop can be replaced by a tail recursion (skipping many details), so that you can have it all with tail recursion. But it does you no good. It is only an intellectual exercise.

I cannot say this reply was not influenced by David Richerby very good comment.

$\endgroup$
  • 2
    $\begingroup$ Tail recursion implements the recursive function call as (essentially) a jump, rather than pushing things onto the stack, jumping and popping things off the stack on return. The generated code looks somewhat like a loop but I wouldn't say that the compiler is replacing recursion with a loop per se. (BTW, the downvote isn't mine.) $\endgroup$ – David Richerby Apr 24 '15 at 8:53
-1
$\begingroup$

Given the amount of wrong info dispensed in the other answers, I strongly invite you [collectively] to read Specification and Transformation of Programs by Helmut A. Partsch; it addresses the topic at length in Chapter 6. Transforming programs (say to turn recursion into tail recursion) is alas not a topic commonly covered in other textbooks.

Briefly: You can turn any function that uses recursion into one that uses only tail recursion. The result may not be very pretty to read though; it's akin to removing a goto, i.e. you will need to encode control decisions as predicates.

If I have time, I'll expand on these points, but realistically it won't happen this weekend.

$\endgroup$
  • $\begingroup$ Before being so harsh on the other answers, you should note that they were writtenwhen the question was extremely vague: "Can any recursion implementation be written as tail-recursion?" It's unclear whether that means, for example, "Can any recursive program be rewritten to involve only tail recursion?" (as I said in the comments, yes, vacuously, by eliminating recursion altogether) or "Can a compiler implement every recursive call as a tail call?" (no) or something else entirely. $\endgroup$ – David Richerby Apr 24 '15 at 8:49
  • $\begingroup$ Interesting. I thought the cps (continuation passing style) transformation I tried to describe in my answer was pretty much the standard way of explicitly turning calls into jumps. What is it missing? How does encoding control decisions as predicates help? Can you at least give us a reference to the paper(s) that Partsch covers in Chapter 6? I don't have access to the book. $\endgroup$ – Wandering Logic Apr 24 '15 at 12:09
  • $\begingroup$ AFAIK, @WanderingLogic's answer is correct. $\endgroup$ – fpbhb Apr 25 '15 at 21:11
  • 1
    $\begingroup$ The statement that “You can turn any function that uses recursion into one that uses only tail recursion” is misleading. It takes more than tail recursion to emulate general recursion: you also need to pass the stack around as a parameter to the function — effectively continuation-passing style. General recursion effectively provides a storage stack, whereas tail recursion operates in constant stack space. In particular, in a language where each function argument encodes a finite amount of information, going from general recursion to tail recursion makes the language no longer Turing-complete. $\endgroup$ – Gilles 'SO- stop being evil' Apr 26 '15 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.