一人読書会「計算機プログラムの構造と解釈」 (11)

1.2.1　線形再帰と反復

再帰的プロセス(recursive process)

任意の正の整数 n に対する階乗関数 n! は、 n ・ (n-1)! で得られる。つまり、n! は、 (n-1)! を計算し、結果に n をかけて計算できる。1! は 1に等しいので、以下の手続きに変換できる。

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

この形のプロセスを再帰的プロセス(recursive process) といい、遅延演算(deferred operations) の列で特徴づけられる。

遅延演算とは、プロセスが膨張と収縮の形をとるとき、膨張時に遅延演算の列として作成される。収縮は演算が実際に実行される時に起きる。

解釈系は、後に実行する演算を覚えておく必要があり、覚えておく必要のある情報量は n に比例して(線形に)成長するため、こういうプロセスを線形再帰的プロセス(liner recuresive porceee) という。

例によって、Schemeでは、その様子を確認するだけのスキルがまだ無いので、たまには Java で確認してみる。

やっていることの、本質的には、これだけのこと。

private long factorial(long num){
package cap1_2_1;

public class Capter1_2_1 {
	public long factorial(long num){
		if (num == 1L){
			return 1L;
		}
		return num * this.factorial(num - 1L);
	}
}

処理の経過をトレースするために、いろいろと組み込み、引数に 8 を与えて実行してみる。

package cap1_2_1;

import java.util.Stack;

public class Capter1_2_1 {
	// トレース用
	private Stack stk = new Stack();
	
	public static void main(String[] args) {
		Capter1_2_1 me = new Capter1_2_1();
		long num = Long.parseLong(args[0]);
		me.testFactorial(num);
	}
	public void testFactorial(long num){
		stk.push(String.format("factional(%d)", num));
		long result = this.factorial(num);
		System.out.printf("*************\n");
		System.out.printf("%d! = %d\n", num, result);
	}
	public long factorial(long num){
		System.out.println(stk.toString());
		stk.pop();
		stk.push(String.format("%d", num));
		
		if (num == 1L){
			System.out.println(stk.toString());
			return 1L;
		}
		
		stk.push(String.format("factorial(%d)", num - 1L));
		long num_minus_1 = this.factorial(num - 1L);
		
		stk.pop(); // 自身
		stk.pop(); // ひとつ手前を計算結果に置き換え
		stk.push(String.format("%d", num * num_minus_1));
		
		System.out.println(stk.toString());
		return num * num_minus_1;
	}
}

膨張と、収縮の様子がよく分かる。

[factional(8)]
[8, factorial(7)]
[8, 7, factorial(6)]
[8, 7, 6, factorial(5)]
[8, 7, 6, 5, factorial(4)]
[8, 7, 6, 5, 4, factorial(3)]
[8, 7, 6, 5, 4, 3, factorial(2)]
[8, 7, 6, 5, 4, 3, 2, factorial(1)]
[8, 7, 6, 5, 4, 3, 2, 1]
[8, 7, 6, 5, 4, 3, 2]
[8, 7, 6, 5, 4, 6]
[8, 7, 6, 5, 24]
[8, 7, 6, 120]
[8, 7, 720]
[8, 5040]
[40320]
*************
8! = 40320

Java 好きだし、おもしろいけど、やはりPython と比べると、思考から実装までのラグがちょっと大きいなぁ~

今日はここまで。

Follow me!

@pppiroto