Using continuation to transform binary recursion to tail recursion

Question

As I'm reading the Programming F# book, I found the 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)
      -> f x
        processSteps (getNext())

  processSteps steps

By using continuation, the binary recursion of traversing a binary has been transformed to tail-recursive function processSteps. My question is that the other function, linearize seems to be non-tail-recursive. Does that mean we are not able to transform a binary-recursion to a tail-recursion completely even using continuation?

Answer 1

linearize is tail-recursive: you don't need to come back from the recursive call to continue the computation.

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

doesn't call linearize. The computation is suspended until processSteps calls getNext ().