一人読書会「計算機プログラムの構造と解釈」 (13)

1.2.1　線形再帰と反復

問題 1.9

次の2つの手続きはどちらも引数を 1増やす手続きと、引数を 1減らす手続きdec をつかって2つの正の数を足す方法を定義している。

(define (plus a b)
  (if (= a 0)
  b
  (inc (plus (dec a) b))))

(define (plus a b)
  (if (= a 0)
  b
  (plus (dec a) (inc b))))

置き換えモデルを使い、それぞれの手続きが (plus 4 5) を評価するときに生成するプロセスを示し、反復的か再帰的かを述べよ。

まｚ、「置き換えモデル」 1.1.5 手続き作用の置き換えモデルで出てきた、各仮パラメータを対応する引数で取り替え、手続きの本体を評価するプロセス。手続きを考える時の補助であり、解釈系の実際の働きを述べるものではない。

やってみよう。

(define (plus 4 5)                  (if (= 4 0) 5 (inc (plus  3 5))))
    (define (plus 3 5)              (if (= 3 0) 5 (inc (plus  2 5))))
        (define (plus 2 5)          (if (= 2 0) 5 (inc (plus  1 5))))
            (define (plus 1 5)      (if (= 1 0) 5 (inc (plus  0 5))))
                (define (plus 0 5)   5) 
            (define (plus 1 5)       6)
        (define (plus 2 5)           7)
    (define (plus 3 5)               8)
(define (plus 4 5)                   9)
9 

(define (plus 4 5)                 (if (= 4 0) 5 (plus  3 6)))
    (define (plus 3 6)             (if (= 3 0) 6 (plus  2 7)))
        (define (plus 2 7)         (if (= 2 0) 7 (plus  1 8)))
            (define (plus 1 8)     (if (= 1 0) 8 (plus  0 9)))
                (define (plus 0 9) 9)))
            (define (plus 1 8)     9)))
        (define (plus 2 7)         9)))  
    (define (plus 3 6)             9)))
(define (plus 4 5)                 9)))
9

本書で、紹介されている書き方で表現するのはちょっと困難なので、再帰をインデントで表現してみた。

前回確認したのと同様、前者が再帰的プロセスにより結果が膨張と収縮にて生成されており、後者は反復的プロセスにより結果が生成されている。

後者のプロセスは末尾再帰的というらしいのだが、何故か？と思ったら、関数の最後の(末尾の)ステップが再帰呼び出しになるような形になっていることによるらしい。上記の置き換えモデルがどのように処理されるかを見れば分かるが、再帰的プロセスと異なり、反復的プロセスにでは、計算結果が出た後は、値を呼び出しの逆順に返すだけだ。このため、末尾再帰的なプロセスは、呼び出しをジャンプに最適化できるということらしい。

Wikipedia 末尾再帰を参照。

今日はここまで。

Follow me!

@pppiroto