再帰呼び出し（Recursive call）
再帰呼び出しとは
再帰呼び出しとは，あるメソッド中でそのメソッド自身を呼び出しているメソッドを，再帰呼び出しメソッドと呼びます． 再帰呼び出しを使うと問題が簡単に解ける場合もあります．
例えば，次のようなメソッドのことを再帰呼び出しメソッドと呼びます．
Integer recursive(Integer value){
if(value == 1){
return 1;
}
return recursive(value - 1) + value;
}
このプログラムは，${\rm sum}(n)=\sum_{i=1}^{n} i$を計算するメソッドです． 漸化式と馴染みの深いプログラミングテクニックです． なお，この式は漸化式では次の通りになります．
\[
{\rm sum}(n) = \begin{cases}
1 & n=1\\
n + {\rm sum}(n-1) & n> 1
\end{cases}
\]
$n$（value）が 1 の時は 1 を返し，それ以外の場合は，$n + {\rm sum}(n - 1)$（recursive(value - 1) + value）を返します．
例題1 階乗改2
第１回目の練習問題 3. 階乗を別の書き方をしてみましょう． $n$の階乗は，$n!=n×(n−1)×(n−2)…2×1$ で求められます． この式を漸化式で表すと次の通りです．
\[
n! = \begin{cases}
1 & n=1\\
n \times (n-1)! & n> 1
\end{cases}
\]
Javaプログラムでこの漸化式を表してみましょう．
public class Factorial2{
void run(String[] args){
for(Integer i = 0; i < args.length; i++){
Integer number = Integer.valueOf(args[i]);
this.print(number, this.factorial(number));
}
}
Integer factorial(Integer number){
if(number == 1){
return 1;
}
return number * this.factorial(number - 1);
}
void print(Integer number, Integer result){
System.out.printf("%d! = %d%n", number, result);
}
// mainメソッドは省略．
}
上記プログラムのfactorialメソッドに注目してください．
引数のnumberの値が1の場合は，返り値として1を返します．
そして，numberの値が1以外の場合は，引数として与える数を変更して，factorialメソッドを再度呼び出しています．
あるメソッドから，自分自身を呼び出すことを再帰呼び出しと呼びます．
上に示した漸化式で考えると理解が容易でしょう．
また，動作を確認するために，上記プログラムのfactorial
メソッドの先頭にSystem.out.printf("factorial(%d)%n", number);
という一文を入れて実行してみても良いでしょう．
実行例
$ java Factorial2 8
8! = 40320
$ java Factorial2 2 5 6
2! = 2
5! = 120
6! = 720
例題2 最大公約数
次に，2つの整数値の最大公約数（Greatest Common Divisor）をユークリッド互除法（Euclidean Algorithm）により求めてみましょう．
ユークリッド互除法は次の漸化式で求められます．
ただし，$x \ \rm mod \ y$は $x$を$y$で割った余り（x % y）を表します．
\[
{\rm gcd}(x, y) = \begin{cases}
x & y = 0のとき \\
{\rm gcd}(y, x\ {\rm mod}\ y) & y \neq 0 のとき
\end{cases}
\]
public class Gcd {
void run(String[] args) {
if(args.length <= 1) {
System.out.println("java Gcd <number> <numbers...>");
return;
}
ArrayList<Integer> values = convert(args);
Integer gcdValue = values.get(0);
for(Integer i = 1; i < values.size(); i++){
gcdValue = // gcd を呼び出してください．
}
System.out.printf("gcd(%s) = %d%n", String.join(", ", args), gcdValue);
}
Integer gcd(Integer x, Integer y) {
if(/* y が 0のとき */) {
return x;
}
// gcd(y, x mod y) を呼び出す
}
ArrayList<Integer> convert(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
for(Integer i = 0; i < args.length; i++){
list.add(Integer.valueOf(args[i]));
}
return list;
}
// mainメソッドは省略
}
実行例
$ java Gcd 9 18
gcd(9, 18) = 9
$ java Gcd 9 18 12 27
gcd(9, 18, 12, 27) = 3
再帰呼び出しの失敗
再帰呼び出しには，必ず再帰からの脱出口を設ける必要があります．
上の例で言えば，if(number == 1){ return 1; } が脱出口になっています．
もし，脱出口が設けられていない，もしくは，設けられていても，適切な条件でなければ再帰から抜け出せず，StackOverflowExceptionが発生します．