[알고리즘] 재귀

재귀란?

재귀란 메서드 호출을 이용한 방법으로 하나의 메서드 내에서 자기 자신을 호출하도록 하여 반복적인 개념을 구현하는 것입니다.

 

재귀함수란?

배열 arr에서 2개의 원소를 조합해야 한다고 하면 아래와 같이 이중 반복문을 이용할 수 있습니다.

3개의 원소를 조합해야 한다면요?

4개, 5개의 원소를 조합한다고 하면요?

그래서 나온 것이 재귀함수, 즉 함수 내부에서 자기 자신을 호출하는 함수입니다.

 

재귀의 최대 범위와 한계점

재귀 호출이 중간에 종료되지 않고 너무 깊게 들어가 버리면 변수들이 메모리를 모두 할당해서 StackOverflowError 예외가 발생합니다. 이런 예외를 피하기 위해서는 재귀 호출의 깊이를 안전하게는 10,000 이하로, 아무리 많아도 20,000 이하로 유지시켜야 합니다.

 

재귀 정의하기

이 문제를 재귀로 접근해 봅시다.

상태 정의하기

재귀는 부분 문제를 해결해 나가는 풀이 방법입니다. 답을 내는 데 입력되는 변수들이 필요하고, 이렇게 답을 결정하는 변수들을 상태라고 합니다. 두 변수 x, y를 사용하여 정의되는 상태는 (x, y)로 표기합니다.

 

그럼 예시에서는 어떻게 정의할까요?

 

종료 조건

for문을 통해 무한 루프가 돌듯, 재귀함수도 종료 조건이 없으면 무한루프로 이어나갑니다. 답이 나오는 상태를 검사하여 답을 반환할 수 있도록 하는 것을 종료 조건이라고 하고, 종료 조건에 도달할 수 있도록 부분 문제로 상태가 변해 가는 것을 상태가 작아진다고 합니다.

이 조건들은 다음과 같이 표기합니다.

점화식

상태와 종료 조건을 정의한 후에는 가장 큰 상태가 어떤 과정을 거쳐 가장 작은 상태인 종료 조건에 도달하는지 정의해야 합니다. 이렇게 상태를 전이시키는 규칙을 점화식이라고 합니다.

 

다시 말씀드릴게요. 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식이 곧 점화식입니다.

예시 문제의 점화식은 위와 같습니다.

 

코드 작성하기

코드 변환하기

부분 문제 나타내기

종료 조건 작성하기

 

점화식 구현하기

점화식은 하나의 부분 문제를 더 작은 상태를 나타내는 부분 문제를 이용하여 푸는 규칙입니다.

재귀 함수를 활용한 예시

 

1. 팩토리얼 계산 방법

💡 팩토리얼 이란? - 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값을 의미합니다. 💡 해당 기능은 factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 결괏값을 반환해 주는 함수입니다. 💡 5라는 값을 파라미터로 넘겼을 때 아래와 같이 호출이 됩니다. factorial(5) = 5 * factorial(4) factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 * factorial(0) factorial(0) = 1 그러므로, factorial(5)는 5 * 4 * 3 * 2 * 1 * 1 = 120이 됩니다.

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5)); // 5! = 5 * 4 * 3 * 2 * 1 = 120
    }

    public static int factorial(int n) {
        if (n == 0) { // 기본 케이스
            return 1;
        } else { // 재귀 케이스
            return n * factorial(n - 1);
        }
    }
}

 

 

2. N 자연수의 합 계산 방법

💡 해당 기능은 sumNaturalNumber() 함수에 파라미터로 값을 넘길 경우 재귀함수를 반복하여 결괏값을 반환해 주는 함수입니다. 5라는 값을 파라미터로 넘겼을 때 아래와 같이 호출이 됩니다. 1+2+3+4+5의 결과값인 15를 반환합니다. 그러므로, sumNaturalNumber(5)는 1+2+3+4+5=15가 됩니다

public class Main {
    public static void main(String[] args) {
        System.out.println(sumNaturalNumber(5)); // 15
    }

    public static int sumNaturalNumber(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n + sumNaturalNumber(n - 1);
        }
    }
}

 

3. 거듭제곱(pow) 계산

💡 거듭제곱(pow)이란? - 하나의 숫자(밑)를 다른 숫자(지수)만큼 곱하는 것입니다. 💡 해당 코드는 파라미터로 base 밑과 exponent 지수를 인자로 받아서 거듭제곱을 수행하는 함수입니다. 파라미터로 밑의 값 2와 지수값 5를 넣었을 때 2 x 2 x 2 x 2 x 2 값이 되어서 32가 출력됩니다.

public class Main {
    public static void main(String[] args) {
        System.out.println(power(2, 5)); // 15
    }

    public static int power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        } else {
            return base * power(base, exponent - 1);
        }
    }
}

 

4. 문자열 뒤집기

💡  해당 예시에서는 reverseString() 함수를 통해 문자열의 값이 0이 되면 문자열을 반환하고 그렇지 않으면 첫 번째 문자를 마지막 문자와 바꾸고 나머지 문자열에 대해 reverseString() 함수를 재귀적으로 호출한 결과를 반환합니다.

public class Main {
    public static void main(String[] args) {
        System.out.println(reverseString("hello")); // "olleh"
    }

	public static String reverseString(String str) {
	    if (str.length() == 0) {
	        return str;
	    } else {
	        return reverseString(str.substring(1)) + str.charAt(0);
	    }
	}
}