2

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?

asked Jul 17, 2014 at 18:41

2 Answers 2

6

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)
answered Jul 17, 2014 at 18:51
4

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)

answered Jul 17, 2014 at 18:47
1
  • 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. Commented Jul 17, 2014 at 19:09

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.