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) 값을 반환하게 된다.

유클리드 호제법

유클리드 호제법은 두 개의 정수 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
    }
}

실행 결과:

피보나치 수열

피보나치 수열의 알고리즘은 재귀를 두번 사용하여 만들 수 있고, 아래와 같이 정의된다.

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"이 된다.

최종 수정 : 2022-04-02