SICP読書録 #4 1.2.1 線形再帰と反復

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

1.2.1 手続きとそれが生成するプロセス

階乗を求める以下のコード。
これは、$n! = n(n-1)!$ だということを利用している。

1_2_1_0.scm

(define (factorial_1 n)
  (if (= n 1)
    1
    (* n (factorial_1 (- n 1)))))

(factorial_1 5)がどう展開されるか？

1_2_1_1.scm

(factorial_1 5)
(* 5 (factorial_1 4))
(* 5 (* 4 (factorial_1 3)))
(* 5 (* 4 (* 3 (factorial_1 2))))
(* 5 (* 4 (* 3 (* 2 (factorial_1 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1))))))
...

これを再帰プロセスという。
ネストが深くなるたび右へ伸びる。つまり記憶すべき情報量が増えていく。

では、次の例はどうか？
掛け算を1*1から始め、1ずつ数を増やす。指定されたnに到達したら終了。

1_2_1_2.scm

(define (factorial_2 n)
  (define (iter product counter)
    (if (> counter n)
      product
      (iter (* counter product)
            (+ counter 1))))
  (iter 1 1))

レキシカルスコーピングによりn=5はiter手続きから見える。
展開すると以下のように。

1_2_1_3.scm

(factorial_2 5)
(iter 1 1)
(iter 1 2)
(iter 2 3)
(iter 6 4)
(iter 24 5)
(iter 120 6)
120

右へ伸びていかない。つまり記憶すべき情報量が再帰のたびに増えない。
これを反復プロセスという。

どちらも再帰手続き（手続きが、その手続き自信を参照してる）なんだけど、
factorial_1は再帰プロセスとなり、factorial_2は反復プロセスとなって、それぞれ異なる。

一般的な言語では、再帰手続き 即 再帰プロセス になっちゃう。
スタックを積まなきゃいけないしね。だからforやwhileのようなループ構造があるのだ。

しかしSchemeでは再帰手続きの結果をなんらかの演算に使わないのなら、
それを反復プロセスとして実行する。これを末尾再帰という。

練習問題 1.9

+を以下のように再定義しちゃった。
ちなみにincはインクリメント。decはデクリメント。

ex1_9_0.scm

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

(+ 4 5)を展開すると。

ex1_9_1.scm

(+ 4 5)
(inc (+ 3 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

右に伸びていくので再帰プロセスになってる。

これならどうか。

ex1_9_2.scm

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

同様に(+ 4 5)を展開する。

ex1_9_3.scm

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
0

めでたく反復プロセスになった。

練習問題1.10

これをアッカーマン関数というらしい。

ex1_10_0.scm

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

実行結果は以下のとおり。

ex1_10_1.scm

gosh> (A 1 10)
1024
gosh> (A 2 4)
65536
gosh> (A 3 3)
65536

以下の手続きについて数学的定義を与えよ。

ex1_10_2.scm

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))

なんだか知らないけど、それぞれn=4として展開してみる。

ex1_10_3.scm

(f 4)
(A 0 4)
(* 2 4)
8

(f n)の結果は$2n$。

ex1_10_4.scm

(g 4)
(A 1 4)
(A 0 (A 1 3))
(A 0 (A 0 (A 1 2)))
(A 0 (A 0 (A 0 (A 1 1))))
(A 0 (A 0 (A 0 2)))
(A 0 (A 0 (* 2 2)))
(A 0 (A 0 4))
(A 0 (* 2 4))
(A 0 8)
(* 2 8)
16

(g n)の結果は$2^n$。

ex1_10_5.scm

(h 4)
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 4)) ; (A 1 2) = 2^2
(A 1 16)      ; (A 1 4) = 2^4
65536         ; (A 1 16) = 2^16

(h n)の結果は$2^{2^n}$か？と思ったけど違う。。。

例えば(h 4)は$2^{2^{2^2}}=65536$。(h 3)は$2^{2^2}=16$。2乗を$n-1$回繰り返した数になる。
数学的定義としてはどう書けばいいんだろう？