[Java/알고리즘] 재귀 함수(Recursion Function) 이해하기

해당 글에서는 재귀함수에 대해 이해하며 다양한 예시와 재귀함수를 이용한 알고리즘을 기반으로 이해를 돕기 위해 작성한 글입니다.

1) 재귀함수(Recursion Function)

---

💡 재귀함수(Recursion Function)란?

- 함수 내부에서 ‘자기 자신을 호출’하는 함수를 의미합니다. 이를 통해서 함수가 자신을 반복적으로 호출하면서 원하는 결과를 도출할 수 있습니다.

- 단, 재귀함수를 사용하는 경우 함수 호출이 계속해서 쌓이기 때문에 호출 스택이 많아져서 성능이 저하될 수 있습니다. 따라서 재귀함수를 작성할 때는 무한루프에 빠지지 않도록 종료 조건을 명확하게 설정해주어야 합니다.

 
 

[ 더 알아보기 ]

💡 호출 스택(Call Stack)이란?

- 프로그램에서 함수나 메서드를 호출할 때 해당 함수나 메서드의 실행이 끝날 때까지 실행되는 다른 함수나 메서드의 호출 정보를 저장하는 자료구조입니다.
- 이 스택은 함수가 호출될 때마다 그 함수의 호출 정보를 저장하고 함수의 실행 결과가 반환되면 해당 함수의 호출 정보를 스택에서 제거합니다.
- 호출 스텍은 디버깅, 예외 처리 및 재귀 함수와 같은 다양한 프로그래밍 작업에 사용됩니다.


💡 재귀 함수와 재귀 알고리즘은 다른 것인가?

- 재귀 알고리즘은 문제를 해결하기 위해 재귀 함수를 사용하는 알고리즘을 의미합니다

 
 
 

2) 재귀 함수의 장단점

---

1. 장점

---

번호	장점
1	코드의 가독성이 높아집니다. 재귀적인 호출을 통해 코드를 간결하게 작성할 수 있습니다.
2	일부 알고리즘에서는 반복문을 사용하는 것보다 재귀 함수를 사용하는 것이 더 직관적입니다.

 

2. 단점

---

번호	단점
1	재귀 함수는 함수를 호출할 때마다 스택에 새로운 프레임을 생성합니다. 따라서, 스택이 너무 깊어질 경우에는 스택 오버플로우가 발생할 수 있습니다.
2	재귀 함수는 함수의 호출이 반복적으로 일어나기 때문에, 일반적으로 반복문을 사용하는 것보다 느립니다.

 
 

3) 재귀 함수의 활용한 예시

---

💡 재귀 함수를 이용하여 모듈을 구성하는 예시를 담고 있습니다.

 
 

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);
        }
    }
}

 

💡 [참고] Math.pow() 함수를 이용하여 동일한 기능을 처리합니다.
💡 이에 대해 궁금하시면 아래의 링크를 확인하시면 도움이 됩니다.

[Java] 숫자(Number) 조작 함수 이해하기 : Math, 진법 변환

 
 

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);
	    }
	}
}

 
 
 

4) 재귀함수를 이용한 알고리즘 : 피보나치 수열, 유클리드 호제법, 이진탐색, 이항 계수

---

 

1. 피보나치 수열 : 경우의 수 계산

---

💡 피보나치 수열이란?

- 이전 두 항의 합이 다음 항이 되는 수열을 의미합니다. 즉, 첫째 항과 둘째 항이 1이고 이후 모든 항은 모든 항은 바로 앞 두항의 합으로 이루어지는 수열을 의미합니다.

- 피보나치 수열의 예로는 [1, 1, 2, 3, 5, 8, 13, 21, 34,...]과 같은 형태로 구성이 됩니다.

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

 

💡 [참고] 피보나치 수열에 대해 관심이 있으시면 아래의 링크를 참고하시면 도움이 됩니다.

[Java/알고리즘] 피보나치의 수열(Fibonacci numbers) : 경우의 수

 
 

2. 유클리드 호제법 알고리즘: 최대공약수 계산

---

💡 유클리드 호제법/알고리즘(Euclidean Algorithm) 이란?

- 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘을 의미합니다.
- 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법을 의미합니다. 그때 작은 수가 최대공약수입니다.

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

 

