プログラミング入門(17)

メソッドの再帰呼出し
フラクタル図形

メソッドの再帰呼出し

メソッドの実行中に他のメソッドを呼び出すことがあります。「メソッドが実行中に、自分自身を呼び出す」ことをメソッドの「再帰呼出し」 (recursive call) と言います。

メソッドの再帰呼出しの例

階乗(factorial)は数学的には以下のように定義できます。

    fact(n) = 1,                 if n=0
              n * fact(n-1),     otherwise

階乗の計算を行なうメソッドをプログラミングしてみましょう。 fact(n) → 1*2*3*...*(n-1)*n だと考えると、int fact(int n) は以下のように定義できます。

Fact2.java 階乗の計算 (繰り返しによる)

import java.util.*;
public class Fact2 {
    static int fact(int x) {
	int i,y;
	y=1;
	for (i=1; i <= x; i++)
	    y = y * i;
	return y;
    }
    public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n,ans;
	while (true) {
	    System.out.print("0以上の整数を入力して下さい。   ");
	    n = sc.nextInt();
	    if (n >= 0) break;
	}
	ans = fact(n);
	System.out.println(n+"の階乗は"+ans+" です");
    }
}

Fact2.java の実行

sp204: ~/pro 4> javac Fact2.java 
sp204: ~/pro 5> java Fact2 
0以上の整数を入力して下さい。   5 
5の階乗は120 です
sp204: ~/pro 6> java Fact2 
0以上の整数を入力して下さい。   0 
0の階乗は1 です
sp204: ~/pro 7> java Fact2 
0以上の整数を入力して下さい。   -1 
0以上の整数を入力して下さい。   7 
7の階乗は5040 です
sp204: ~/pro 8>

階乗の計算を再帰的なメソッド呼び出しを使ってプログラミングすると次のようになります。

Fact3.java 階乗の計算 (再帰呼び出しによる)

import java.util.*;
public class Fact3 {
    static int fact(int n) {
	int ans;
	if (n <= 0) ans = 1;
	else ans = n * fact(n-1);
	return ans;
    }
    public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n,ans;
	while (true) {
	    System.out.print("0以上の整数を入力して下さい。   ");
	    n = sc.nextInt();
	    if (n >= 0) break;
	}
	ans = fact(n);
	System.out.println(n+"の階乗は"+ans+" です");
    }
}

Fact3.java の実行

sp204: ~/pro 4> javac Fact3.java 
sp204: ~/pro 5> java Fact3 
0以上の整数を入力して下さい。   5 
5の階乗は120 です
sp204: ~/pro 6> java Fact3 
0以上の整数を入力して下さい。   0 
0の階乗は1 です
sp204: ~/pro 7> java Fact3 
0以上の整数を入力して下さい。   -1 
0以上の整数を入力して下さい。   7 
7の階乗は5040 です
sp204: ~/pro 8>

Fact3.javaと実質は同じですが、メソッドをもう少し短く書いた例が Fact4.java です。

Fact4.java 階乗の計算 (再帰呼び出しによる)

import java.util.*;
public class Fact4 {
    static int fact(int n) {
	if (n <= 0) return 1;
	return n * fact(n-1);
    }
    public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n,ans;
	System.out.print("0以上の整数を入力して下さい。   ");
	n = sc.nextInt();
	ans = fact(n);
	System.out.println(n+"の階乗は"+ans+" です");
    }
}

グラフィック用のクラス MyGraphics

以前の授業で ToyGraphics クラスを用いたプログラムを作りました。また、その次の回の授業ではToyGraphics を拡張して MyGraphics クラスを作りました。覚えていますか？

以下の例では MyGraphics クラスを利用します。

フラクタル図形

自然界では、ある物をどんどん細かくみていくと再び元の形が現れることがあります。そのような図形では、自分自身を縮小した図形を自分の一部分として含んでいることになります。これを自己相似形といいます。フラクタルとはそのようなパターンを扱う学問分野です。

フラクタル構造を持つものの例として、地形や樹木の形などが有名です。そこで、樹木の形を再帰的に定義して、グラフィックメソッドを用いて描いてみることにしましょう。

「あとどれだけ深く再帰呼び出しを繰り返すか」を (変数 level として) メソッドに渡していく方法で書いたプログラムが Fractal1.java です。

メソッド tree が void型になっていることに注意して下さい。値を返さないメソッドは void 型として宣言します。

Fractal1.java

