[알고리즘] 재귀 (Recursion)

[알고리즘] 재귀 (Recursion)

재귀(Recursion)는 알고리즘과 프로그래밍에서 많이 사용되는 중요한 개념 중 하나입니다.

재귀란 함수가 자기 자신을 호출하는 프로그래밍 기법을 말합니다.

이를 통해 복잡한 문제를 간결하고 우아하게 해결할 수 있습니다.

이번 블로그 포스트에서는 재귀의 기본 개념과 함께, 재귀를 사용하여 문제를 해결하는 방법을 설명하겠습니다.

 

 

 

개념

재귀 함수는 자기 자신을 호출하는 함수입니다.

재귀를 효과적으로 사용하기 위해서는 두 가지 중요한 요소가 필요합니다

 

기저 조건(Base Case)

재귀 호출을 멈추기 위한 조건입니다.

기저 조건이 없으면 함수는 무한히 자신을 호출하게 되어 프로그램이 종료되지 않습니다.

 

재귀 단계(Recursive Step)

문제를 더 작은 하위 문제로 분해하고, 이 하위 문제를 해결하기 위해 자기 자신을 호출하는 단계입니다.

 

 

 

 

예시

숫자를 받아 해당 숫자의 계승(팩토리얼)을 반환하는 팩토리얼 함수를 작성하시오.
팩토리얼은 정수와 그 아래의 모든 정수의 곱입니다.
예를 들어, 4 팩토리얼 (4!)은 4 * 3 * 2 * 1 = 2입니다.
팩토리얼 0(0!)은 항상 1입니다.

function factorial(n) {
    // 기저 조건: n이 0이면 1을 반환
    if (n <= 1) return 1;
    
    // 재귀 단계: n * (n-1)의 팩토리얼
    return n * factorial(n - 1);
}

// 예제 사용
console.log(factorial(5)); // 출력: 120

 

 

 

숫자를 받아 피보나치 수열의 n번째 숫자를 반환하는 fib라는 재귀 함수를 작성하시오.

피보나치 수열은 1, 1로 시작하는 1, 1, 2, 3, 5, 8, ...의 정수의 수열이며, 모든 수는 이전 두 수의 합과 같다는 것을 명심하세요.

function fib(n){
    // base case (기저 조건)
    if (n <= 2) return 1;
    
    // recursion step (재귀 단계)
    return fib(n-1) + fib(n-2);
}


// fib(4) // 3
// fib(10) // 55
// fib(28) // 317811
// fib(35) // 9227465

 

 

 

 

장점

코드의 간결성

재귀를 사용하면 코드가 더 간결하고 직관적으로 보일 수 있습니다. 특히, 문제를 작은 하위 문제로 분할하는 자연스러운 방식입니다.

 

 

문제 해결의 직관성

재귀는 수학적 정의나 문제 해결 전략을 코드로 쉽게 변환할 수 있게 도와줍니다. 예를 들어, 트리 탐색, 그래프 탐색, 분할 정복 알고리즘 등이 있습니다.

 

 

 

 

단점

성능 문제

재귀 호출은 함수 호출마다 스택 메모리를 사용하므로, 재귀 깊이가 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.

 

 

오버헤드

반복적인 함수 호출은 성능 오버헤드를 발생시킬 수 있습니다.

이 경우, 반복(iteration)으로 대체하는 것이 더 효율적일 수 있습니다.

 

 

 

 

결론

재귀는 복잡한 문제를 간결하고 직관적으로 해결할 수 있는 강력한 기법입니다.

기저 조건과 재귀 단계를 적절히 설정하면 다양한 문제를 효과적으로 해결할 수 있습니다.

그러나 성능 문제와 스택 오버플로우를 주의해야 합니다.

재귀의 장점과 단점을 잘 이해하고 적절히 활용하는 것이 중요합니다.