Can all recursive functions be re-written as tail-recursions?

Question

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?

Solution 1

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").

Solution 2

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.

Solution 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.

Solution 4

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.

Solution 5

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.

View more solutions