Algorithm | 再帰関数(Recursion Function)

再帰関数

再帰関数は、処理中に自分自身を呼び出す関数を指す。
例えば、1からNまでの合計を求める関数は、再帰を使って次のように定義できる。

public class SumRecursion {

    public int sum(int n) {
        if(n == 0) {
            return 0;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        SumRecursion recursion = new SumRecursion();
        int result = recursion.sum(10);
        System.out.println(result); // 55
    }
}

実行結果:

注意点は、sum(10)を呼び出しているが、最初に値を返すのはsum(0)である。そして最後にsum(10)の値が返される。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数m、nの最大公約数(GCD(m, n))を求めるアルゴリズムである。

mをnで割ったとき、余りをrとすると、以下のように定義される。

GCD(m, n) = GCD(n, r)

再帰関数を使うと、数学で有名なユークリッドの互除法アルゴリズムを書ける。

public class GcdRecursion {

    public int gcd(int m, int n) {
        if(n == 0) {
            return m;
        }
        return gcd(n,  m % n);
    }

    public static void main(String[] args) {
        GcdRecursion recursion = new GcdRecursion();
        int result = recursion.gcd(30, 7);
        System.out.println(result); // 1
    }
}

実行結果:

フィボナッチ数列

フィボナッチ数列のアルゴリズムは再帰を2回使って作ることができ、以下のように定義される。

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n = 2, 3, ...)

public class FibonacciRecursion {
    
    public int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        FibonacciRecursion recursion = new FibonacciRecursion();
        int result = recursion.fibonacci(10);
        System.out.println(result); // 55
    }
}

実行結果:

ここで作成したフィボナッチ数列のアルゴリズムの計算量はO((1+√5)^n/2)である。

aからbまでの合計を求める

以下のコードは、aからbまでの合計を求める例である。

package com.devkuma.algorithum.programming.recursion;

public class SumRangeRecursion {

    int sumRange(int a, int b) {
        if (a == b) {
            return a;
        }
        return sumRange(a, b - 1) + b;
    }

    public static void main(String[] args) {
        SumRangeRecursion recursion = new SumRangeRecursion();
        int result = recursion.sumRange(1, 3);
        System.out.println(result); // 6
    }
}

実行結果:

上の例では、1 + 2 + 3 + 4 + 5 = 15のように計算される。

これを展開すると以下のようになる。

sumRange(1, 5) = sumRange(1, 5 - 1) + 5 > sumRange(1, 4) + 5 > 10 + 5 = 15
sumRange(1, 4) = sumRange(1, 4 - 1) + 4 > sumRange(1, 3) + 4 > 6 + 4 = 10
sumRange(1, 3) = sumRange(1, 3 - 1) + 3 > sumRange(1, 2) + 3 > 3 + 3 = 6
sumRange(1, 2) = sumRange(1, 2 - 1) + 2 > sumRange(1, 1) + 2 > 1 + 2 = 3
sumRange(1, 1) = 1

素数かどうかの判定

以下のコードは、素数かどうかを判定する例である。

public class PrimeRecursion {

    boolean hasDivisor(int n, int i) {
        if (i == n) {
            return false;
        }
        if (n % i == 0) {
            return true;
        }
        return hasDivisor(n, i + 1);
    }

    boolean isPrime(int n) {
        if (n == 1) {
            return false;
        } else if (n == 2) {
            return true;
        } else {
            return !hasDivisor(n, 2);
        }
    }

    public static void main(String[] args) {
        PrimeRecursion recursion = new PrimeRecursion();
        boolean result1 = recursion.isPrime(7);
        System.out.println(result1); // true

        boolean result2 = recursion.isPrime(4);
        System.out.println(result2); // false
    }

}

実行結果:

true
false

相互再帰: 奇数・偶数判定

以下のコードは、奇数と偶数を判定する例であり、メソッド同士が互いに呼び出し合う相互再帰関数として実装されている。

package com.devkuma.algorithum.programming.recursion;

public class EvenOddRecursion {

    boolean isEven(int n) {
        if (n == 0) {
            return true;
        }
        return isOdd(n-1);
    }

    boolean isOdd(int n) {
        if (n == 0) {
            return false;
        }
        return isEven(n-1);
    }

    public static void main(String[] args) {
        EvenOddRecursion recursion = new EvenOddRecursion();

        System.out.println(recursion.isEven(8)); // true
        System.out.println(recursion.isEven(9)); // false
        System.out.println(recursion.isOdd(8)); // false
        System.out.println(recursion.isOdd(9)); // true
    }
}

実行結果:

true
false
false
true

配列から最大値を求める

以下のコードは、入力された配列aで個数nまでの最大値を求める例である。

public class MaxArrayRecursion {

    public static int max(int[] a, int n) {
        int x;
        if (n == 1) {
            return a[0];
        } else {
            x = max(a, n - 1);
        }

        if (x > a[n - 1]) {
            return x;
        }
        return a[n - 1];
    }

    public static void main(String[] args) {
        int arr[] = {0, 80, 60, 40, 20, 100};
        System.out.println(max(arr, 3));
    }
}

実行結果:

入力された配列aで3番目までを見ると"0, 80, 60"であり、その中で最も大きい値は"80"になる。