Hatena::Groupsicp

SICP読書記

 | 

2009-11-22

問題3.9

問題3.9 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.9 - SICP読書記

再帰

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

(factorial 6)

呼び出しのスタックトレースは以下の通り。それぞれの環境に名前をつける。

(factorial 6) [E1]

→(factorial 5) [E2]

→(factorial 4) [E3]

→(factorial 3) [E4]

→(factorial 2) [E5]

→(factorial 1) [E6]

環境の構成としては

大域環境

|

    • E6
    • E5
    • E4
    • E3
    • E2
    • E1

になる。

反復版

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

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

(factorial 6)

呼び出しは

(factorial 6) [E1]

→(fact-iter 1 1 6) [E2]

→(fact-iter 1 2 6) [E3]

→(fact-iter 2 3 6) [E4]

→(fact-iter 6 4 6) [E5]

→(fact-iter 24 5 6) [E6]

→(fact-iter 120 6 6) [E7]

→(fact-iter 720 7 6) [E8]

環境の構成は

大域環境

    • E1
    • E2
    • E3
    • E4
    • E5
    • E6
    • E7
    • E8

結局どっちも大域環境下に直接全ての手続きが束縛されているので、環境も大域環境の一段階下にぶらさがる。

 |