Are there problems that cannot be written using tail recursion?

Question

Tail recursion is an important function of optimizing performance in functional languages, as it allows recursive calls to consume a constant stack (rather than O (n)).

Are there any problems that simply cannot be written in a tail-recursive style or can you always convert a naive-recursive function into a tail-recursive one?

If so, can one day functional compilers and interpreters be smart enough to automatically convert?

Answer 1

Yes, in fact you can take some kind of code and convert every function call - and every return - into a tail call. What you are finishing is called a continuation-pass style or CPS.

For example, here is a function containing two recursive calls:

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

And here is what it would look like if you converted this function to a continuation 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 (+ LR)))))) (ctn 1))) 

The optional ctn argument is a procedure in which count-tree-cps tail calls instead of returning. (sdcvvc answers that you cannot do everything in O (1) space, and rightly so, here each continuation is a closure that takes up some memory.)

I did not convert calls in car or cdr or + to tail calls. This could also be done, but I assume that these leaf calls will indeed be inline.

Now for the fun part. Chicken Scheme actually performs this conversion on all compiled code. The procedures compiled by the Chicken never return. There's a classic article explaining why Chicken Scheme does this, written in 1994 before Chicken was implemented: CONS should not contradict its arguments. Part II: Cheney on the MTA

Surprisingly, the style of continuing the passage is quite common in JavaScript. You can use it to perform lengthy calculations by avoiding the browser browser "slow script" popup. And this is attractive for asynchronous APIs. jQuery.get (a simple wrapper around XMLHttpRequest) is clearly in a continuation style; the last argument is a function.

Answer 2

It is 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 par with the old chestnut of the 1960s, that control flow designs can be eliminated, because each program can be written as a loop with a case embedded in it.

It is useful to know that many functions that are not explicitly tail-recursive can be converted to tail-recursive form by adding cumulative parameters. (The latest version of this conversion is a transition to the Continuing Pass (CPS) style, but most programmers find the result of the CPS conversion difficult to read.)

Here is an example of a function that is “recursive” (in fact, it just repeats itself), but is not tail recursive:

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

In this case, the multiplication occurs after a recursive call. We can create a tail recursive version by putting the product in the cumulative parameter:

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

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

---

I find the following differences useful:

• In an iterative or recursive program, you solve a problem of size n by first solving one subproblem of size n-1 . The calculation of the factor function falls into this category, and this can be done either iteratively or recursively. (This idea generalizes, for example, 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 resolving two sub-tasks of size n/2 . Or, more generally, you solve a problem of size n first resolving a subtask of size k and one of sizes nk , where 1 < k < n . Quicksort and mergesort are two examples of these kinds of problems that can be easily programmed recursively, but the program is not so simple iteratively or using only tail recursion. (You should essentially mimic recursion using an explicit stack.)

• In dynamic programming, you solve a problem of size n by first resolving all subtasks 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 the points for which the shortest path is 1 stop, then for which the shortest path is 2 stops, etc. etc.)

Only the first type of program has a simple conversion to the tail-recursive form.

Answer 3

Any recursive algorithm can be rewritten as an iterative algorithm (perhaps a stack or a list is required), and iterative algorithms can always be rewritten as tail-recursive algorithms, so I believe that any recursive solution can somehow be converted to tail-recursive decision.

(In the comments, Pascal Quoc points out that any algorithm can be converted to a continuation style .)

Please note that just because something is tail recursive does not mean that its memory usage is permanent. It just means that the callback stack is not growing.

Answer 4

You cannot do everything in O (1) space (spatial hierarchy theorem). If you insist on using tail recursion, you can save the call stack as one of the arguments. Obviously, this does not change anything; somewhere inside, there is a call stack, you just make it clearly visible.

If so, can one day functional compilers and interpreters be smart enough to automatically convert?

Such a transformation will not reduce spatial complexity.

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

Answer 5

I don't think that something like tak can be implemented using only tail calls. (not allowing continuation)