クラスライブラリ応用 再帰的アルゴリズム (演習)

例題1: 再帰的定義を使った階乗計算

教科書 pp.152-155参照。 「ある処理」の方法を、「ある処理」自身を使って定義することを再帰的 (recursive) 定義と言う。

階乗の計算を取り上げ再帰の例を示す。階乗 n! は次のように説明できる。 

n! = 1 × 2 × 3 × … × n

しかし、この定義は「…」という部分を含んでいて曖昧である。 そこで、次のような方法で説明することを考える。 

n! = (n - 1)! × n
ただし n = 0 のとき n! = 1

n!の式の右辺にも (n - 1)! という階乗の計算そのものがあることに注意。 n!を計算するためには、(n - 1)! を計算して n を掛け、 (n - 1)! を計算するためには、(n - 2)! を計算して (n - 1) を掛け、 ということを n が 0 になるまで行えば良いことになる。 これをプログラムで表すと次のようになる。 

int fact(int n) {
    if (n == 0) return 1;
    else
        return fact(n - 1) * n;

}

このプログラムの実行の様子は以下のとおりである。 

fact(5) を計算するためには fact(4) * 5 を計算する必要がある
  fact(4) を計算するためには fact(3) * 4 を計算する必要がある
    fact(3) を計算するためには fact(2) * 3 を計算する必要がある
      fact(2) を計算するためには fact(1) * 2 を計算する必要がある
        fact(1) を計算するためには fact(0) * 1 を計算する必要がある
          fact(0) は定義より 1 である
        fact(0) = 1 の値が計算できたので fact(1) = 1 * 1 = 1
      fact(1) = 1 の値が計算できたので fact(2) = 1 * 2 = 2
    fact(2) = 2 の値が計算できたので fact(3) = 2 * 3 = 6
  fact(3) = 6 の値が計算できたので fact(4) = 6 * 4 = 24
fact(4) = 24 の値が計算できたので fact(5) = 24 * 5 = 120

例題2: 真に再帰的な問題 (フィボナッチ数)

教科書pp.158-160と類似の例題。 再帰的に定義される有名な数列にフィボナッチ数がある。 n番目のフィボナッチの数を fib(n) で表すと、 次のように定義される。 

fib(n) = fib(n - 2) + fib(n - 1)
ただし、n = 2 または n = 1 のとき fib(n) = 1

この数列は1, 1, 2, 3, 5, 8, ... と続く数列で、 隣り合う2つの数を足し算すると、その上位の数になる数列である。 例えば、 1+1=2, 1+2=3, 2+3=5, 3+5=8, ... と永遠に続いていく。 また、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, .... と 急速に大きくなることも知られている。

再帰的定義を用いてフィボナッチ数を求めるプログラムは以下のとおり。 

int fib(int n) {
    if (n == 1 || n == 2) return 1;
    else {
        int ans = fib(n - 2) + fib(n - 1);
        return ans;
    }
}

この計算方法の特徴は、 メソッドの中で2回の再帰呼び出しが行われていることである。 例えば、fib(5)の計算では fib(3) と fib(4) の2回の呼び出しを行う。

この計算の様子を図で表すと次のようになる。 

                fib(5)
                ／   ＼
              ／       ＼
            ／           ＼
         fib(3)          fib(4)
        ／   ＼          ／   ＼
    fib(1)   fib(2)   fib(2)  fib(3)
                             ／   ＼    
                          fib(1)  fib(2)

再帰を理解する練習として、計算の順序を 1 〜 9 まで番号づけしてみよう。

さて、この計算は再帰を使って書くと簡単であるが、実際の手順は複雑であるため 繰り返しで書き換えることは難しい。 このように、複数回にわたって再帰呼び出しを行う計算を「真に再帰的である」と言う。

再帰とリスト

先週学んだリストと再帰には構造的に類似していることがわかる。 以下に再帰とリストのプログラムを示す。

再帰 

int fact(int n) {
    if (n == 0) return 1;
    else
        return fact(n-1) * n;
}

リストのノード 

class Node {
    String element;
    Node next;
}

これらのプログラムで注目すべきポイントは、 両方とも自分から自分自身を使うような構造になっていることである。 リストも再帰を使って処理するのが容易なデータ構造の一つである。

再帰を使ってリストのノードを順にたどる

follow_r(x)の、xの初期値はheadとする。

void follow_r(Node p) {
    if (p == null)
        return;        <-- nullすなわちこれ以上たどるノードがなければ、何もせず戻る

    p に関する処理;
    follow_r(p.getNext());  <-- 次のノードを引数に与えて、再びこのメソッドを呼び出す
}

