再帰的プログラム

再帰的プログラムの簡単な例

繰り返し(for)の課題３で 1＋2＋3＋…＋n を計算するプログラムを作りました。

ファイル名 Kurikaeshi3.java

/** 1＋2＋3＋…＋n を計算する */
public class Kurikaeshi3 { 
    public static void main( String[] args ) {
       int n = 10;    //どこまで加えるか
       int s =  0;    //合計をいれておく変数
       for( int i=1; i<=n; i++ ) {
           s = s + i;
       }
       System.out.print( "１ から " );
       System.out.print( n );
       System.out.print( " までの和は " );
       System.out.println( s );
    }
}

これを「 n までの和は、n-1 までの和に n を足したもの」ということと、「 n=1 のときの 答えが １ 」ということに注目すれば、別のアルゴリズムでプログラムできます。

ファイル名 Saiki01.java

public class Saiki01{
    public static void main(String[] args) {
        int n = 10;
        System.out.println( n + "までの和 = " + madenowa(n));
    }
    static int madenowa(int i) {
        if(i==1) {
           return 1;
        }
        else{
           return i + madenowa(i-1);
        }
    }
}

madenowaというのはスタティックなメソッドです。（スタティックというのはインスタンスを作らなくても使えるメソッド）

madenowaの中でmadenowaが呼ばれている（使われている）ことに注目してください。

これだとプログラムが終わらないと思うかも知れませんが、i が １ になれば、終わります。つまり、１ まで足せば終わりということです。

メソッドの中で自分自身を呼ぶ。このような手法を使ったプログラムを再帰的プログラムとか、リカーシブルプログラムといいます。

課題

１．

ファイル名 Saiki01.java

上記プログラムを確認しなさい。

２．

1×2×3×…×n を計算するプログラムをつくれ。ただし、再帰的手法を使うこと。n は int n=10; などとプログラム内で与えるものとする。

ファイル名 Saiki02.java

３．

Saiki02.java の n をプログラムの開始時に引数として与えるようにしなさい。ただし、再帰的手法を使うこと。

Saiki01.java のように int で計算すると、ちょっと大きな数を入れられると計算限界を超える。long や double を使うように工夫すること。

ファイル名 Saiki03.java

引数から数値を得るには

int n = 10;
のかわりに
int n    = Integer.parseInt(args[0]);
long n   = Long.parseLong(args[0]);
double n = Double.parseDouble(args[0]);

メソッドは、

static long kaijou(long i) {
static double kaijou(double i) {

longでは20まで計算できる

15までの積 = 1307674368000
16までの積 = 20922789888000
17までの積 = 355687428096000
18までの積 = 6402373705728000
19までの積 = 121645100408832000
20までの積 = 2432902008176640000
21までの積 = -4249290049419214848

doubleでは…

120.0までの積 = 6.689502913449124E198
130.0までの積 = 6.466855489220472E219
140.0までの積 = 1.346201247571752E241
150.0までの積 = 5.7133839564458505E262
160.0までの積 = 4.714723635992059E284
170.0までの積 = 7.257415615307994E306
180.0までの積 = Infinity