酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2010年7月26日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html

再帰的アルゴリズム 再帰は重要なアルゴリズムの概念である．とくに参照型を用いた柔軟なデータ構造を扱う場合には，基本的に再帰的アルゴリズムを用いるしかない．ここでは，再帰的アルゴリズムを詳細に検討し，その動作の理解をする

通りがけ順の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 親の頂点に戻る 二分探索木を走査すると 横倒しの木を表示できる 29 29 20 20 32 32 14 14 24 24 30 30 48 48 7 7 19 19 21 21 31 31

木の根が左にある、 左から右へ生えている木を表示するプログラム public void printTreeRecursive() { this.printTreeRecursive(this.root, 0); } private void printTreeRecursive(MyNode aLocalRootNode, int depth) { if(null == aLocalRootNode) return; this.printTreeRecursive(aLocalRootNode.getRight(), depth+1); for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(aLocalRootNode.getData().toString()); this.printTreeRecursive(aLocalRootNode.getLeft(), depth+1); 再帰呼び出し (29, "リンゴ") (20, "ミカン") (14, "サクランボ") (32, "バナナ") (30, "イチゴ") (24, "ブルーベリー") ( 7, "グレープフルーツ") (21, "レモン") (48, "メロン") (31, "スイカ") (19, "ナシ") (17, "モモ") (23, "マンゴー") (28, "ブドウ") (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) 再帰呼び出し版 木の根が左にある、 左から右へ生えている木を表示するプログラム

this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 this.printTreeRecursive((23, “マンゴー”), 4); 左部分木探索中 this.printTreeRecursive((23, "マンゴー"), 4);出力 this.printTreeRecursive((23, "マンゴー"), 4); 右部分木探索中 this.printTreeRecursive((17, “モモ”), 4); 左部分木探索中 this.printTreeRecursive((17, "モモ"), 4);出力 this.printTreeRecursive((31, “スイカ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3);出力 this.printTreeRecursive((19, "ナシ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3); 右部分木探索中 this.printTreeRecursive((19, “ナシ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3); 右部分木探索中 this.printTreeRecursive((28, “ブドウ”), 3); 左部分木探索中 this.printTreeRecursive((19, "ナシ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, "グレープフルーツ"), 3);出力 this.printTreeRecursive(( 7, "グレープフルーツ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, “グレープフルーツ”), 3); 左部分木探索中 this.printTreeRecursive((21, “レモン”), 3); 左部分木探索中 this.printTreeRecursive((21, "レモン"), 3);出力 this.printTreeRecursive((21, "レモン"), 3); 右部分木探索中 this.printTreeRecursive((24, “ブルーベリー”), 2); 左部分木探索中 this.printTreeRecursive((48, "メロン"), 2); 右部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2); 右部分木探索中 this.printTreeRecursive((14, "サクランボ"), 2); 右部分木探索中 this.printTreeRecursive((30, "イチゴ"), 2); 右部分木探索中 this.printTreeRecursive((14, “サクランボ”), 2); 左部分木探索中 this.printTreeRecursive((30, “イチゴ”), 2); 左部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2);出力 this.printTreeRecursive((48, "メロン"), 2);出力 this.printTreeRecursive((30, "イチゴ"), 2);出力 this.printTreeRecursive((14, "サクランボ"), 2);出力 this.printTreeRecursive((48, “メロン”), 2); 左部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 左部分木探索中 this.printTreeRecursive((20, "ミカン"), 1); 右部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 出力 this.printTreeRecursive((32, “バナナ”), 1); 左部分木探索中 this.printTreeRecursive((32, "バナナ"), 1); 右部分木探索中 this.printTreeRecursive((32, “バナナ”), 1); 出力 this.printTreeRecursive((29, “リンゴ”), 0); 左部分木探索中 this.printTreeRecursive((29, "リンゴ"), 0);出力 this.printTreeRecursive((29, "リンゴ"), 0); 右部分木探索中

漸化式からの計算 階乗 f(0) = 1, f(x) = x! = x*f(x-1) フィボナッチ数列 f(0) = 1, f(1) = 1, f(x) = f(x-2) + f(x-1) いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合 f(0)やf(1)で停止

末尾再帰なので再帰呼び出しをループに変換することは容易 public class Factorial { public static int factorial(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); System.out.println("factorial(" + aTarget + ")に入ります"); if(0 == aTarget){ System.out.println("factorial(0) から出ます: 1"); return 1; } int total = aTarget * Factorial.factorial(aTarget - 1); System.out.println("factorial(" + aTarget + ") から出ます: " + total); return total; 階乗を求めるプログラム public static int factorialWithoutRecursion(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); if(0 == aTarget){ return 1; } int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; return total; 末尾再帰なので再帰呼び出しをループに変換することは容易

f(0)から順にたどれば結果を求めることができる public class Fibonatti { public static int fibonatti(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); System.out.println("fibonatti(" + aTarget + ") に入ります"); if((0 == aTarget) || (1 == aTarget)){ System.out.println("fibonatti(" + aTarget + ") から出ます: 1"); return 1; } int total = fibonatti(aTarget - 2) + fibonatti(aTarget - 1); System.out.println("fibonatti(" + aTarget + ") から出ます: " + total); return total; public static int fibonattiWithoutRecursion(int aTarget) { if(0 > aTarget) throw new IllegalArgumentException(); if((0 == aTarget) || (1 == aTarget)){ return 1; } int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= aTarget; count++){ total = old1 + old2; old2 = old1; old1 = total; return total; f(0)から順にたどれば結果を求めることができる f(x)に必要とされるのはf(x-1)とf(x-2)なので変数を2つ追加すれば足る

[sakai@star 13]$ java FactorialTest 720 factorial(6)に入ります factorial(5)に入ります factorial(4)に入ります factorial(3)に入ります factorial(2)に入ります factorial(1)に入ります factorial(0)に入ります factorial(0) から出ます: 1 factorial(1) から出ます: 1 factorial(2) から出ます: 2 factorial(3) から出ます: 6 factorial(4) から出ます: 24 factorial(5) から出ます: 120 factorial(6) から出ます: 720 [sakai@star 13]$ [sakai@star 13]$ java FibonattiTest 8 fibonatti(5) に入ります fibonatti(3) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(3) から出ます: 3 fibonatti(4) から出ます: 5 fibonatti(5) から出ます: 8 [sakai@star 13]$

再帰的アルゴリズム ハノイの塔 一回に一枚の円盤しか動かしてはいけない。 移動の途中で円盤の大小を逆に積んではいけない。 常に大きい方の円盤が下になるようにする。 棒以外のところに円盤を置いてはいけない。

円盤オブジェクトと 指定の大きさの円盤を生成するメソッド public class Disk { public Disk(int aSize) { if(1 > aSize){ throw new IllegalArgumentException(); } this.size = aSize; public int size() { return this.size; private int size = 0; 円盤オブジェクトと 指定の大きさの円盤を生成するメソッド

塔オブジェクトと スタックを用いて円盤操作を実現する import java.util.Stack; public class Tower { public Tower() { this.stack = new Stack(); } public Disk get() { return (Disk)this.stack.pop(); public Disk get(int anIndex) { return (Disk)this.stack.get(anIndex); public int size() { return this.stack.size(); } public boolean put(Disk aDisk) { if(this.stack.isEmpty()){ this.stack.push(aDisk); return true; int topSize = ((Disk)this.stack.peek()).size(); if(aDisk.size() < topSize){ return false; private Stack stack; 塔オブジェクトと スタックを用いて円盤操作を実現する

再帰呼び出し public class Hanoi { private Tower[] tower = new Tower[] { }; private int disks; } public Hanoi(int aDisks) { this.disks = aDisks; for(int count = aDisks; 0 < count; count--){ this.tower[0].put(new Disk(count)); } this.printAll(); public void doHanoi() { this.doHanoi(this.disks, 0, 1, 2); private void doHanoi (int aDisks, int aFrom, int aTo, int anOther) { if(1 == aDisks){ Disk disk = this.tower[aFrom].get(); this.tower[aTo].put(disk); } else { this.doHanoi(aDisks - 1, aFrom, anOther, aTo); this.doHanoi(aDisks - 1, anOther, aTo, aFrom); 再帰呼び出し

private void printAll() { int[] towerSizes = { tower[0].size(), tower[1].size(), tower[2].size() }; int towerSizeTotal = (towerSizes[0] + towerSizes[1] + towerSizes[2]); int[] sizes = {towerSizes[0], towerSizes[1], towerSizes[2]}; for(int count = 0; count < towerSizeTotal; count++){ for(int tcount = 0; tcount < 3; tcount++){ if((towerSizeTotal - towerSizes[tcount]) <= count){ Disk disk = this.tower[tcount].get(--sizes[tcount]); System.out.print("\t"); for(int disks = 0; disks < disk.size();disks++){ System.out.print("-"); } }else{ System.out.print("\t|\t"); System.out.println(""); System.out.println("-------------------------------------------------");

再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 最も最後に呼ばれた関数が最初に抜ける 実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまりLIFO、スタック 一時変数や途中経過を退避する領域が あればループにより実現できる

退避すべきデータ 部分木の根 今何をしているか？ ループに変換するにはこれをスタックに退避 再帰呼び出しでは、プログラムの流れとして 保持していた。つまりCPUのプログラムカウンタ 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る ループに変換するにはこれをスタックに退避 探索中の頂点の深さは計算できるので退避不要

木の根が左にある、 左から右へ生えている木を表示するプログラム public void printTreeLoop() { MyNode node, currentRootNode = this.root; int depth = 0, todo = 0; Stack stack = new Stack(); while(true){ switch(todo++){ case 0: node = currentRootNode.getRight(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 1: for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(currentRootNode.getData().toString()); // 続く… ループ版 木の根が左にある、 左から右へ生えている木を表示するプログラム

一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る case 2: node = currentRootNode.getLeft(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 3: if(stack.empty()){ return; todo = ((Integer)stack.pop()).intValue(); currentRootNode = (MyNode)stack.pop(); depth--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る