[참고] 유클리드 호제법에 대해 관심이 있으시면 아래의 링크를 참고하시면 도움이 됩니다.

[Java/알고리즘] 유클리드 호제법(Euclidean Algorithm) : 최대공약수, 최소공배수

 
 
 

3. 이진 탐색(Binary Search) 알고리즘

---

💡 이진 탐색(Binary Search) 알고리즘이란?

- 정렬된 배열에서 원하는 데이터를 빠르게 찾기 위한 알고리즘입니다.

- 이진탐색은 배열의 중간값을 선택한 후, 찾고자 하는 데이터와 중간값을 비교합니다. 만약 중간값이 찾고자 하는 데이터보다 크다면, 중간값의 왼쪽 부분 배열에서 다시 중간값을 선택하여 비교합니다. 반대로 중간값이 찾고자 하는 데이터보다 작다면, 중간값의 오른쪽 부분 배열에서 다시 중간값을 선택하여 비교합니다. 이 과정을 반복하여 원하는 데이터를 찾습니다.
- 이진탐색은 데이터의 개수가 많을 때도 빠르게 데이터를 찾을 수 있기 때문에 많이 사용되는 알고리즘 중 하나입니다.

 
 

💡  높은 인덱스가 낮은 인덱스보다 크거나 같은지 확인합니다.

1. 중간 값을 구합니다.

2. 배열의 요소 값이 찾는 값과 동일하면 중간 값을 반환합니다.

3. 중간 값이 키보다 큰 경우 : 낮은 인덱스와 중간 인덱스에서 1을 뺀 값을 가지고 함수를 재귀적으로 호출합니다.

4. 중간 값이 키보다 작은 경우 : 중간 인덱스에 1을 더하고 높은 인덱스와 함께 함수를 재귀적으로 호출합니다

/**
 * 재귀를 사용하여 이진 알고리즘을 구현합니다.
 * @param arr 배열
 * @param low 낮은 인덱스
 * @param high 높은 인덱스
 * @param key 검색할 값
 * @return
 */
public static int binarySearch(int[] arr, int low, int high, int key) {
    // 1. 높은 인덱스가 낮은 인덱스보다 크거나 같은지 확인합니다.
    if (high >= low) {

        // 2. 중간 값을 구합니다.
        int mid = low + (high - low) / 2;

        // 3. 배열의 요소 값이 찾는 값과 동일하면 중간 값을 반환합니다.
        if (arr[mid] == key) {
            return mid;
        }
        // 4. 중간 값이 키보다 큰 경우 : 낮은 인덱스와 중간 인덱스에서 1을 뺀 값을 가지고 함수를 재귀적으로 호출합니다.
        else if (arr[mid] > key) {
            return binarySearch(arr, low, mid - 1, key);
        }
        // 5. 중간 값이 키보다 작은 경우 : 중간 인덱스에 1을 더하고 높은 인덱스와 함께 함수를 재귀적으로 호출합니다
        else {
            return binarySearch(arr, mid + 1, high, key);
        }
    }

    // 6. 높은 인덱스가 낮은 인덱스보다 작으면 배열에서 키를 찾지 못했음을 나타내기 위해 -1을 반환합니다.
    return -1;
}

 
 
 

💡 [참고] 이진 탐색에 대해 관심이 있으시면 아래의 링크를 참고하시면 도움이 됩니다.

[Java/알고리즘] 이진/이분탐색(Binary Search) 이해하기

 
 
 

4. 이항계수(binomial theorem) 알고리즘

---

💡 이항계수(binomial theorem) 알고리즘이란?

- 조합론에서 사용되며, n개의 서로 다른 원소에서 r개의 원소를 선택하는 경우의 수를 의미합니다.

 
 
 

💡 해당 알고리즘은 원소 n개 중에서 r개를 선택하는 경우의 수를 계산하는 함수입니다.

1. r이 0이거나 n과 같으면 함수는 1을 반환합니다.

2. 그렇지 않으면 k-1과 n-1인자로하여 자기 자신을 두 번 호출하고 두 결과의 합을 반환합니다.

3. 이 과정은 k가 0이나 n과 같아질 때까지 반복됩니다.

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