再帰呼び出し(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

第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が発生します.