General recursion to tail-recursion

Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.

My view is that it's not possible everytime. For example if you have a function which calls itself recursively twice or three times, then you can't make all the recursive calls into tail-calls, right? Or is there always a way to reduce the number of recursive calls to one single recursive call?

You should be able to do it using continuation passing style.

In CPS, each function takes an explicit continuation function which represents the rest of the computation. Instead of returning a value directly, a function in CPS passes the result to the continuation instead.

For example if you had the following Tree data type:

type Tree = Empty | Node of Tree * int * Tree

and you wanted to sum the values, you could write function to sum the left and right subtrees in turn:

let rec sum_cps t f =
match t with
| Empty -> f 0
| Node(l, v, r) -> sum_cps l (fun lv ->
sum_cps r (fun rv -> f (lv + v + rv)))

let sumT t = sum_cps t (fun i -> i)

You can do that transformation using Continuation Passing Style.

Read for instance A.Appel Compiling with Continuations book

Intuitively, you replace -after CPS transformation- (nearly) each call frame of the call stack with a heap-allocated continuation frame (or "closure" when viewing continuations as functions). (so you might not win much: the avoided stack frames are replaced by garbage collected continuation frames).

See also Appel's old paper: garbage collection can be faster than stack allocation

(which might be less true today, perhaps because of cache issues)

• Oh course the downside is that you build lots and lots of closures (the continuations). It's not a good way to improve performance or memory use. – user7043 Jul 17 '14 at 19:09