재귀 (Recursion)

재귀 (Recursion) 설명:

재귀는 어떤 함수가 자신을 다시 호출하는 것을 의미합니다. 재귀는 문제를 더 작은 부분 문제로 나누어 해결하는 방식을 사용하며, 종종 반복문의 대안으로 사용됩니다. 재귀를 사용하면 코드가 더 간결하고 이해하기 쉬워질 수 있지만, 잘못 사용하면 메모리 사용량이 증가하거나 스택 오버플로우와 같은 문제가 발생할 수 있습니다.

재귀의 기본 원칙:
1. 기본 경우(Base Case): 재귀 호출을 중단할 조건. 이를 정의하지 않으면 함수가 무한히 호출되어 프로그램이 중지될 수 있습니다.
2. 재귀 경우(Recursive Case): 함수가 자기 자신을 다시 호출하는 부분. 이 때, 문제의 크기나 복잡성이 감소해야 합니다.

JavaScript에서의 재귀 예제:

1. 팩토리얼 계산:

function factorial(n) {
    if (n <= 1) return 1; // 기본 경우
    return n * factorial(n - 1); // 재귀 경우
}

console.log(factorial(5)); // 120

2. 피보나치 수열:

function fibonacci(n) {
    if (n <= 1) return n; // 기본 경우
    return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 경우
}

console.log(fibonacci(5)); // 5

재귀의 사용 사례:

1. 트리나 그래프의 탐색: 트리나 그래프의 모든 노드를 방문할 때, 재귀를 사용하여 깊이 우선 탐색(DFS)을 구현할 수 있습니다.
2. 분할 정복 알고리즘: 문제를 더 작은 부분 문제로 분할하여 해결하는 방식, 예를 들면 병합 정렬(merge sort)이 있습니다.
3. 하노이의 탑: 재귀적 방법을 사용하여 문제를 해결합니다.
4. 순열 및 조합: 재귀를 사용하여 모든 가능한 순열 또는 조합을 생성합니다.

장점:
1. 코드가 더 간결하고 깔끔해질 수 있습니다.
2. 복잡한 문제를 간단하게 나누어 해결할 수 있습니다.

단점:
1. 메모리 사용량이 증가할 수 있습니다. (스택 메모리가 누적되어 사용됨)
2. 최적화되지 않은 재귀는 성능 문제를 일으킬 수 있습니다. (예: 위의 피보나치 예제는 큰 n에 대해 매우 비효율적입니다.)
3. 스택 오버플로우: 너무 많은 재귀 호출로 인해 함수 호출 스택이 넘치는 문제가 발생할 수 있습니다.

재귀는 강력한 프로그래밍 기법이지만, 사용할 때는 주의가 필요합니다. 특히, 기본 경우를 명확하게 정의하고, 불필요한 반복 재귀 호출을 피하도록 최적화하는 것이 중요합니다.