Are there problems that cannot be written using tail recursion?

Solution 1:

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

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.

Solution 2:

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:

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

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.

Solution 3:

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.

Solution 4:

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.

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

Such conversion will not decrease space complexity.

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

Solution 5:

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