Using continuation to convert binary recursion to tail recursion

Question

When I read the F # programming book, I found an example code snippet on page 195 as follows:

type ContinuationStep<'a> = | Finished | Step of 'a * (unit -> ContinuationStep<'a>) let iter f binTree = let rec linearize binTree cont = match binTree with | Empty -> cont() | Node(x, l, r) -> Step(x, (fun () -> linearize l (fun() -> linearize r cont))) let steps = linearize binTree (fun () -> Finished) let rec processSteps step = match step with | Finished -> () | Step(x, getNext) -> fx processSteps (getNext()) processSteps steps 

Using a sequel, the binary recursion traversal of a binary file has been converted to the tail recursive function processSteps . My question is, another linearize function seems non-tail-recursive. Does this mean that we cannot completely convert binary recursion to tail recursion even with continuation?

Answer 1

The example is a bit subtle because it does not use regular extensions, but instead builds a structure that can be evaluated step by step. In the place where you usually make a recursive call, it returns a Step value that contains the function that you (recursively) call.

In the second case, the linearize function returns Step , containing a function that will call linearize recursively, but not immediately make a recursive call. Thus, the function does not make a recursive call (it just stores a recursive link).

It only makes sense to think about whether the program is tail-recursive when you look at processSteps because it makes the actual loop - and it is tail-recursive as it executes Step by Step without saving stack space for each Step .

If you want to build a list instead of a chain of lazy steps, you will need to make a linearize recursive call right inside the continuation:

 let rec linearize binTree cont = match binTree with | Empty -> cont [] | Node(x, l, r) -> linearize l (fun l -> linearize r (fun v -> cont (x::v))) 

This is essentially the same as the previous function, but actually calls linearize instead of building a Step containing a function that will call linearize .

Answer 2

linearize is tail recursive: you do not need to return from a recursive call to continue the calculation.

 fun () -> linearize l (fun() -> linearize r cont) 

does not call linearize . The calculation is suspended until processSteps calls getNext () .