Take the 2-minute tour ×

Tail recursion is an important performance optimisation stragegy in functional languages because it allows recursive calls to consume constant stack (rather than O(n)).

Are there any problems that simply cannot be written in a tail-recursive style, or is it always possible to convert a naively-recursive function into a tail-recursive one?

If so, one day might functional compilers and interpreters be intelligent enough to perform the conversion automatically?

share|improve this question
I disagree that tail recursion is a performance optimisation. It has to do with correctness: Programming in a language without this, prevents you from handling unbounded repetition with recursion, whereas in languages with this feature, you are free to use recursion (with certain constraints) for unbounded repetition. This is an important point: The (guaranteed) presence of tail-recursion changes the semantics of the language. –  harms Dec 11 '09 at 15:36
How does it change the semantics? The same abstract computation is being described in either case. The time and space complexity of the resulting code is arguably an implementation detail, albeit an important one if you expect to actually run the program. –  C. A. McCann Dec 11 '09 at 17:22
I should perhaps have qualified that it changes the semantics if you have a static stack, which I understand is the normal case, e.g. with Java you can pass a paramater at startup for the jvm as to how big the stack should be, but the stack cannot grow and grow until the machine's memory is used up. You speak of the abstract computation, and you are in a sense correct, but this is a classic example of a "leaky abstraction": The underlying implementation exerts itself, and without a guarantee for tail-calls, the programmer cannot rely on them. –  harms Dec 11 '09 at 17:55
add comment

5 Answers

up vote 24 down vote accepted

Yes, actually you can take some code and convert every function call—and every return—into a tail call. What you end up with is called continuation-passing style, or CPS.

For example, here's a function containing two recursive calls:

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))

And here's how it would look if you converted this function to continuation-passing style:

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

The extra argument, ctn, is a procedure which count-tree-cps tail-calls instead of returning. (sdcvvc's answer says that you can't do everything in O(1) space, and that is correct; here each continuation is a closure which takes up some memory.)

I didn't transform the calls to car or cdr or + into tail-calls. That could be done as well, but I assume those leaf calls would actually be inlined.

Now for the fun part. Chicken Scheme actually does this conversion on all code it compiles. Procedures compiled by Chicken never return. There's a classic paper explaining why Chicken Scheme does this, written in 1994 before Chicken was implemented: CONS should not cons its arguments, Part II: Cheney on the M.T.A.

Surprisingly enough, continuation-passing style is fairly common in JavaScript. You can use it to do long-running computation, avoiding the browser's "slow script" popup. And it's attractive for asynchronous APIs. jQuery.get (a simple wrapper around XMLHttpRequest) is clearly in continuation-passing style; the last argument is a function.

share|improve this answer
I don't know if this was the best answer to the question, but it was by far the most informative answer. +1 –  Imagist Dec 12 '09 at 1:15
It's easier to think of transforming a language with goto and no procedure calls into one with only tail-recursive calls: i.e. each goto, besides the first, becomes a procedure invocation followed by an end. It's the transformation that lies behind Dijkstra's GOTO considered harmful. –  Charles Stewart Dec 14 '09 at 8:57
Shouldn't count-tree-cps contain nested calls to itself, rather than count-tree? –  Nate Kohl Nov 4 '11 at 15:00
Yep. Fixed. . . . –  Jason Orendorff Nov 15 '11 at 12:04
add comment

It's true but not useful to observe that any collection of mutually recursive functions can be turned into a tail-recursive function. This observation is on a par with the old chestnut fro the 1960s that control-flow constructs could be eliminated because every program could be written as a loop with a case statement nested inside.

What's useful to know is that many functions which are not obviously tail-recursive can be converted to tail-recursive form by the addition of accumulating parameters. (An extreme version of this transformation is the transformation to continuation-passing style (CPS), but most programmers find the output of the CPS transform difficult to read.)

Here's an example of a function that is "recursive" (actually it's just iterating) but not tail-recursive:


In this case the multiply happens after the recursive call. We can create a version that is tail recursive by putting the product in an accumulating parameter:

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

The inner function f is tail-recursive and compiles into a tight loop.

I find the following distinctions useful:

  • In an iterative or recursive program, you solve a problem of size n by first solving one subproblem of size n-1. Computing the factorial function falls into this category, and it can be done either iteratively or recursively. (This idea generalizes, e.g., to the Fibonacci function, where you need both n-1 and n-2 to solve n.)

  • In a recursive program, you solve a problem of size n by first solving two subproblems of size n/2. Or, more generally, you solve a problem of size n by first solving a subproblem of size k and one of size n-k, where 1 < k < n. Quicksort and mergesort are two examples of this kind of problem, which can easily be programmed recursively, but is not so easy to program iteratively or using only tail recursion. (You essentially have to simulate recursion using an explicit stack.)

  • In dynamic programming, you solve a problem of size n by first solving all subproblems of all sizes k, where k<n. Finding the shortest route from one point to another on the London Underground is an example of this kind of problem. (The London Underground is a multiply-connected graph, and you solve the problem by first finding all points for which the shortest path is 1 stop, then for which the shortest path is 2 stops, etc etc.)

Only the first kind of program has a simple transformation into tail-recursive form.

share|improve this answer
some run time environments have very limited stack space and unlimited heap memory, so yes, it is useful to know how to convert any code to tail-recursive code, there. –  Will Ness Aug 7 '12 at 7:30
add comment

Any recursive algorithm can be rewritten as an iterative algorithm (perhaps requiring a stack or list) and iterative algorithms can always be rewritten as tail-recursive algorithms, so I think it's true that any recursive solution can somehow be converted to a tail-recursive solution.

(In comments, Pascal Cuoq points out that any algorithm can be converted to continuation-passing style.)

Note that just because something is tail-recursive doesn't mean that its memory usage is constant. It just means that the call-return stack doesn't grow.

share|improve this answer
-1: Not all recursive methods can be made tail-recursive. See my answer for an example. –  Benoit Dec 11 '09 at 15:21
You can write an iterative tree-traversal algorithm by using a stack. –  Kristopher Johnson Dec 11 '09 at 15:22
I meant consume constant stack. Thanks for pointing out my mistake. –  ctford Dec 11 '09 at 15:22
@Ben S: "in CPS [...] every call is a tail call." See it for yourself in context: en.wikipedia.org/wiki/Continuation-passing_style –  Pascal Cuoq Dec 11 '09 at 15:34
@Ben S: sorry, but you're answer is wrong. Tail-recursive tree traversal and insertion is easy to write using continuation passing. See the following urls: stackoverflow.com/questions/833180/handy-f-snippets/… and fortysix-and-two.blogspot.com/2009/06/… –  Juliet Dec 11 '09 at 22:15
show 2 more comments

You can't do everything in O(1) space (space hierarchy theorem). If you insist on using tail recursion, then you can store the call stack as one of the arguments. Obviously this doesn't change anything; somewhere internally, there is a call stack, you're simply making it explicitly visible.


Such conversion will not decrease space complexity.

As Pascal Cuoq commented, another way is to use CPS; all calls are tail recursive then.

share|improve this answer
add comment

I don't think something like tak could be implemented using only tail calls. (not allowing continuations)

share|improve this answer
add comment

Your Answer


