【Java アルゴリズム修行⑩】再帰アルゴリズム

再帰とは

再帰と言われても、再起しか思い浮かばなかったのでまずは定義を調べてみましょう。

ある事象において、それが自分自身を含んでいたり、
自分自身を用いて定義されていたりするのであれば、再帰的であると表現できる

ふむ。。 ちょっと良くわからないですね
よく再帰の例で使用される階乗（3だったら 3×2×1という具合に求めるやつですね）をコードでみてみましょう。

import java.util.*;

    public class Main {
        public static void main (String... args){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            System.out.println(n + "の階乗は " + fuctional(n));
        }

        static int fuctional(int n){
            if (n > 0){
                return n * fuctional(n-1);
            }else{
                return 1;
            }
        }
    }

入力値が3であれば、 functional(3)という形でメソッドを呼ぶことになりますが、
中身は 引数が 1以上であれば、引数 × functional(引数 - 1)という形で自分自身のメソッドを呼び、
0以下であれば 1を返すといったものです。

なるほど、どうやら自分で自分自身を再度呼ぶようなフローのことを再帰というらしいですね。。
ただ動きがいまいち分かりにくいので、一つずつ追ってみましょう。

functional(3)で呼ばれたら
3 × functional(3 - 1)となり、functional(2)が呼ばれます。 2 > 0なので、そのまま
2 × functional(2 - 1)となり、functional(1)が呼ばれます。 1 > 0なので、そのまま
1 × functional(1 - 1)となり、functional(0)が呼ばれます。 0 > 0ではないので、ここで1がreturnされます

それぞれのfunctionalで返す値を並べてみると、

functional(3 - 1)　→ 2 × functional(2 - 1)
functional(2 - 1) → 1 × functional(1 - 1)
functional(1- 1)→ 1

となるので、頭から並べると 3　× 2 × 1 × 1 = 6 ということで階乗が成立します。
図にするとこんな感じです。

自分自身のメソッドを呼び出す　というよりも、自分自身と同じメソッドの呼び出しを繰り返すという理解が自然かもしれません。
同じメソッドを繰り返すので、永遠にループしてしまうんじゃないかとも思いましたが、
if(n > 0)という条件文を配置し、fuctional(n-1)ということで引数を減らしているので
無限ループにはならない再帰呼び出しということですね。。！

ユークリッド互除法

先ほどは階乗でしたが、次に2つの整数値の最大公約数を再帰的に求める方法を再帰で考えてみましょう。
2つの整数値の約数を並べて、お互い一致する値の最大値を求める。。というやり方もありそうですが、
この問題に対して、古代エジプトのエウクレイデスさんは、ユークリッドの互除法というのを思い付きます

エウクレイデスさんは以下のように考えました。

2つの整数値を長方形の2辺の長さとすると、2つの整数値の最大公約数を求める問題は、以下のようになる。。
2つの整数値の最大公約数 =「幾つかの数の共通の約数のうち、最小のもの」

ある長方形を、正方形で埋めて作ったとき、正方形の最大の辺の長さが最大公約数じゃん！という閃きですね。変態ですね。
例えば、

辺の長さが48、高さが18である下のような長方形を例に考えてみます。

まず最初に18の正方形2つを埋めることができ、残りの1つは高さ18、幅12の四角形
となりました。
そこから12の正方形1つを埋めることができました。　残りの1つは 高さ6 幅12の四角形となったので、
6の正方形を2つ埋めることで、これで最初の長方形を全て正方形で埋めることができました。

このとき、最小の正方形が6であるので、48と18の最大公約数は6ということになります。
これだけだとただの数学の話なのですが、求める手順が同一なことに気が付いたでしょうか？？
上記の正方形にする手順を計算にすると下記のようになります。

48 ÷ 18 = 2...12
18 ÷ 12 = 1...6
12 ÷ 6 = 2　

2つの整数値が与えられたとき、大きい方の値を小さい方の値で割り、割り切れる場合は小さい方が最大公約数
割り切れない場合は、小さい方の値と、剰余で同じ手続きを踏めば割り出すことができるということですね！

手順が同じであれば、再帰で求めることができそうなので、早速コードにしてみましょう！

import java.util.*;

    public class Main {
        public static void main (String... args){
            Scanner sc = new Scanner(System.in);
            int x = sc.nextInt();
            int y = sc.nextInt();
            System.out.println(x + "と" + y +"の最大公約数は" + gcd(x,y));
        }

        static int gcd(int x, int y){
            if (y == 0){
                return x;
            }else{
                return gcd(y, x % y);
            }
        }
    }

実際の手順はgcdメソッドで行っていますが、
具体的には引数で持ってきた2つの値を y が 0になるまで再帰的に余剰を求め続けています。
先ほどの長方形であれば
gcd(48,18)として、48 % 18 での返り値は2なので
gcd(18,12)となり 18 % 12 での返り値は6なので
gcd(12,6)となり、割り切れるため gcd(6,0)となり、 y == 0 となるのでxが返されますね！

仮に x < y で渡したとしても、gcd (18 ,48) となり、18 % 48 の返り値は 18 となるので
gcd(48, 18)と逆転して同じように処理が繰り返されます。

剰余があればそれを小さい方の値で割って見て。。と言うのを繰り返しているので再帰で求めるのが早いというのは納得ですね！

真の再帰

ここまでの再帰呼び出しは1回だけでしたが、これを2回行うのが真の再帰と呼ばれているらしいです。（さっきのは偽なのか。。）
まずは下記コードをみてみましょう。

