알고리즘 - 재귀

재귀 함수 정의

• 재귀 함수는 실행 과정에서 자기 자신을 호출하는 함수

재귀 함수의 효과적인 활용

• 문제 분할
  • 복잡한 문제를 더 작고 관리하기 쉬운 부분으로 나눌 수 있다.
• 코드 간소화
  • 중첩된 반복문이 복잡하거나 그 중첩 횟수를 예측하기 어려울 때, 재귀를 사용하면 코드의 가독성을 향상시키고 로직을 단순화할 수 있다.
  • 특히 트리나 그래프와 같은 데이터 구조를 순회할 때 유리

case1. 반복문 사용

public class Staircase {

    public static int countWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = b;
            b += a;
            a = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        int stairs = 5;
        System.out.println("Number of ways = " + countWays(stairs));
    }
}

case2. 재귀함수 사용

public class Staircase {

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

    public static void main(String[] args) {
        int stairs = 5;
        System.out.println("Number of ways = " + countWays(stairs));
    }
}

사용시 주의할 점

• 함수 호출과 메모리 관리
  • 재귀 함수를 사용할 때, 함수 내에서 다른 함수를 호출하면 현재 작업이 일시 중지되며, 이 과정은 호출 스택을 통해 관리된다.
• 종료 조건
  • 무한 루프를 방지하기 위해 재귀 함수는 반드시 종료 조건을 포함해야 한다.
• 메모리 사용과 성능
  • 재귀 호출의 깊이가 깊어질수록 많은 메모리를 소모하고, 이는 스택 오버플로우를 일으킬 수 있다.
  • 재귀는 반복문에 비해 더 많은 메모리 사용과 수행 시간을 필요로 할 수 있다.
• 효율성 고려
  • 모든 재귀 함수는 반복문으로도 동일한 기능을 구현할 수 있으므로, 함수의 깊이와 성능을 고려하여 더 효율적인 방법을 선택해야 한다.

재귀 함수 예시

int factorial(int n)
{
	if (n == 0)
    	return 1;
    return n * factorial(n-1);
}

factorial(3)을 실행한 경우 Stack Memory

이미지 출처

재귀 함수가 사용되는 주요 알고리즘

• 분할 정복 (병합정렬, 퀵정렬)
• 트리 (이진 탐색)
• 그래프 탐색 (DFS)
• 다이나믹 프로그래밍
• 백트래킹 (조합, 순열, N-Queen)

---

ref.
https://velog.io/@kai6666/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%AC%EA%B7%80-%ED%95%A8%EC%88%98-Recursion
https://gomguard.tistory.com/111