23.10.30) TIL - 재귀함수

코딩테스트를 풀다가 재귀함수에 대해 알게되어서 정리해보았다.

재귀함수란(Recursive Function)?

자기 자신을 호출하는 함수, 재귀 함수는 문제를 더 작은 부분 문제로 분할하여 해결하는데 사용되며, 종종 반복적인 작업을 간단하게 만드는 데 유용하다.

public class RecursiveExample {
    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println("5의 팩토리얼은 " + result + "입니다.");
    }

    public static int factorial(int n) {
        // 기저 사례: n이 0 또는 1일 때
        if (n == 0 || n == 1) {
            return 1;
        } else {
            // 재귀 호출: n! = n * (n-1)!
            return n * factorial(n - 1);
        }
    }
}

위의 예제에서 factorial 함수는 재귀적으로 자기 자신을 호출하여 n의 팩토리얼을 계산한다.

 

재귀함수를 사용할 때 주의할 점

1. 기저 사례(Base Case): 재귀 함수는 무한 루프를 방지하기 위해 항상 하나 이상의 기저 사례를 가져야 합니다. 기저 사례는 재귀 호출을 멈추는 조건을 정의합니다. 위의 예제에서는 n이 0 또는 1일 때 팩토리얼 값을 1로 반환하여 재귀 호출을 종료합니다.

2. 작은 문제로 분할: 재귀 함수는 주어진 문제를 더 작은 하위 문제로 분할하고, 이 작은 하위 문제를 해결하기 위해 자신을 호출합니다. 이렇게 하면 문제가 해결 가능한 크기로 줄어들고, 재귀 호출이 종료될 수 있습니다.

3. 재귀 호출: 함수 내에서 자기 자신을 호출하여 하위 문제를 해결합니다. 재귀 호출은 종료 조건에 도달할 때까지 계속됩니다.

4. 상태 변화: 재귀 함수는 상태를 변화시키는데, 이는 매개변수를 통해 이루어집니다. 각 재귀 호출은 다른 매개변수 값을 가질 수 있습니다.

---

재귀함수를 이용한 알고리즘 정리

1. 피보나치 수열

>> 첫 번째와 두 번째 항이 1이며, 세 번째 항부터는 바로 앞의 두 항을 더한 값으로 이루어집니다. 피보나치 수열은 다음과 같이 시작합니다. (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...)

>> 첫 번쨰와 두 번째 항이 모두 1이므로 n이 2보다 작거나 같을 때는 1을 반환하게 하고, 2보다 크면 fibonacci함수의 (n - 1)항과 (n - 2)항의 값을 더해서 계산한다.

>> 3번째 항은 fibonacci(2) + fibonacci(1)인데 둘다 2보다 작거나 같아서 1이 되기 때문에 fibonacci(3)은 2가 된다.

