おたっく's blog

プログラミングなど技術的なことを中心に書きます。

JavaScriptでSICPを勉強する その2

JavaScriptSICPを勉強する その2」です。

1.2 手続きとその生成するプロセス (p.17)


階乗を計算する関数factorialについて考えてみましょう。
scheme

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

JavaScript

function factorial(n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n);
}

再帰で階乗を計算していますが、5!を計算するプロセスは以下のようになります。(演算子の順序は前置記法でなく見やすくしています)

(factorial 5)
=> 5 * (factorial 4)
=> 5 * 4 * (factorial 3)
=> 5 * 4 * 3 * (factorial 2)
=> 5 * 4 * 3 * 2 * (factorial 1)
=> 5 * 4 * 3 * 2 * 1
=> 5 * 4 * 3 * 2
=> 5 * 4 * 6
=> 5 * 24
=> 120

再帰呼び出しの途中では一時的に値をスタックに保持する必要があり、メモリを無駄に消費します。これを末尾再帰に書き換えてみましょう。
scheme

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

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

JavaScript

function factorial(n) {
    return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
    if(counter > max_count)
        return product;
    else
        return fact_iter(counter * product, counter + 1, max_count);
}

末尾再帰に書き換えた結果、5!を計算するプロセスは以下のようになりました。見ての通り再帰の途中でproductに計算途中の値が入っています。

(factorial 5)
=> (fact-iter   1 1 5)
=> (fact-iter   1 2 5)
=> (fact-iter   2 3 5)
=> (fact-iter   6 4 5)
=> (fact-iter  24 5 5)
=> (fact-iter 120 6 5)

次はフィボナッチ数を計算してみましょう。フィボナッチ数についての説明はWikipedia:フィボナッチ数にも書いてあります。最初は単純な再帰で書いてみます。
scheme

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

JavaScript

function fib (n) {
    if (n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

このような再帰で書くと計算にとても時間がかかってしまいます。例えばfib(5)を計算するときのプロセスは以下のようになります。(多少評価される順序が違うかも)

(fib 5)
=> ((fib 4) + (fib 3))
=> (((fib 3) + (fib 2)) + ((fib 2) + (fib 1)))
=> ((((fib 2) + (fib 1)) + ((fib 1) + (fib 0))) + (((fib 1) + (fib 0)) + 1))
...

同じ計算を何度もしていて非常に効率の悪い計算をしています。これを末尾再帰に書き換えてみましょう。
scheme

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

JavaScript

function fib(n) {
    return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
    if (count == 0)
        return b;
    else
        return fib_iter(a + b, a, count - 1);
}

末尾再帰に書き換えた結果、(fib 5)の計算プロセスは以下のようになります。

(fib 5)
=> (fib-iter 1 0 5)
=> (fib-iter 1 1 4)
=> (fib-iter 2 1 3)
=> (fib-iter 3 2 2)
=> (fib-iter 5 3 1)
=> (fib-iter 8 5 0)
=> 5 

再帰呼び出しするときに計算途中の値を引数としているようです。無駄な計算がなくなって効率が良くなりました。

最後にべき乗の計算をする関数を書いてみましょう。
scheme

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1))))

JavaScript

function expt(b, n) {
    if(n == 0)
        return 1;
    else
        return b * expt(b, n-1);
}

これも末尾再帰に書き換えてみましょう。
scheme

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

JavaScript

function expt(b, n) {
    return expt_iter(b, n, 1);
}
function expt_iter(b, counter, product) {
    if (counter == 0)
        return product;
    else
        return expt_iter(b, counter - 1, b * product);
}

単純な再帰の方が簡潔に書ける場合が多いですが、一般的には末尾再帰の方が処理が早いです。いくつかの例を見てなんとなく末尾再帰が理解できた気がします。次回は高階手続きによる抽象のおはなしで「JavaScriptでSICPを勉強する その3」です。