The Little Schemerの第三の戒めは次のように述べています。
リストを構築するときは、最初の典型的な要素を記述し、それを自然再帰にコンスします。
「自然再帰」の正確な定義は何ですか? 私が質問している理由は、ダニエル・フリードマンによるプログラミング言語の原則に関するクラスを受講していて、次のコードは「自然に再帰的」とは見なされないためです。
(define (plus x y)
(if (zero? y) x
(plus (add1 x) (sub1 y))))
ただし、次のコードは「自然に再帰的」と見なされます。
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
私は「不自然に再帰的」なコードの方が好きです。ただし、そのようなコードは忌み嫌われるものと見なされます。関数を末尾再帰形式で記述すべきではない理由を尋ねると、副講師は単に「自然再帰を台無しにするな」と答えました。
「自然に再帰的な」形式で関数を書くことの利点は何ですか?
「自然な」(または単に「構造的な」) 再帰は、学生に再帰について教え始める最良の方法です。これは、Joshua Taylor が指摘する素晴らしい保証があるためです。終了することが保証されています[*]。学生は、この種のプログラムに頭を悩ませるのに十分な時間を費やしているため、これを「ルール」にすることで、壁にぶつかって頭をぶつけることを大幅に減らすことができます。
構造的再帰の領域を離れることを選択した場合、プログラマーは追加の責任を負うことになります。つまり、すべての入力でプログラムが停止するようにすることです。考えて証明することはもう1つあります。
あなたの場合、それはもう少し微妙です。2 つの引数があり、2 番目の引数に対して構造的に再帰的な呼び出しを行っています。実際、この観察 (プログラムは引数 2 で構造的に再帰的である) から、元のプログラムは、同じ収束の証明を継承しているため、非末尾呼び出しプログラムとほぼ同じくらい正当であると主張できます。これについてダンに聞いてください。私は彼が何を言わなければならないか興味があります。
[*] ここで正確に言うと、終了しない他の関数の呼び出しなど、あらゆる種類の間抜けなものを法制化する必要があります。
自然再帰は、扱っている型の「自然な」再帰的定義に関係しています。ここでは、自然数を扱っています。「明らかに」自然数はゼロまたは別の自然数の後継であるため、自然数を構築する場合は、自然に出力する0か、たまたま再帰的に計算される(add1 z)他の自然数を出力します。z
教師はおそらく、再帰型定義とその型の値の再帰処理との間のリンクを作成することを望んでいます。ツリーやリストを処理しようとしても、数で発生するような問題は発生しません。なぜなら、自然数を「不自然な方法」で日常的に使用しているため、教会の数字の観点から考えると自然に異議を唱える可能性があるからです。
末尾再帰関数の書き方を既に知っているという事実は、その文脈では無関係です。これは、少なくとも今のところ、末尾呼び出しの最適化について話す教師の目的ではないようです。
アソシエイト インストラクターは最初はあまり役に立ちませんでしたが (「自然再帰をいじる」は「聞かないで」のように聞こえます)、あなたが提供したスナップショットで彼/彼女が提供した詳細な説明はより適切でした。