メソッドが自分自身を呼び出す処理を、再帰メソッド呼び出しと言う。(実は自分自身を呼び出すように見えて，もう一つのコピーを呼び出しているだけなのですがね．)
メソッドの再帰呼び出しを使うことで，いろいろな面白いプログラムが書ける．
数学で使う概念の一つに階乗がある．
nの階乗は１からnまでの数を掛け合わせたもので，n!と書く．次に例を示す．
nの階乗は以下の式で求められる．
つまり，n-1の階乗が求められれば，それにnをかけることでnの階乗が求められる．
この式を応用し，再帰を使うことで，階乗を求めるプログラムを次のように書ける．
1: /* 2: * Factorial.java 3: * 階乗を計算するプログラム 4: * Created on 2011/12/18 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class Factorial extends Turtle { 8: 9: public static void main(String[] args) { 10: Turtle.startTurtle(new Factorial()); 11: } 12: 13: public void start() { 14: print("factorial(1) = " + factorial(1)); 15: print("factorial(2) = " + factorial(2)); 16: print("factorial(3) = " + factorial(3)); 17: print("factorial(4) = " + factorial(4)); 18: print("factorial(5) = " + factorial(5)); 19: } 20: 21: int factorial(int n) { 22: int result; 23: if (n == 1) { 24: result = 1; 25: } else { 26: result = n * factorial(n - 1); 27: } 28: return result; 29: } 30: 31: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、Factorialプログラムが実行できます。
上記の例ではfactorial()メソッドからfactorial()メソッドを呼んでいるので，再帰の終点を作ってやらないと呼出しが無限に続いて，プログラムが止まらなくなる． （実際には，呼び出すごとにメソッドがスタックと呼ばれるメモリに読み込まれるので，そのメモリがいっぱいになってStackOverFlowErrorというエラーを出して止まる．
したがって，どこかで止めるプログラムを書かなければならない．上記の例では，
if (n == 1) {
result = 1;
}
の部分がそれにあたる．
再帰のプログラムはメソッドの中で自分自身のメソッドを呼び出しているのが特徴だが，自分自身に見えるけれども実は新たなコピーを作り，呼び出しているだけである．
このコピーの様子を視覚化して理解するために，呼出し過程を図示してみよう．
1: /* 2: * Factorial.java 3: * 階乗を計算するプログラム(プリント付き) 4: * Created on 2011/12/18 macchan 5: * Revised on 2012/12/18 macchan 6: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 7: */ 8: public class FactorialWithPrint { 9: 10: public static void main(String[] args) { 11: FactorialWithPrint factorialWithPrint = new FactorialWithPrint(); 12: factorialWithPrint.run(); 13: } 14: 15: public void run() { 16: System.out.println("factorial(5, 0) = " + factorial(5, 0)); 17: } 18: 19: int factorial(int n, int indentCount) { 20: printStart(n, indentCount); 21: int result; 22: if (n == 1) { 23: result = 1; 24: } else { 25: result = n * factorial(n - 1, indentCount + 1); 26: } 27: printEnd(result, indentCount); 28: return result; 29: } 30: 31: void printStart(int length, int indentCount) { 32: makeIndent(indentCount); 33: System.out.print("factorial(" + length + ", " + indentCount + ")"); 34: System.out.println(""); 35: } 36: 37: void printEnd(int result, int indentCount) { 38: makeIndent(indentCount); 39: System.out.print("// return " + result); 40: System.out.println(""); 41: } 42: 43: void makeIndent(int indentCount) { 44: for (int i = 0; i < indentCount; i++) { 45: System.out.print("\t"); 46: } 47: } 48: 49: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、FactorialWithPrintプログラムが実行できます。
factorial(5, 0) factorial(4, 1) factorial(3, 2) factorial(2, 3) factorial(1, 4) // return 1 // return 2 // return 6 // return 24 // return 120
異なる引数でメソッドが呼ばれているだけということが分かったと思う．
（ちなみに，階乗の計算は総和と同じように繰り返しでも書ける．）
フィボナッチ数列という数列がある．これも文系の諸君にはあまりなじみがないかもしれないが， 自然界によくみられる不思議な数列である．（このサイトなどをみてみよう）
fib(n)は次の式で求められる．
以下が具体例である．
フィボナッチ数列も再帰の例でよく出てくる例で，再帰を使うことでプログラムを次のように書ける．
1: /* 2: * Fibonacchi.java 3: * フィボナッチ数列を計算するプログラム 4: * Created on 2011/12/18 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class Fibonacci extends Turtle { 8: 9: public static void main(String[] args) { 10: Turtle.startTurtle(new Fibonacci()); 11: } 12: 13: public void start() { 14: print("fib(1) = " + fib(1)); 15: print("fib(2) = " + fib(2)); 16: print("fib(3) = " + fib(3)); 17: print("fib(4) = " + fib(4)); 18: print("fib(5) = " + fib(5)); 19: print("fib(6) = " + fib(6)); 20: print("fib(7) = " + fib(7)); 21: } 22: 23: int fib(int n) { 24: int value; 25: if (n == 1) { 26: value = 1; 27: } else if (n == 2) { 28: value = 2; 29: } else { 30: value = fib(n - 1) + fib(n - 2); 31: } 32: return value; 33: } 34: 35: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、Fibonacciプログラムが実行できます。
これも呼出し過程を図示してみよう
1: /* 2: * Fibonacchi.java 3: * フィボナッチ数列を計算するプログラム(プリント付き) 4: * Created on 2011/12/18 macchan 5: * Revised on 2012/12/18 macchan 6: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 7: */ 8: public class FibonacciWithPrint { 9: 10: public static void main(String[] args) { 11: FibonacciWithPrint fibonacciWithPrint = new FibonacciWithPrint(); 12: fibonacciWithPrint.run(); 13: } 14: 15: public void run() { 16: System.out.print("fib(5, 0) = " + fib(5, 0)); 17: } 18: 19: int fib(int n, int indentCount) { 20: printStart(n, indentCount); 21: int value; 22: if (n == 1) { 23: value = 1; 24: } else if (n == 2) { 25: value = 2; 26: } else { 27: value = fib(n - 1, indentCount + 1) + fib(n - 2, indentCount + 1); 28: } 29: printEnd(value, indentCount); 30: return value; 31: } 32: 33: void printStart(int length, int indentCount) { 34: makeIndent(indentCount); 35: System.out.print("fib(" + length + ", " + indentCount + ")"); 36: System.out.println(""); 37: } 38: 39: void printEnd(int result, int indentCount) { 40: makeIndent(indentCount); 41: System.out.print("// return " + result); 42: System.out.println(""); 43: } 44: 45: void makeIndent(int indentCount) { 46: for (int i = 0; i < indentCount; i++) { 47: System.out.print("\t"); 48: } 49: } 50: 51: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、FibonacciWithPrintプログラムが実行できます。
fib(5, 0) fib(4, 1) fib(3, 2) fib(2, 3) // return 2 fib(1, 3) // return 1 // return 3 fib(2, 2) // return 2 // return 5 fib(3, 1) fib(2, 2) // return 2 fib(1, 2) // return 1 // return 3 // return 8
最後の例の呼出し過程をよく見るとfib(1)とかfib(2)は何回も呼ばれており，大変効率が悪いプログラムである．
再帰プログラムでは，プログラムが計算式と似たように，わかりやすく書ける代わりに，効率が悪くなることがある．（絶対にそうなるわけではない）
上記のフィボナッチ数列のプログラムは，fib(20)くらいまでは動作するが，fib(50)ではコンピュータはお手上げ状態のはず（計算が終わらない）はずである．試してみよう． 実は，現実には，フィボナッチ数列は，「再帰を使ってはいけない例」として有名である．
フラクタル図形は簡単に言えば「どんなに拡大しても複雑な図形」のことをさす。(wikipedia 2011)
フラクタル図形の一種である自己相似図形は，自分自身と同じ形のミニチュアが自分の中に入れ子になっている図形をさす．
自己相似図形と再帰プログラムには深い関係があり，再帰プログラムを使ってフラクタル図形を書くことができる．
このような図形を書くには，まず繰り返される基本的な図形と変換ルールを考える．この場合は以下のように「Y」に小さな「Y」を足していく プログラムを考える．
まず，「Y」を描くプログラムを書く．ここで一回テストしてみることが重要である． （いきなり再帰のプログラム書こうとした先輩は，ことごとく失敗しています！）
1: /* 2: * DrawY.java 3: * Yを描くプログラム 4: * Created on 2011/12/18 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class DrawY extends Turtle { 8: 9: // 起動処理 10: public static void main(String[] args) { 11: Turtle.startTurtle(new DrawY()); 12: } 13: 14: // タートルを動かす処理 15: public void start() { 16: window.size(500, 500); 17: warp(250, 400); // 木を描く位置まで移動する 18: 19: drawY(50); 20: } 21: 22: // Yを描く 23: void drawY(int length) { 24: fd(length);// 幹を描く 25: 26: // 左の枝を描く 27: lt(30); 28: fd(length / 2); 29: bk(length / 2); 30: rt(30); 31: 32: // 右の枝を描く 33: rt(30); 34: fd(length / 2); 35: bk(length / 2); 36: lt(30); 37: 38: bk(length);// 幹の根元に戻る 39: } 40: 41: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、DrawYプログラムが実行できます。
次に，大きな「Y」の先に小さな「Y」を書くように，再帰呼び出しを行う．再帰の終点も忘れずに！
1: /* 2: * DrawTree.java 3: * 再帰を使って木を描くプログラム 4: * Created on 2011/12/18 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class DrawTree extends Turtle { 8: 9: // 起動処理 10: public static void main(String[] args) { 11: Turtle.startTurtle(new DrawTree()); 12: } 13: 14: // タートルを動かす処理 15: public void start() { 16: window.size(500, 500); 17: warp(250, 400); // 木を描く位置まで移動する 18: 19: drawY(50); 20: } 21: 22: // Yを描く 23: void drawY(int length) { 24: 25: if (length < 5) {// 再帰の終点 26: return; 27: } 28: 29: fd(length);// 幹を描く 30: 31: // 左の枝を描く 32: lt(30); 33: fd(length / 2); 34: drawY(length / 2); 35: bk(length / 2); 36: rt(30); 37: 38: // 右の枝を描く 39: rt(30); 40: fd(length / 2); 41: drawY(length / 2); 42: bk(length / 2); 43: lt(30); 44: 45: bk(length);// 幹の根元に戻る 46: 47: } 48: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、DrawTreeプログラムが実行できます。
このプログラムのメソッドの呼出し過程を表示すると，次のようになる．
1: /* 2: * DrawTreeWithPrint.java 3: * 再帰を使って木を描くプログラム(プリント付き) 4: * Created on 2011/12/18 macchan 5: * Revised on 2012/12/18 macchan 6: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 7: */ 8: public class DrawTreeWithPrint extends Turtle { 9: 10: // 起動処理 11: public static void main(String[] args) { 12: Turtle.startTurtle(new DrawTreeWithPrint()); 13: } 14: 15: // タートルを動かす処理 16: public void start() { 17: window.size(500, 500); 18: warp(250, 400); // 木を描く位置まで移動する 19: 20: drawY(50, 0); 21: } 22: 23: // Yを描く 24: void drawY(int length, int indentCount) { 25: printStart(length, indentCount); 26: 27: if (length < 5) {// 再帰の終点 28: printEnd(indentCount); 29: return; 30: } 31: 32: fd(length);// 幹を描く 33: 34: // 左の枝を描く 35: lt(30); 36: fd(length / 2); 37: drawY(length / 2, indentCount + 1); 38: bk(length / 2); 39: rt(30); 40: 41: // 右の枝を描く 42: rt(30); 43: fd(length / 2); 44: drawY(length / 2, indentCount + 1); 45: bk(length / 2); 46: lt(30); 47: 48: bk(length);// 幹の根元に戻る 49: 50: printEnd(indentCount); 51: } 52: 53: void printStart(int length, int indentCount) { 54: makeIndent(indentCount); 55: System.out.print("drawY(" + length + ", " + indentCount + ")"); 56: System.out.println(""); 57: } 58: 59: void printEnd(int indentCount) { 60: makeIndent(indentCount); 61: System.out.print("//"); 62: System.out.println(""); 63: } 64: 65: void makeIndent(int indentCount) { 66: for (int i = 0; i < indentCount; i++) { 67: System.out.print("\t"); 68: } 69: } 70: 71: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、DrawTreeWithPrintプログラムが実行できます。
drawY(50, 0) drawY(25, 1) drawY(12, 2) drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // // drawY(12, 2) drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // // // drawY(25, 1) drawY(12, 2) drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // // drawY(12, 2) drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // drawY(6, 3) drawY(3, 4) // drawY(3, 4) // // // // //
（呼び出し過程もフラクタル図形になっているところが印象的である．）
木を描くサンプルプログラムを改造して、自然な木を描くプログラムにしよう。
【自然な木に見せるためのヒント】
ファイル名は「NaturalTree.java」とすること．
メソッドの再帰呼出しを応用して，下記の図を書いてみましょう．
ファイル名は「Tournament.java」とすること．
メソッドの再帰呼出しを応用して，下記の図を書いてみましょう．
ファイル名は「Gasket.java」とすること．
メソッドの再帰呼出しを応用して，下記の図を書いてみましょう．
ファイル名は「SuperStar.java」とすること．
メソッドの再帰呼出しを応用して，下記の図を書いてみましょう．
ファイル名は「Koch.java」とすること．
このサイトを参考にして，ひまわりの絵を描いてみましょう．
ファイル名は「Sunflower.java」とすること．
このサイトを参考にして，葉っぱの絵を描いてみましょう．
ファイル名は「Leaf.java」とすること．