一人読書会 「計算機プログラムの構造と解釈」 (12)
1.2.1 線形再帰と反復
反復的プロセス(iterative process)
再帰的プロセス(recursive process) の確認を前回行った、次は、同じく階乗を求める処理を反復的プロセス(iterative process) で行う。
(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)))
・・・反復という響きから、再帰ではなく、繰り返しを行うイメージだったが、例示されているコードは、思いっきり再帰している様に見える。
そもそもSchemeでは、ループが書けないのか？
反復的プロセスが『再帰』してしまっていたら、再帰的プロセスと、反復的プロセスの違いは何なのだ？
前回の Java での書き換えはメソッド呼び出しが見えにくかったので、今回はもう少しわかりやすく、メソッドの入り口と出口で、内容をトレースする様にして、再帰的プロセス、反復的プロセス、ループ処理のそれぞれで、途中経過を出力しながら階乗を計算させてみる。
package cap1_2_1;
public class Factorial {
public static void main(String[] args) {
Factorial me = new Factorial();
long num = Long.parseLong(args[0]);
// 再帰処理
System.out.printf("%d! = %d\n", num, me.recursiveFactorial(num));
// 反復処理(再帰)
System.out.printf("%d! = %d\n", num, me.iterativeFactorial(1L,1L,num));
// 反復処理(ループ)
System.out.printf("%d! = %d\n", num, me.loopFactorial(num));
}
/* 再帰処理により階乗を計算 */
public long recursiveFactorial(long num) {
trace(num,"recursive", true);
if (num == 1L) {
return trace(1L, "recursive" , false);
}
return trace(num * recursiveFactorial(num - 1L),"recursive" , false);
}
/* 反復処理(再帰)により階乗を計算 */
public long iterativeFactorial(long product, long counter, long num) {
trace(product,"iterative", true);
if (counter > num) {
return trace(product, "iterative", false);
}
return trace(iterativeFactorial(product * counter, counter + 1, num), "iterative", false);
}
/* 反復処理(ループ)により階乗を計算 */
public long loopFactorial(long num) {
trace(num,"loop", true);
long product = 1L;
long counter = 1L;
while(true) {
if (counter > num) {
return trace(product, "loop", false);
}
product *= counter;
counter++;
}
}
/*
* メソッドの呼び出しをトレース
* メソッドに入った時、リターン時に呼ぶ
*/
private long trace(long num, String method, boolean isEnter) {
/*
// スタックトレースを吐く
StackTraceElement[] elms = Thread.currentThread().getStackTrace();
for (StackTraceElement e : elms) {
System.out.printf("\t%s ", e.getMethodName());
}
*/
// (E) Enter (R) Return
System.out.printf("\t(%s) %s %6d\n", (isEnter)?"E":"R", method, num);
return num;
}
}
8 を引数に処理を行ったところ。(E) は、メソッドの入り口、(R)は出口でのトレース。
recursive が再帰プロセスで、iterative が反復プロセス。
(E) recursive 8 (E) recursive 7 (E) recursive 6 (E) recursive 5 (E) recursive 4 (E) recursive 3 (E) recursive 2 (E) recursive 1 (R) recursive 1 (R) recursive 2 (R) recursive 6 (R) recursive 24 (R) recursive 120 (R) recursive 720 (R) recursive 5040 (R) recursive 40320 8! = 40320 (E) iterative 1 (E) iterative 1 (E) iterative 2 (E) iterative 6 (E) iterative 24 (E) iterative 120 (E) iterative 720 (E) iterative 5040 (E) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 (R) iterative 40320 8! = 40320 (E) loop 8 (R) loop 40320 8! = 40320
おー 再帰、反復の両プロセスでも、『再帰』を利用しているが、行われている処理内容が全く異なることが分かった。
再帰プロセスでは、行きに計算処理をスタックに積んでいき(膨張)、帰りに計算を行っている(収縮)が、反復処理では徐々に成長していっている。
本書に「再帰的プロセス(process)と再帰的手続き(procedure)を混同しないように注意しなければならない」とあるのは、この違いのことか。
「手続きが再帰的」 というときには、手続の構文に再帰を含むことをいう。上記Java に書き換えた iterativeFactorial() メソッドは、再帰的手続きだが、反復的プロセスということ。なるほど。
「(Ada,Pascal,Cを含む)通常の言語の実装が、再帰手続きの実行で消費する記憶量が、プロセスは原理的に反復的であっても、手続き呼び出しの数とともに増加するように設計してある」 要するに、通常の言語では、本質的にプロセスが反復的でも、構文が再帰だと、メソッド呼び出しがスタックされる。このために、これらの区別がまぎらわしいとのこと。
また、『これらの言語では、反復プロセスは、do、repeat、until、for、while のような特殊目的の「ループ構造」に頼ってしか記述できない。』
確かに、上記 Java 例で iterativeFactorial はメソッド呼び出しが、一番底まで到達すると結果は計算されていて、あとはメソッド呼び出しを戻りながら結果を呼び出し元に返すだけにもかかわらず、メソッド呼び出しはスタックに積まれていくのだから、実際のプロセスが反復的だからといってメモリの使用量など変わらないだろう。trace() メソッドのスタックトレースを吐くコメントを外すと同じようにメソッドがスタックにつまれていって取り出されていく様がよく分かる。
繰り返し構文で書き直すと、loopFactorial() メソッドとなる。
じゃあ、Scheme ではどうなのよ？と思ったら、5章で検討すると。また、実装上この欠点はないと。
へー
構文上の再帰は、シンタックスシュガーで、実際は固定スペースで実行できるらしい。この性質の実装を 末尾再帰的(tail recursive) と言うらしい。
へー
今日はここまで。