>> 4번째 항은 fibonacci(3) + fibonacci(2)인데 fibonacci(2)는 1이고, fibonacci(3)은 위의 과정을 거쳐 2가 되서 fibonacci(4)는 3이 된다. 이런식으로 반복된다.

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10;
        System.out.print("피보나치 수열: ");
        for (int i = 1; i <= n ; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    public static int fibonacci(int n) {
        if(n <= 2) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

---

2. 유클리드 호제법 알고리즘(최대공약수)

>> 두 개의 양의 정수에 대한 최대공약수(Greatest Common Divisor, GCD)를 찾는 알고리즘입니다. 두 정수 a와 b의 최대공약수를 GCD(a, b)로 표현하며, 유클리드 호제법은 이를 효과적으로 계산하는 방법을 제공합니다.

>> b가 0이면 a를 그대로 반환하고, 그게 아니면 a위치에 b를 넣고 b에 위치에 a를 b로 나눈 나머지를 넣어 계산한다.

>> gcd(12, 8)이 들어가면 b가 0이 아니기 때문에 gcd(8, 12 %8 = 4)가 되고 b가 0이 아니기 때문에 gcd(4, 8%4 = 0)이 된다. b가 0이 되었기 때문에 gcd의 값은 4가 된다.

public class GCD {
    public static void main(String[] args) {
        int a = 12;
        int b = 8;
        int gcd = gcd(a, b);
        System.out.println("최대공약수(GCD) : " + gcd);
    }
    public static int gcd(int a, int b) {
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

---

3. 이진 탐색 알고리즘

>> 정렬된 배열에서 특정 원소를 찾는 효율적인 방법을 제공하는 알고리즘입니다. 이진 탐색은 배열을 반으로 나누어 탐색 범위를 좁혀가며 원하는 원소를 찾아냅니다.

>> 이진 탐색의 기본 알고리즘

• 주어진 배열은 정렬되어 있다고 가정합니다.
• 배열의 중간 원소를 선택하고, 이 중간 원소와 찾으려는 원소를 비교합니다.
• 중간 원소와 찾으려는 원소가 동일하면 원하는 원소를 찾은 것이므로 알고리즘을 종료합니다.
• 중간 원소와 찾으려는 원소를 비교하여 중간 원소가 더 작으면, 배열의 왼쪽 반만을 다시 탐색 대상으로 삼습니다.
• 중간 원소가 더 크다면, 배열의 오른쪽 반만을 다시 탐색 대상으로 삼습니다.
• 위의 과정을 반복하여 원하는 원소를 찾을 때까지 계속합니다.

>> 원소를 찾지 못한 경우 -1를 리턴하게한다.

>> 중간값을 구하고, 타겟과 중간값을 비교해서 같으면 그 값을 리턴하고, 타겟이 크거나 작으면 재귀함수를 호출해서 반복작업해서 타겟을 찾는다.

>> 아래 과정을 살펴보면, 중간값은 0 + (7 - 0) / 2 = 3이 나온다. arr 배열의 3번째 인덱스의 값은 7이고, 7과 target 값 11을 비교한다.

>> target값이 더 크므로 중간값 3에 1을 더해서 왼쪽값에 넣는다. 이 떄 중간값은 4 + (7 - 4) / 2 = 5가 된다.

>> arr[5]는 11이고, target 값과 같으므로 11을 리턴한다.

public class BinarySearch {
    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 11;
        int result = binarySearch(sortedArray, target, 0, sortedArray.length - 1);
        if (result != -1) {
            System.out.println("원소 " + target + "을(를) 찾았습니다. 인덱스: " + result);
        } else {
            System.out.println("원소 " + target + "을(를) 찾지 못했습니다.");
        }
    }

    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 원하는 원소를 찾지 못한 경우
        }

        int mid = left + (right - left) / 2; // 중간값

        if (arr[mid] == target) {
            return mid; // 원하는 원소를 찾은 경우
        } else if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right); // 오른쪽 반 탐색
        } else {
            return binarySearch(arr, target, left, mid - 1); // 왼쪽 반 탐색
        }
    }
}

---

4. 이항계수 알고리즘

>> 조합론에 사용되며, 주어진 집합에서 원하는 수의 원소를 선택하는 방법의 수를 나타낸다.

>> 이항계수의 정의 nCk = n! / (k! * (n - k)!)

>> 여기서 nCk는 n개의 원소에서 k개의 원소를 선택하는 경우의 수를 나타내며, n!는 n 팩토리얼을 나타낸다.

>> 이항계수는 동적 계획법 또는 파스칼의 삼각형을 사용하여 효율적으로 계산할 수 있다.

>> 아래 예제는 파스칼의 삼각형 예제이다.

>> 파스칼의 삼각형에서 n은 세로 행을 의미한다.(0부터 시작)

>> 파스칼의 삼각형에서 k는 가로 행을 의미한다.(0부터 시작)

>> k가 0 또는 k와 n의 값이 같다면 외곽의 1을 의미하는 것이므로 1을 리턴한다.

>> 다음 행부터는 이전의 binomialCoefficient(n-1, k-1) 왼쪽부분과

binomialCoefficient(n-1, k) 오른쪽 부분을 더한 값으로 계산한다.

public class BinomialCoefficient {
    public static int binomialCoefficient(int n, int k) {
        if (k == 0 || k == n) {
            return 1;
        }
        return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
    }

    public static void main(String[] args) {
        int n = 5;
        int k = 2;
        int result = binomialCoefficient(n, k);
        System.out.println("이항 계수 " + n + "C" + k + "는 " + result + "입니다.");
    }
}