本日の課題 (12/6 20:30まで)

提出先: /home/submit/JavaLib/[出題日]/[学籍番号]

[注意] 本課題では、1つクラスを1つのファイルとして作成することを想定している。 ファイル名は、「public宣言を行ったクラスの名前.java」 である。 ファイルが別々であっても、同じディレクトリにあるpublic宣言されたクラスは、 相互に利用することができる。 (詳しく知りたい人は、「パッケージ」について調べると良い)

問題1

再帰的定義に基づき、2つのint型の数の最大公約数を求めるメソッド gcd を作成しなさい。 また、作成したメソッド gcd を呼び出して最大公約数を求め結果を表示する main メソッドも作成し、正しく動作することを確認しなさい。 提出ファイル名は Gcd.java とする。 

public class Gcd {
    public static void main(String[] args) {

        /* fill in here */

    }

    static int gcd(int a, int b) {

        /* fill in here */

    }
}

問題2

リストの回の問題で作成したクラス MyLinkedList を拡張し、 再帰呼び出しを使ってリストの内容を表示するメソッド print_r を作成しなさい。 クラス名は MyLinkedList2 とする。 (提出ファイル名 MyLinkedList2.java)

作成するメソッド

public void print_r()
リストの中身を順に表示するために、外部から呼び出されるフロントエンド用メソッド。 このメソッドは、単に次に示す引数付きのメソッドを呼び出すだけとする。
private void print_r(Node p)
再帰呼び出しを行ってリストの中身を表示する引数付きのメソッド。 p は表示対象のノードとし、 このメソッドを次々再帰呼び出しするように作る。 なお、このメソッドはクラス内部でだけ使われるため、 private 宣言すると良い。

次のようなmainメソッドで正しく動作することを確認すること。 

public class MyLinkedList2Main {
    public static void main(String[] args) {
        MyLinkedList2 list = new MyLinkedList2();

        System.out.println("空のリストの内容を表示 (何も表示されなければok)");
        list.print_r();

        System.out.println("=======================");
        list.addLast("Copernicus");
        list.addLast("Newton");
        list.addLast("Heisenberg");
        list.addLast("Einstein");
        list.addLast("Maxwell");

        System.out.println("リストの内容を表示 (Copernicus, Newton, Heisenberg, Einstein, Maxwellの順に表示されればok)");
        list.print_r();
    }
}

問題3 (Advanced: できたところまで提出)

前の問題で作成したクラス MyLinkedList2 をさらに拡張し、 再帰呼び出しを使ってノードの削除を行うメソッドを作成しなさい。 クラス名は MyLinkedList3 とする。 (提出ファイル名 MyLinkedList3.java)

作成するメソッド

public void remove_r(String elem)
リストから文字列 elem を有するノードを削除する、 このメソッドは、外部から呼び出されるフロントエンド用メソッドとし、 単に次に示す引数付きのメソッドを呼び出すだけとする。
private Node remove_r(String elem, Node p)
再帰呼び出しを使いリストを順番たどり、途中でelemと一致するノードがあった場合、 このノードを含まないようにリストを再構築する。 p は比較対象のノードとし、 このメソッドを次々再帰呼び出しするように作る。 なお、このメソッドはクラス内部でだけ使われるため、 private 宣言すると良い。

リスト再構成の考え方

メソッド remove_r(String elem, Node p) は次のような考え方で リストの再構成を行う。

ヒント

以下の断片を組み合わせることで remove_r メソッドを完成させることができる。 順番は各自考えること。 

    もし、pが削除すべきノードであれば、
        pの次のノードの在処を返す
    そうでなければ、
        pそのものの在処を返す

    再帰呼び出しによって返ってきた「次のノードの在処」をpのnextにセット

    if (p == null)
        return null;

次のようなmainメソッドで、正しく動作することを確認すること 

public class MyLinkedList3Main {
    public static void main(String[] args) {
        MyLinkedList3 list = new MyLinkedList3();

        list.addLast("Copernicus");
        list.addLast("Newton");
        list.addLast("Heisenberg");
        list.addLast("Einstein");
        list.addLast("Maxwell");

        list.print_r();

        list.remove_r("Copernicus");
        list.remove_r("Heisenberg");
        list.remove_r("Maxwell");

        System.out.println("=======================");
        System.out.println("削除後 Newton, Einstein が残っていればok");
        list.print_r();
    }
}

作成したプログラムが正しく動作するかどうか、必要かつ十分なテストを行うこと。

TOP > クラスライブラリ応用
東京電機大学 情報メディア学科