次のように私はプログラミングのF＃の本を読んでいたよう末尾再帰

Question

にバイナリ再帰を変換するために継続を使って、私は195ページの例のコードスニペットを見つけました：

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 

継続を使用することにより、トラバースのバイナリ再帰バイナリはテール再帰関数processStepsに変換されています。私の質問は、他の関数、linearizeは非テール再帰的であるようです。これは、バイナリ再帰を末尾再帰に完全に変換することができないことを意味しますか？

Answer 1

この例は、通常の継続を使用しないため、少しずつ微妙ですが、代わりに段階的に評価できる構造を構築しています。通常、再帰呼び出しを行う場所では、（再帰的に）呼び出す関数を含む値Stepを返します。第2のケースで

、linearize関数が再帰的にlinearizeを呼び出す関数を含むStepを返しますが、それはすぐに再帰呼び出しをしないありません。したがって、関数は再帰呼び出しを行いません（再帰参照を格納するだけです）。

それが実際のループを行いますので、それだけで、あなたがprocessStepsを見たときにプログラムは末尾再帰であるかどうかを検討することは理にかなって - そしてそれはそれぞれのスタック空間を維持することなく、StepでStepを実行するため、それは、末尾再帰でありますStep。

あなたの代わりに怠惰なステップのチェーンのリストを作成したい場合、あなたはすぐに継続内linearizeに再帰呼び出しを行う必要があるだろう：

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

これは、基本的に以前と同じです実際にはlinearizeを呼び出す関数を含むStepをビルドする代わりにlinearizeを呼び出します。

Answer 2

linearizeはtail-recursiveです。計算を続けるために再帰呼び出しから戻ってくる必要はありません。

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

linearizeを呼び出しません。 processStepsがgetNext()になるまで計算が中断されます。