再帰呼び出し（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）を返します．
例題 階乗改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);
という一文を入れて実行してみても良いでしょう．
再帰呼び出しの失敗
再帰呼び出しには，必ず再帰からの脱出口を設ける必要があります．
上の例で言えば，if(number == 1){ return 1; } が脱出口になっています．
もし，脱出口が設けられていない，もしくは，設けられていても，適切な条件でなければ再帰から抜け出せず，StackOverflowExceptionが発生します．