2

私は約 8 か月前に The perils of Java Schoolsを読み、それ以来、すぐに学ぶべきことのチェックリストとして使用しています。私は彼が話していることのほとんどを理解しています。

ただし、よくわからない部分があります。

純粋に機能的なプログラムでは、変数の値は決して変化しませんが、常に変化します! パラドックス！

このことから私が得ているのは (私が間違っていたら許してください)、彼は再帰について話しているということですが、再帰は
概念が単純すぎるように思えます。これが私の考えです：

(define (tail-rec n) 
  (if (= n 1) 
    (display "Done!") 
    (begin 
       (display n)
       (newline) 
       (tail-rec (- n 1)))))

出力されているものを見るとn、末尾再帰関数の の値はまだ変化していませんが、実際に変化していることがわかります。tail-recまた、関数自体は
変数の状態を変更していないため、純粋に関数であることを意味します。
すぅ…
これでいいのか？
これはジョエルが話していたことですか？そうでない場合は、私を修正してください。

4

1 に答える 1

3

あなたの質問に答えるために、ジョエルの記事は確かにその文脈での再帰に言及していました。

ただし、副作用があるためdisplay、コードは実際には純粋に機能的ではありません。newlineそこで、ちょっと話を逸らして、純粋関数型の再帰コードの具体的な例をいくつか紹介します。

最大公約数関数を考えます。

(define (gcd x y)
  (if (zero? y)
      x
      (gcd y (modulo x y))))

xここで、除算の剰余yが非ゼロになるたびに、 (末尾) 再帰的gcdに再度呼び出します。この新しい呼び出しでは、xとのy値が異なります。(特に、y値は反復ごとに小さくなり、最終的には、それが起こるために 1 でなければならない場合でも、正確にx除算する基本ケースにつながります。)yy

純粋関数再帰の別のケース (今回は末尾再帰ではありませんが、末尾再帰を使用して実装することもできます) は、2 つの並べ替えられた数値リストをマージするためのアルゴリズムを実装するために使用されます。

(define (merge lhs rhs)
  (cond ((null? lhs) rhs)
        ((null? rhs) lhs)
        ((< (car rhs) (car lhs))
         (cons (car rhs) (merge lhs (cdr rhs))))
        (else
         (cons (car lhs) (merge (cdr lhs) rhs)))))

lhs繰り返しますが、との両方rhsが空ではないケースを扱っているときはいつでもmerge、リストの 1 つが各呼び出しで短くなるように、 への別の呼び出しに再帰し、最終的にリストの 1 つが空である基本ケースに到達します。 .

このマージ関数は、マージソートを実装するために使用できます。

(define (mergesort lst)
  (let ((len (length lst)))
    (if (< len 2)
        lst
        (let-values (((lhs rhs) (split-at lst (quotient len 2))))
          (merge (mergesort lhs) (mergesort rhs))))))

これは、分割統治アルゴリズムの典型的な例です。リストに 2 つ以上の要素が含まれるたびに、リストを左右の半分に分割し、それぞれの半分に再帰してから、並べ替えられた半分を再びマージします。

于 2013-08-11T08:37:28.447 に答える