import java.util.*;

    public class Main {
        public static void main (String... args){
            Scanner sc = new Scanner(System.in);
            int x = sc.nextInt();
            recur(x);
        }

        static void recur(int n){
            //nが正の時は処理を続ける
            if (n > 0){
                recur(n-1);
                System.out.print(n);
                recur(n-2);
            }else{
                return;
            }
        }
    }

ここで4という値を入力してみると、出力されるのは1231412という数列になります。

流れを追ってみると、まずはrecur(4)というのが呼ばれて、その後に4という値を出力していますが、
実際に4という値が出力されるのは5番目となっており、かなり後の方に呼ばれています。
一通りの処理を追ってみるとこんな感じです。

まずはrecur(4)が呼ばれますが、
その後recur(3)が呼ばれ→recur(2)が呼ばれ→recur(1)が呼ばれ→recur（0）が呼ばれ　ここで初めて n > 0で returnがおきます
recur(1)に戻り、 System.out.print(1)として1が出力され次に、recur(-1)が呼ばれ、 ここでも同様にreturnが起きるので
recur(2)に戻り、System.out.print(2)として2が出力され次に、recur(0)が呼ばれ、ここでも同様にreturnが起きるので
recur(3)に戻り、System.out.print(3)として3が出力され次に、recur(1)が呼ばれ、1が出力され、recur(-1)が呼ばれreturnされます
recur(4)に戻り、System.out.print(4)として4が出力され次に、recur(2)が呼ばれ、
recur(1)が呼ばれるので、1が出力され、returnし、2が出力され、recur(0)となるのでここで終了します。

上から下に流れていく順次処理でみると、違和感がありますが、実際には下記のような形で呼ばれています。

青い矢印を辿って1個下流の箱へと移動し、returnまでいけば、赤文字部分を表示してから、赤い矢印に戻っていくと言う流れですが
こうしてみるとなかなかに複雑な呼ばれ方をしていまね。。

recur(-1)~recur(4)までのそれぞれの挙動をまとめてみるとこんな感じになります。

recur(4) → recur(4-1)が呼ばれて 4が出力されて recur(4-2)が呼ばれるという流れで
あとはそれぞれの出力を当てはめていけば 1231412という数列を割り出すことができますね！

ハノイの塔

再帰アルゴリズムでで解く有名な問題に「ハノイの塔」というものがあります。
ルールは下記の通りです。

• 3本の杭と、大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の軸に大きい円盤から順に重ねられている。
• 円盤を一回に一枚ずつどこかの軸に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

なんでこんなことすんねんって感じですが、渋々解いてみましょう。

円盤の移動手順をシンプルにして考えてみます。
最初に積まれている円盤をa、移動先の軸をb、残りの軸をcとしたとき、

一番底にある円盤以外をaからcに移動し、bに一番底の円盤を移動したら
あとはcの円盤をbに移動するという流れで考えることができそうです。

import java.util.Scanner;

class Hanoi {

    static String[] name = {"Ａ軸", "Ｂ軸", "Ｃ軸"};

    //--- 円盤をx軸からy軸へ移動 ---//
    static void move(int n, int x, int y) {
        if (n > 1) {
          move(n - 1, x, 6 - x - y);
        }

        System.out.println("円盤[" + n + "]を" + name[x - 1] + "から" + name[y - 1] + "へ移動");

        if (n > 1) {
          move(n - 1, 6 - x - y, y);
        }
    }

    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);
        System.out.println("ハノイの塔");
        System.out.print("円盤の枚数：");
        int n = stdIn.nextInt();

        move(n, 1, 3);   // 第1軸に積まれたn枚を第3軸に移動
    }
}

A,B,Cと軸の合計を1,2,3で表しているので、軸番号の合計は6となり、
一番底の円盤以外を避難させる中間軸（B）は常に 6 - x - y で表すことができます。

基本的には下記の動作を動かす円盤が0になるまで行います。
① 底の円盤を除いたグループ（円盤[1]〜円盤[n-1]）をAからCへ
② 底の円盤nをAからBへ移動した旨を表示
③ 底の円盤を除いたグループ（円盤[1]〜円盤[n-1]）をCからBへ

実際に動かしてみると下記のような出力が得られたので無事に円盤を移動することができました！

ハノイの塔
円盤の枚数：3
円盤[1]をＡ軸からＣ軸へ移動
円盤[2]をＡ軸からＢ軸へ移動
円盤[1]をＣ軸からＢ軸へ移動
円盤[3]をＡ軸からＣ軸へ移動
円盤[1]をＢ軸からＡ軸へ移動
円盤[2]をＢ軸からＣ軸へ移動
円盤[1]をＡ軸からＣ軸へ移動

学んだこと

• 自分自身と同じメソッドの呼び出しを繰り返すことを再帰的という
• 再帰は、引数が同じものも繰り返されるので、引数ごとに分けて考えると理解しやすい
• 引数の値を操作することによって呼び出す回数を制御することができる

再帰というと無限ループを起こしてしまうものだとばかり思っていましたが、
実際は引数を用いて呼び出しを制御できることが分かりました！
コードとしても複雑な処理を、メソッド1つだけ定義して、あとはそれを再帰的に呼ぶことで
処理が完了してしまうという流れもみることができ、実務では、親DBが子DB一覧を呼んで、子DBが孫DB一覧を呼んで、、
というような親子関係のDB構造を扱うときに使用することがあるかもしれないので、引き続き頑張っていきます！