재귀 알고리즘

개념을 먼저 익힌 후에 백준 알고리즘을 푸는식으로 해야겠다. 맨땅에 헤딩식으로 하면 나는 잘 이해가 안되는 것 같다. 천천히 하더라도 깊이있게 해보자❗

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.

바로 예제로 가보도록 하자

팩토리얼 구하기

재귀의 예시로 팩토리얼이 있다.
n!(팩토리얼) 은 n * n-1 * n-2 * ... 이다.
이것을 그대로 코드로 표현하면 다음과 같다.

import java.util.Scanner;

public class Factorial {
    static int factorial(int n) {
        if(n > 0)
            return n * factorial(n - 1);
        else
            return 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n + "! = " + factorial(n));
    }
}

동작형식을 자세하게 보면 factorial(int n)은 n이 0보다 크면 n * factorial(n - 1) 를 호출하고 아니면 1을 반환한다.

풀어서 써보자.

예를 들어 n값에 3을 넣었다고 가정한다.

• n = 3
  • 3 * factorial(2);
  • 2 * factorial(1);
  • 1 * factorial(0);
  • return 1

이 순서로 들어가게 될텐데,

맨 마지막의 1부터 1 * 2 * 3 이 되는 것이다.
호출은 n = 3부터 시작했으니 정렬이 되면 3 * 2 * 1이 되게 된다.

이렇게 해서 3! 의 답인 6을 얻게된다.

내가 재귀를 볼때 막힘없이 봐야 이해가 쏙 되는것 같은 느낌 😂

한번에 안읽히면 머릿속에서 무한루프를 도는느낌이다.

항상 끝부터 쭉 나간다음 생각해 보는것이 이해가 잘된다❗

재귀 안썼을 때

static int factorial(int n) {
        int count = 1;
        
        for(int i = n; i > 0; i--) {
            count *= i;
        }
        
        return count;
    }

유클리드 호제법

최대공약수를 재귀로 구할 수 있다.

두 정수를 직사각형 두 변의 길이라고 가정하면 최대 공약수를 구하는 문제는 다음과 같아질 수 있다.

직사각형을 정사각형으로 완전히 채우고, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하자

4와 22 의 최대 공약수를 구해보자고 가정하면

1. 22 x 4에서 4를 한변으로 하는 정사각형으로 분할한다.
2. 5개의 4 x 4 정사각형이 생기고 2 x 2 두개가 남는다.
3. 이렇게 더이상 나눌 수 없는 2 x 2 정사각형이 생겼으므로 2가 최대 공약수이다.

public class Euclid {
    static int solution(int x, int y) {
        if(y == 0) {
            return x;
        }

        return solution(y, x % y);
    }

    public static void main(String[] args) {
        int x = 22;
        int y = 4;
        System.out.println(solution(x, y));
    }
}

단순하게 해석하면 0일때까지 계속 solution 자기 자신을 호출하면서 맨 마지막에 남은 x를 돌려주는 것이다.

재귀 안썼을 때

static int gcd2(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

배열 모든 요소의 최대 공약수

public class EucArray {

    static int euc(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    static int eucArray(int[] arr, int index, int length) {
        if(length == 1) {
            return arr[index];
        }

        if(length == 2) {
            return euc(arr[index], arr[index + 1]);
        }

        return euc(arr[index], eucArray(arr, index + 1, length - 1));
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 8, 12, 15};
        System.out.println(eucArray(arr, 0, arr.length));
    }
}

막상 풀어보니까 이렇게 복잡한거는 재귀보다는 다른 방법이 나아보이는....