オンラインSICP読書女子会 #3(1.2.1~1.2.2) まとめ

#ladiescpp の主催してる オンラインSICP読書女子会 #3 - connpassのまとめです〜。
まちがっているところがあればどんどんコメントください(｀･ω･´)ゞ

次回の参加は オンラインSICP読書女子会 #4 (1.2.3~1.2.4) - connpass から！

1.2.1 線形再帰と反復

factorial(再帰)

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

; > (factorial 1)
; 1
; > (factorial 5)
; 120

遅延演算の連鎖によって特徴づけられるこのタイプのプロセスを 再帰プロセス と呼ぶ。
再帰プロセスはステップ数・必要な情報量はnに比例して増加

※プロセスと手続きを混同しない。
再帰手続き: その手続きの定義が (直接または間接的に) その手続き自身を参照しているという構文的事実を指す
再帰プロセス: どのようにプロセスが展開するか・ということであり構文の問題ではない

置換モデル(図1.3)では展開に続く縮約という形で示している。

• 展開はプロセスが遅延演算の連鎖を構築する際に起こる。
• 縮約は実行する際に起こる。

**factorial(反復)**


(define (factorial-iter product counter max-count)
  (if (> counter max-count) product
      (factorial-iter (* product counter) (+ counter 1) max-count)))

(define (factorial n)
  (factorial-iter 1 1 n))

; (factorial 5)
; > 120

状態が限られた数の状態変数に集約されるようなプロセスを 反復プロセス(iterative process) と呼ぶ。
反復プロセスは、再帰手続きとして記述されていても、固定の空間で実行できる。
この性質をもった実装は末尾再帰と呼ばれる。

気になった部分メモ

Scheme の実装には、この欠点がありません。反復プロセスは、再帰手続きとして記述されていても、固定の空間で実行できます。 (P36)

置換モデル
わかりやすく考えるために、定義したものや引数を展開していく

練習問題1.9 再帰プロセスと反復プロセス

以下の２つの手続きを、置換モデルを使って(+ 4 5)を評価する際に生成するプロセスを示す。

---

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

の場合、再帰プロセス

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

---

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


の場合、反復プロセス

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

---

hioさん

; (1)
; (+ 4 5)
; > (inc (+ (dec 4) 5))
; (inc (+ 3 5))
; > (inc (inc (+ (dec 3) 5)))
; (inc (inc (+ 2 5)))
; > (inc (inc (inc (+ (dec 2) 5))))
; (inc (inc (inc (+ 1 5))))
; > (inc (inc (inc (inc (+ (dec 1) 5)))))
; (inc (inc (inc (inc (+ 0 5)))))
; (inc (inc (inc (inc 5))))
; (inc (inc (inc 6)))
; (inc (inc 7))
; (inc 8)
; 9
;
; (2)
; (+ 4 5)
; > (+ (dec a) (inc b))
; (+ 3 6)
; > (+ (dec 3) (inc 6))
; (+ 2 7)
; > (+ (dec 2) (inc 7))
; (+ 1 8)
; > (+ (dec 1) (inc 8))
; (+ 0 9)
; 9
;
; 前者は再帰プロセス.
; 後者は反復プロセス.

練習問題1.10 アッカーマン関数

;; アッカーマン関数 A

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

; めも
; yが0なら0, 
; xが0なら2y
; yが1なら2
; それ以外はA(x - 1, A(x, y - 1))

以下の式の値は何になるか。
(A 1 10) (A 2 4) (A 3 3)

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

(define (f n) (A 0 n))

f(n) = 2n

(define (g n) (A 1 n))

---

@cocodrips

n = 3
A(1, 3)
A(0, A(1, 2))
A(0, A(0, A(1, 1))) # A(1, 1) = 2
A(0, A(0, 2)) # A(0, 2) = 4
A(0, 4)
8

g(n) = 2^n

---

hioさん

(define (g n) (A 1 n))
(A 1 n)
; # (else (A (- x 1) (A x (- y 1))))
; > (A (- x 1) (A x (- y 1))) 
; > (A (- 1 1) (A 1 (- n 1))) 
; > (A 0 (A 1 (- n 1))) 

