第５講数値計算（2/2）

再帰呼び出し（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 Factorial3 {
    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メソッドは省略
}

例題の解答例

import java.util.ArrayList;

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(gcdValue, values.get(i));
        }
        System.out.printf("gcd(%s) = %d%n", String.join(", ", args), gcdValue);
    }
    Integer gcd(Integer x, Integer y) {
        if(y == 0) {
            return x;
        }
        return gcd(y, x % 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;
    }
    public static void main(String[] args){
        Gcd gcd = new Gcd();
        gcd.run(args);
    }
}

実行例

$ 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が発生します．

練習問題

1. GrandTotal改

第０講練習問題 3. 総和を求めるを再帰呼び出しを使って計算するプログラムを作成してください．クラス名は，GrandTotal2としてください．また，コマンドライン引数で最大値を与えられるようにしてください．

出力例

$ java GrandTotal2
1から10までの総和は55です．
$ java GrandTotal2 10
1から10までの総和は55です．
$ java GrandTotal2 100
1から100までの総和は5050です．
$ java GrandTotal2 90
1から90までの総和は4095です．

2. Fibonacci数列改

第１講練習問題 5. Fibonacci数列を再帰呼び出しを使って計算してみましょう． Fibonacci数列の $n$項目の値を出力してください．クラス名はFibonacci2としてください．

コマンドライン引数に値が指定されない場合は，10項目が指定されたものとしてください．コマンドライン引数に複数個の数値が与えられた場合，全ての数値に対して結果を出力してください．

出力例

$ java Fibonacci2
fobonacci(10) = 55
$ java Fibonacci2 1 2
fibonacci(1) = 1
fibonacci(2) = 1
$ java Fibonacci2 4 10 20
fibonacci(4) = 3
fibonacci(10) = 55
fibonacci(20) = 6765
$ java Fibonacci2 40
fibonacci(40) = 102334155

3. 最小公倍数

コマンドライン引数で与えられた全ての数値の最小公倍数（Least Common Multiple）を求めるプログラムを作成してください．クラス名は Lcm としてください．なお，2つの数の最小公倍数は次の式で求められます．最大公約数（gcd）は例題の通りです．

\[ {\rm lcm}(a, b)=|ab|/{\rm gcd}(a, b) \]

出力例

$ java Lcm 3 6
lcm(3, 6) = 6
$ java Lcm 30 42
lcm(30, 42) = 210
$ java Lcm 3 6 9 18
lcm(3, 6, 9, 18)=18
$ java Lcm 1 2 3 4 5 6 7 
lcm(1, 2, 3, 4, 5, 6, 7)=420

ヒント

処理の流れ

与えられた全ての数（$a_1, a_2, ..., a_n$）の最小公倍数を求めるには，次のように計算すると良いでしょう．つまり，最初の2つの数（$a_1$と$a_2$）の最小公倍数を求め，$l_1$ とする．次に，$l_1$と$a_3$の最小公倍数を求め，$l_2$とする．続けて，順番に最小公倍数を求めていくと良いでしょう． \[ {\rm lcm}({\rm lcm}({\rm lcm}(a_1, a_2), a_3), ...) \]

文字列の結合

文字列を特定の文字で区切って結合するには，String.joinメソッドを使うと良いでしょう．

String[] array = // ... "1", "2", "3", "4"
String joined = String.join(", ", array); // "1, 2, 3, 4"という文字列が得られる．

その他

絶対値を求める

4. 回文チェッカー

コマンドライン引数で与えられた文字列（複数指定可）が回文（palindrome）であるかどうかを確認するプログラムを作成してください．回文とは，始めから読んだ場合と終わりから読んだ場合とで，文字の出現する順番が同じである文字列のことを指します（本来は意味の通じるように，という条件もありますが，プログラムでは判断するのは難しいので，意味については関知しないものとします）．

クラス名は PalindromeChecker としてください．

出力例

$ java PalindromeChecker akasaka
akasaka: true
$ java PalindromeChecker ABBA madamimadam
ABBA: true
madamimadam: true # Madam, I'm Adam
$ java PalindromeChecker あかさか わにのにわ つつみがみっつ
あかさか: false
わにのにわ: true
つつみがみっつ: false

一般的な回文では，濁音，半濁音，促音，拗音は清音と同一視されます（つつみがみっつは回文として扱われる）．しかし，処理がややこしくなりますので，上記の条件は無視して良いです（つつみがみっつは回文として扱わなくて良いです）．

ヒント1: 文字列のn文字目を取得する．

文字列（String型）のn文字目を取得するには，charAtメソッドを用います． charAt メソッドは１つのInteger型の値を受け取り，Character型の変数を返します．

String string = "abracadabra";
Character c1 = string.charAt(0);
    // => 'a'（１文字目の'a'）
Character c1 = string.charAt(string.length() - 1);
    // => 'a'（最後の文字の'a'）

ヒント2: 部分文字列を取得する

文字列（String型）の部分文字列を取得するには，substringメソッドを用います． substring メソッドは１つ，もしくは２つのInteger型を受け取ります．

String string = "abracadabra";
String sub1 = string.substring(2);
    // => "racadabra"
String sub2 = string.substring(2, string.length() - 2);
    // => "racadab"
String sub3 = string.substring(1, string.length() - 1);
    // => "bracadabr"

ヒント3: 考え方

次の考え方で回文であるかを判定できます．

まず，isPalindrome メソッドを定義しましょう．引数は１つのString型を受け取り，Boolean型を返します．

メソッドの最初で，文字列の長さが1文字以下ならば回文であると判定します．
そうでないなら，受け取った文字列から最初の文字（first）と最後の文字（last）を取得します（文字列のn文字目を取得する）．
first と last が一致しなければ，回文ではないと判定します．
最初と最後の文字を除いた部分文字列を取得します（部分文字列を取得する）．
取得した部分文字列を引数にして，isPalindromeを呼び出し，その結果をメソッドの返り値とします．

以下も参照してください．

まとめ

あるメソッドの中で自分自身を呼び出せる．
- 再帰呼び出しと呼ぶ．
- 再帰呼び出しのメソッドは，必ず再帰から抜ける脱出口が存在する．
  - もし，存在しなければ，StackOverflowExceptionが発生する．
    - メソッド呼び出しが深すぎて，それ以上メソッドを呼び出せない状態．
その他
- 文字列のn文字目を取得する
- 部分文字列を取得する

第５講 数値計算（2/2）

第５講 数値計算（2/2）のサブセクション