public class Fractal1 {
    static void tree(int level,int x,int y,int length,double angle,double theta,MyGraphics mg) {
	int x1,y1,newlength;
	if (level <= 0) return;
	x1 = (int) (length * Math.cos(angle) + x);
	y1 = (int) (length * Math.sin(angle) + y);
	mg.drawLine(x,y,x1,y1,255,255,255); // 本体を描く
	newlength = (int) (length * 0.5);
	tree(level-1,x1,y1,newlength,angle,theta,mg); // 先の枝
	x1 = (int) (length * Math.cos(angle)/3 + x);
	y1 = (int) (length * Math.sin(angle)/3 + y);
	tree(level-1,x1,y1,newlength,angle+theta,theta,mg); // 右の枝
	x1 = (int) (length * Math.cos(angle)*2/3 + x);
	y1 = (int) (length * Math.sin(angle)*2/3 + y);
	tree(level-1,x1,y1,newlength,angle-theta,theta,mg); // 左の枝
    }
    public static void main(String[] args) {
	MyGraphics mg = new MyGraphics(); // ウィンドウを生成する
	tree(6,80,400,100,-Math.PI/2,Math.PI/6,mg); // 春: θ=π/6, level=6
	tree(7,240,400,100,-Math.PI/2,Math.PI/6,mg); // 夏: θ=π/6, level=7
	tree(7,400,400,100,-Math.PI/2,Math.PI/4,mg); // 秋: θ=π/4, level=7
	tree(5,560,400,100,-Math.PI/2,Math.PI/4,mg); // 冬: θ=π/4, level=5
    }
}

Fractal1.java の実行

sp204:~/pro 11> javac Fractal1.java 
sp204:~/pro 12> java Fractal1 
新しいウィンドウの中に絵が表示されます。右上の×をクリックすると終了します。
sp204:~/pro 13>

演習

課題

以下のような手順で計算できる数をフィボナッチ数と呼びます。

フィボナッチ数の定義
    fib(0) → 1
    fib(1) → 1
    fib(n) → fib(n-1)+fib(n-2)    n>=2 のとき

「整数を引数として受けとりフィボナッチ数を計算して返すメソッド」

    static int fib(int n)

を Fib.java というファイルの中に作って下さい。さらに、同じファイルの中に「キーボードから入力された整数を fib()メソッドの引数として渡して、その結果を表示する」 mainメソッドを作って下さい。

Fib.java

import java.util.*;
public class Fib {
    static int fib(int n) {
      // nが0の場合は 1 を返す
      // nが1の場合は 1 を返す
      // それ以外の場合は、再帰呼出しを使ってフィボナッチ数を計算した結果を返す
    }
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
        int i,j;
        while (true) {          // ０以上の値が入力されるまで繰り返す
            System.out.print("０以上整数を入力して下さい   ");
            i = sc.nextInt();
            if (i >= 0) break;
        }
        j = fib(i);
        System.out.println("フィボナッチ数は" + j + "です。");
    }
}

提出課題5

樹木曲線 (tree curve) を描くメソッド

void tree(int level,int x,int y,int length,double angle,double theta,MyGraphics mg)

をFractal2.javaというファイル中に作って下さい。さらに同じファイルの中に以下のようなmainメソッドを定義して実行させてみましょう。

Fractal2.java

public class Fractal2 {
    static void tree(int level,int x,int y,int length,double angle,double theta,MyGraphics mg) {
	int x1,y1,newlength;
	// levelが0以下ならばreturn
	// x1 を計算する
	// y1 を計算する
	// (x,y)と(x1,y1)の間に直線を描く
	// newlength を計算する
	// 右の枝を描くためにtreeメソッドを再帰呼出しをする
	// 左の枝を描くためにtreeメソッドを再帰呼出しをする
    }
    public static void main(String[] args) {
	MyGraphics mg = new MyGraphics(); // ウィンドウを生成する
	tree(14,320,479,100,-Math.PI/2,Math.PI/6,mg);
    }
}

提出方法

宿題提出WEBの「１年セミナー課題5」 http://nw.tsuda.ac.jp/tsuda/handin/up.php?id=2006/1semi/kadai5 から提出して下さい。

課題の提出〆切は7月30日 13:00です。〆切に遅れないように注意して下さい。

正しく提出されたかどうかを http://nw.tsuda.ac.jp/tsuda/handin/list.php?id=2006/1semi/kadai5 で必ず確認しておいて下さい。