関数の再帰呼び出しをうまく使いたい

こんにちは。mp_hskです。

本日のテーマは知ってるけど業務ではほとんど使わない再帰の復習。

再帰って??

関数(メソッド)内で自身を呼び出す方法。

ループが必要な処理をより簡単に書けることがある手法。

定番 n! を求める

再帰の定番として出題されるのは自然数 n の階乗を求めるプログラム。

こんな感じ。

public class Saiki1 {
    public static void main(String args) {
        System.out.println(kaijyo(5));
    }

    /**
     * n! を求める関数
     */
    private static int kaijyo(int n){
        if(n == 0){
            return 1;
        }else{
            return n * kaijyo(n -1);
        }
    }
}

この場合5!を求め、120が出力される。この仕組みを説明すると

kaijyo(5)

   → n != 0 なので 5 * kaijyo(4)

         → n != 0 なので 4 * kaijyo(3)

              → n != 0 なので 3 * kaijyo(2)

                   → n != 0 なので 2 * kaijyo(1)

                       → n != 0 なので 1 * kaijyo(0)

                            → n == 0 なので 1が返る

       ← 1 * 1 = 1が返る 

                  ←  2 * 1  = 2が返る

              ← 3 *2 = 6 が返る

         ← 4 * 6 = 24 が返る

     ←  5 * 24 = 120 が返る

ってな感じである。(わかりづらい?) 

階乗はループでも書けるが、ループで書くとこんな感じで少しかっこ悪くなる

public class Saiki1 {
    public static void main(String args) {
        System.out.println(kaijyo2(5));
    }

    /**
     * n! を求める関数
     */
    private static int kaijyo2(int n){
        if(n == 0){
            return 1;
        }else{
            int tmp = 1;
            for(int i = 1; i <= n;i++){
                tmp *= i;
            }
            return tmp;
        }
    }

}

エレガントなプログラムを書くにはやっぱり階乗ができるとうれしい。

フィボナッチ数列のn番目を求める

これも有名な問題。フィボナッチ数列とは

1 1 2 3 5 8 13 21 .... と n番目が a(n - 1) + a(n - 2)となる数列のこと。

今度は再帰版とループ版と一気に実装して確かめてみる。

public class Saiki2 {
    public static void main(String[] args) {
        System.out.println(fibo(15));
        System.out.println(fibo2(15));
    }

    /**
     * フィボナッチ数列のn番目を求める(再帰版)
     * n = 0の場合は1にする
     */
    private static int fibo(int n){
        if( n < 3){
            return 1;
        }else{
            return fibo(n - 1) + fibo(n - 2);
        }
    }

    /**
     * フィボナッチ数列のn番目を求める(ループ版)
     * n = 0の場合は1にする
     */
    private static int fibo2(int n){
        if(n < 3){
             return 1;
        }else{
            List<Integer> tmp = new ArrayList<Integer>();
            tmp.add(1);
            tmp.add(1);
            for(int i = 2;i < n;i++){
                tmp.add(tmp.get(i - 1) + tmp.get(i - 2));
            }
            return tmp.get(n - 1).intValue(); }
        }
    }

}

実行結果はどっちも同じ 610になるけどループ版の方は明らかに行数も多いし

無駄にListのオブジェクトを作っているので再帰の方がきれい。

まとめ

再帰は使いこなせるとプログラムをより短く、エレガントに書けるため身に着けたい。

今回はかなりメジャーで簡単なやつを書いたが、難しいアルゴリズムにもトライしたい(小並感)

 

ツッコミあればお待ちしてます。