読者です 読者をやめる 読者になる 読者になる

SICP第1章(4)

問題1.15

a

実際に関数pの最初に

(display (format "x = ~a\n" x))

を入れて実行してみれば簡単か。

x = 0.049999999999999996
x = 0.1495
x = 0.4351345505
x = 0.9758465331678772
x = -0.7895631144708228

となり、5回呼ばれた。

b

sine関数が再帰的に呼ばれるわけだが、終了条件はangleの絶対値が0.1以下になること。で、angleは毎回1/3になっている。てことはステップ数は\log_3 aでいいのかな?sine関数は末尾再帰ではないので呼ばれる度にスペースを使う。ということはスペースも\log_3 aか。

問題1.16

ヒントにあるようにab^nが不変になるように考えてみる。例えば3^10だったら以下のようになればよい。

   b   n      a
   3  10      1
   9   5      1
   9   4      9
  81   2      9
6561   1      9
6561   0  59049

つまり、nが偶数のときはb=b^2, n=n/2, a=aとして再帰、奇数のときはb=b, n=n-1, a=b*aとする。