教育サーバーのページ
オンラインテキスト目次
コンピュータリテラシー演習
ソフトウエア入門演習
教育サーバーのページ
オンラインテキスト目次
コンピュータリテラシー演習
ソフトウエア入門演習
n! とは、普通
n! = n x (n-1) x ・・・・ x 3 x 2 x 1で定義される（ただし、
0! = 1 と定義しておく）。
例：階乗の非再帰版メソッド
┏━━━━━━━━━ fact0.java ━━━━━━
/*
usage:
java fact0 9
9 の階乗 = 362880
*/
public class fact0 {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
if (n <0)
System.out.println("非負の整数値を入力してください");
else
System.out.println(n + " の階乗 = " + factorial(n));
}
static int factorial(int n){
int fact = 1;
if (n == 0)
return fact;
else { // in case of n > 0
for (int i = n; i > 0; i--)
fact *= i;
return fact;
}
}
}
しかし、次の階乗関数の再帰的定義の方が階乗の意味がずっとわかりやすい：
1 if n = 0
n! =
n x (n-1)! otherwise
これは次のようなメソッドとしてプログラムできる。
この方法が再帰的プログラミングというものである。
すっきりとしたでしょ？
┏━━━━━━━━━ 階乗を求める再帰的メソッド ━━━━━━
static int factorial(int n){
if (n == 0)
return 1;
else // in case of n > 0
return n * factorial(n - 1);
}
上のプログラムを見ると分かるように、factorial(n) の値を求めるメソッド定義で、factorial(n - 1) と自分自身を使っている。 つまり、自己参照している。 それゆえに、このようなプログラミングスタイルを再帰的と呼ぶのである。
さて、factorial(n - 1) の値を知るためには factorial(n - 2) が必要で、それを知るには factorial(n - 3) が、、ということになる。 しかし、factorial(0) の値が与えられているために、この過程を逆にさかのぼって必要な値が求まるという仕組みになっている。
再帰的プログラミングでは、このようにさかのぼって行ったときに、最後に具体的値（や手続き）が定義されているように書かねばならない。 そのような遡りが有限回数で終了して値（や手続き）が定義されていないと、無限に遡り続けようとして終了しないことになる。
Fibonatti数列
次のような値をもつ数列を Fibonatti（フィボナッチ）数列という。
0番目が 1、1番目が 1 とする。
2番目の値は 0番目と1番目の値を足したもの、3番目の値は1番目と2番目の値を足したもの、4番目の値は2番目と3番目の値を足したもの、、、、、。
Fibonatti数列の最初の項は次のようになる：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ......
このとき、は非負の整数 n に対して fibonatti(n) を返す非再帰的メソッド fibonatti(int n) を書いて
java fibo0 11 11 番目のFibonatti数 = 144と動作する java プログラム fibo0.java を書いて実行し、Fibonati数の20項まで求めよ。
2.0 の 0 乗 = 1.0 2.0 の 2 乗 = 4.0 2.0 の 3 乗 = 8.0 2.0 の -1 乗 = 0.5 2.0 の -2 乗 = 0.2 2.0 の 2 乗 = 4.0
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .....とうような数集合である（ここでは自然数にゼロも含めておく）。
いま、自然数 n に対して次の操作（メソッド） suc しか定義されていないとする：
suc(n) = n の後にある数 = n'
ここで suc(n) の値 n' を n + 1 と記していないことに注意する。 なぜなら、また足し算 + は定義されていないのであるから。たとえば、suc(2) = 3, suc(5) = 6 などである。 つまり、suc(n) は自然数が 0 から小さい順に並べてあるとき、自然数 n の後ろにある自 然数を与える関数であり、これを後者関数（successor）と呼び、基本的な原始帰納関数の1つである。
数 n の前の数を与える前者関数（predecessor） pred を次のように再帰的に定義する：
pred(n) = 0 if n = 0 pred(suc(n)) = n if n > 0
ここでも pred(n) の値 を n - 1 と記していないことに注意する。 なぜなら、また引き算 - は定義されていないのであるから。以降、自然数に対する基本演算である足し算（+）や引き算（-）、かけ算（*）をこの後者関数を使って再帰的（または帰納的ともいう）に定義していく。
┏━━━━━━━━━ suc(int n) と pred(int n) ━━━━━━
static int suc(int n){
return n + 1;
}
static int pred(int n){
if(n == 0)
return 0;
else
return n - 1;
}
x if y = 0
sum(x, y) =
suc(sum(x, pred(y))) if y > 0
例えば、sum(2, 3) は次のように求めることができる：
sum(2, 3) = suc(sum(2, 2)) = suc(suc(sum(2, 1)))
= suc(suc(suc(sum(2, 0))))
= suc(suc(suc(2))) = suc(suc(3))
= suc(4)
= 5
自然数 x から自然数 y の差（difference）
をとる関数 diff(x, y) を次のように定義する：
自然数の範囲でしか考えていないので、このような定義になる。
x if y = 0
diff(x, y) =
pred(diff(x, pred(y))) if y > 0
例えば、diff(4, 2) は次のように求めることができる：
diff(4, 2) = pred(diff(4, 1)) = pred(pred(diff(4, 0)))
= pred(pred(4)) = pred(3)
= 2
% java primitive 12 3 12 と 3 の和 = 15 12 と 3 の差 = 9 12 と 3 の積 = 36
ソフトウエア入門演習
コンピュータリテラシー演習
オンラインテキスト目次
教育サーバーのページ