ここで (f n) 及び (g n) の定義より,

; > (f (A 1 (- n 1))) 
; > (f (g (- n 1))) 
; > (* 2 (g (- n 1)))

すなわち以下の様な等比数列となる

g(n) = 2*g(n-1) = 2^n

####(define (h n) (A 2 n))

n = 2
A(2 2)
A(1, A(2, 1)) #A(2, 1) = 2
A(1, 2)
4

n = 3
A(2 3)
A(1, A(2, 2)) 
A(1, A(1, A(2, 1))) #A(2, 1) = 2
A(1, A(1, 2)) #A(1, 2) = 4
A(1, 4) # 2 ^ 4

これだけじゃわからなそう。

(A 2 1) ;2 2^1
(A 2 2) ;4 2^2
(A 2 3) ;16 2^4
(A 2 4) ;65536 2^16
(A 2 5) ;200352993040684646497907235156025575044782547556975141926501697371089405955631145308950613088093334810103823434290726318182294938211881266886950636476154702916504187191635158796634721944293092798208430910485599057015931895963952486337236720300291696959215610876494888925409080591145703767520850020667156370236612635974714480711177481588091413574272096719015183628256061809145885269982614142503012339110827360384376787644904320596037912449090570756031403507616256247603186379312648470374378295497561377098160461441330869211810248595915238019533103029216280016056867010565164675056803874152946384224484529253736144..........

h(n) = 2 ^ {h(n - 1)}

テトレーションという名前のある演算だそう。

---

hioさん

; (A 2 n))
; # (else (A (- x 1) (A x (- y 1))))
; > (A (- x 1) (A x (- y 1)))
; > (A (- 2 1) (A 2 (- n 1)))
; > (A 1 (A 2 (- n 1)))

ここで (g n) 及び (f n) の定義より,

; > (g (A 2 (- n 1)))
; > (g (h (- n 1)))

h(n) = 2^h(n-1) = hyper4(2, n)

1.2.2 木の再帰

みんな大好きフィボナッチ数列(｀･ω･´)ゞ

練習問題1.11

関数fを演算する手続きを、再帰プロセス/反復プロセスそれぞれによって書け。

;; 再帰
(define (f n)
  (if (< n 3) n
      (+ (f (- n 1))
	 (* 2 (f (- n 2)))
	 (* 3 (f (- n 3))) ) ))

;; gosh> (f 2)
;; 2
;; gosh> (f 8)
;; 335


;; 反復
(define (f-iter count end a1 a2 a3)
  (if (<= count end)
      (f-iter (+ count 1)
	      end
	      a2
	      a3
	      (+ a3 (* 2 a2) (* 3 a1)) )
      a3))


(define (f n)
  (if (< n 3)
      n
      (f-iter 3 n 0 1 2)))

;; gosh> (f 4)
;; 11
;; gosh> (f 8)
;; 335

# 一度pythonで書いてから考えた
def f(n):
    array = [0] * (n + 1)
    for i in xrange(n + 1):
        if (i < 3):
            array[i] = i
        else:
            array[i] = array[i - 1] + (2 *  array[i - 2]) + (3 * array[i - 3])

    return array[n]

練習問題1.12

パスカルの三角形の要素を再帰プロセスによって求める手続きをかけ

@cocodrips

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

斜めにするとわかりづらいからこういう風に考えて、
n段目の左からm個目は、
(n-1)段目の左から m個目 + (m - 1)個目

(define (pascal top left)
  (cond
   ((= left 1) 1)
   ((= top 1) 0)
   (else (+ (pascal (- top 1) (- left 1)) (pascal (- top 1) left) ))

   ))

;; gosh> (pascal 1 1)
;; 1
;; gosh> (pascal 5 3)
;; 6

---

hioさん

左端と右端で折り返していくタイプ

(define (node row col)
    (cond ((= col 1) 1) ; 左側の辺.
          ((= col row) 1) ; 右側の辺.
          (else
              (+ (node (- row 1) (- col 1))
                 (node (- row 1) col)))))

練習問題1.13

かんがえちゅう・ω・