これをtail-recursiveにするにはどうすればいいですか？

Question

私はこのコードを持っている：

(define (prog1 x y) 
    (let ([rel (related x y)]) 
     (cond 
     [(null? rel) (list x)] 
     [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))]))) 

私が何をしたいのかを試してみて、それが末尾再帰にするです。私は私のような何かをする必要があることを知っている：

(define (prog1 x y) 
    (prog1-iter x y `())) 

(define (prog1-iter x y acc) 
    (... 
    )) 

をしかし、私は、このコードに私のコードから行くことが方法がわからないよ...私は、元はそれにマップを持っているので、それはだと思うし、私はどのようにわかりませんよこれをprog1-iterに組み込みます。誰かが正しい方向に私を向けることができます！

Answer 1

テール再帰は本質的に反復的なものに対しては簡単に書くことができます。あなたの関数は潜在的にそれ自身を何度も呼び出すので、単純ではありません。それにもかかわらず、どのプログラムも繰り返し実行することができます（たとえば、コンピュータは巨大な反復マシンです）。

まず、あなたの関数はで直接（すなわちprog1は自分自身を直接呼び出さない）ではありません。むしろ、prog1はmapを呼び出し、あなたが与えたラムダを呼び出します（おそらく何回か）。その後、prog1が呼び出されます。それは間接的です。 mapへのコールはテールコールではありません。 mapからラムダへのコールは確かにテールコールではありません（複数回呼び出す必要があるかもしれません）。ラムダからprog1へのコールはテールコールです。

したがって、「尾を再帰的」とするときには、正確に何が必要なのかよくわかりません。 prog1からの一連のコールの各コールを自分自身にテールコールさせますか？あるいは、プログラム内のすべてのコールをテールコールにしたいですか？そこmapの「末尾再帰」のバージョンが存在するが、それらは、マッピング関数の呼び出しmapからmapへの呼び出しに関してのみ「末尾再帰であり、ではないので、彼らはあなたのケースのために有用ではない。

プログラム内のすべての呼び出しを末尾呼び出しにする一般的な方法は、continuation-passing styleと呼ばれます。基本的に、すべての関数は追加の関数引数、「継続」を取ります。基本的に、継続は、非テールコールの後の元の関数の "残りの部分"を包含し、それは "返された結果"を取ることになります。引数としての元の非テールコール。私はyを変換する方法を練習として残しますCPSへの私たちのプログラム