General recursion to tail-recursion

Question

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?

Answer 1

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)

Answer 2

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