「自然再帰」の定義は何ですか?

2015年08月28日に質問されました。  ·  閲覧回数 4.4k回  ·  ソース

Aadit M Shah picture
2015年08月28日

リトルスキームの第三戒

リストを作成するときは、最初の典型的な要素を説明してから、それを自然再帰に当てはめます。

「自然再帰」の正確な定義は何ですか? 私が質問している理由は、Daniel Friedmanによるプログラミング言語の原則に関するクラスを受講しており、次のコードは「自然に再帰的」とは見なされないためです。

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

末尾再帰であるため、「不自然に再帰的な」コードを好みます。 ただし、そのようなコードはアナテマと見なされます。 関数を末尾再帰形式で記述してはいけない理由を尋ねると、アソシエイトインストラクターは単に「自然再帰を台無しにしないでください」と答えました。

関数を「自然再帰」形式で記述することの利点は何ですか?

回答

John Clements picture
2015年08月29日
9

「自然な」(または単に「構造的な」)再帰は、再帰について生徒に教え始めるための最良の方法です。 これは、Joshua Taylorが指摘する素晴らしい保証があるためです。つまり、終了することが保証されています[*]。 学生は、この種のプログラムに頭を悩ませるのに十分な苦労をしているので、これを「ルール」にすることで、壁にぶつかるのを大幅に減らすことができます。

構造的再帰の領域を離れることを選択した場合、あなた(プログラマー)は追加の責任を負います。これは、プログラムがすべての入力で停止することを保証することです。 考えて証明することがもう1つあります。

あなたの場合、それはもう少し微妙です。 2つの引数があり、2番目の引数で構造的に再帰的な呼び出しを行っています。 実際、この観察(プログラムは引数2で構造的に再帰的です)を使用すると元のプログラムは同じ収束証明を継承するため、末尾呼び出しを行わないプログラムとほぼ同じように正当であると私は主張し

[*]ここで正確に言うと、終了しない他の関数の呼び出しなど、他のあらゆる種類の間抜けなものを法制化する必要があります。

coredump picture
2015年08月28日
6

自然再帰は、処理しているタイプの「自然な」再帰的定義と関係があります。 ここでは、自然数を使用しています。 「明らかに」の自然数は、ゼロであるか、別の自然数、あなたは自然数を構築したいとき、あなたは自然に出力の後継以来、 0または(add1 z)いくつかの他の天然のためのz 、たまたま再帰的に計算されます。

教師はおそらく、再帰型の定義とその型の値の再帰的処理の間にリンクを作成することを望んでいます。 木やリストを処理しようとしても、自然数を「不自然な方法」で日常的に使用しているため、チャーチ数の観点から考えると自然な異議を唱える可能性があるため、数に関する問題は発生しません。

末尾再帰関数の記述方法をすでに知っているという事実は、そのコンテキストでは関係ありません。少なくとも今のところ、これは末尾呼び出しの最適化について話す教師の目的ではない

アソシエイトインストラクターは最初はあまり役に立ちませんでしたが(「自然な再帰をいじる」は「聞かないでください」と聞こえます)、あなたが与えたスナップショットで彼/彼女が与えた詳細な説明はより適切でした。

Kevin picture
2015年08月28日
1
(define (plus x y)
(if (zero? y) x
    (add1 (plus x (sub1 y)))))

y != 0場合、 (plus x (sub1 y))の結果がわかれば、 add1を計算する必要があることを覚えておく必要があります。 したがって、yがゼロに達すると、再帰は最も深くなります。 これでバックトラッキングフェーズが始まり、 add1が実行されます。 このプロセスは、 traceを使用して観察できます。

私は次のトレースを行いました:

(require racket/trace)
(define (add1 x) ...)
(define (sub1 x) ...)
(define (plus x y) ...)
(trace plus)

(plus 2 3)

これがトレースです:

>(plus 2 3)
> (plus 2 2)
> >(plus 2 1)
> > (plus 2 0)  // Deepest point of recursion
< < 2           // Backtracking begins, performing add1 on the results
< <3
< 4
<5
5               // Result

違いは、他のバージョンにはバックトラッキングフェーズがないことです。 数回自分自身を呼び出していますが、中間結果(引数として渡される)を記憶しているため、反復的です。 したがって、プロセスは余分なスペースを消費していません。


末尾再帰プロシージャの実装は、反復的な同等の手順を作成するよりも簡単または洗練されている場合があります。 ただし、目的によっては、再帰的に実装できない/実装できない場合があります。

PS:ガベージコレクションアルゴリズムについて少し説明しているクラスがありました。 このようなアルゴリズムは、スペースが残っていない可能性があり、したがって再帰のためのスペースがないため、再帰的ではない可能性があります。 最初は本当に理解しにくかった「Deutsch-Schorr-Waite」というアルゴリズムを覚えています。 最初に彼は概念を理解するためだけに再帰バージョンを実装し、その後反復バージョンを作成しました(したがって、手動でメモリのどこから来たかを覚えておく必要があります)、再帰バージョンの方がはるかに簡単でしたが、実際には使用できなかったと信じています...