재귀

요약

재귀

base case & recursive case

• base case(기저 조건, stopping condition) : 재귀적 호출에서 빠져나오는 경우(탈출 조건)를 의미합니다.

• recursive case(재귀 호출) : 자기 자신을 호출하여 하위 작업을 수행하는 경우를 의미합니다.

재귀 함수의 특징

• 스택처럼 호출한 함수를 쌓았다가 종료조건을 만나면 위에서부터 하나씩 꺼내 처리하는 방식입니다.

• 절차지향 사고를 탈피하여 귀납적으로 사고하는 방식이 필요합니다.

• 함수의 인자로 어떤 것을 받고, 어디까지 계산 후 넘겨줄지 명확하게 정해야 합니다.

• 모든 재귀함수는 반복문으로 동일한 동작을 할 수 있습니다.

• 종료조건을 꼭 포함해야 한다. 그렇지 않으면 재귀함수는 무한루프에 빠질 수 있습니다.

재귀 함수의 장점

• 큰 문제를 작은 문제로 분할하여 쉽게 풀 수 있는 재귀 관계를 파악했을 경우, 이를 쉽게 코드로 옮길 수 있다.

• 코드가 짧아지고 코드가 직관적이여서 가독성이 높아진다.

• 반복문을 사용하지 않아 코드가 간결해진다.

재귀 함수의 단점

• 재귀호출과 반복문 구현 비교 시, 실제 Call Stack 과정에서 재귀호출이 속도가 느리고, 메모리도 더 많이 사용한다.

• 약 1000번 정도까지만 재귀호출이 가능하기 때문에 많은 호출이 필요할 때는 사용이 불가능합니다.

• 무한루프에 빠질 경우 메모리 용량을 초과해서 스택 오버플로우를 발생시킬 수 있다.

재귀 사용 예

• 피보나치 수열, 팩토리얼 구하기

• 병합 정렬, 퀵 정렬

• 이진 검색

• 트리 탐색, 중위, 전위, 후위 등 여러 트리 문제들

• 그래프 탐색, 깊이 우선 탐색과 너비 우선 탐색

• 동적 계획법의 예

• 분할 정복 알고리즘

• 하노이의 탑

• 백트래킹 알고리즘

꼬리 재귀

• 함수 호출 스택에 쌓이지 않고, 컴파일러나 인터프리터에 의해 최적화될 수 있습니다. 따라서 스택 오버플로우의 위험이 줄어듭니다.

• 재귀 호출 이후에 추가적인 연산이 없으므로, 재귀 호출 이후의 계산 없이 함수가 바로 종료됩니다 (일반 재귀보다 실행 속도가 더 빠릅니다)

• 누적값(accumulator)을 활용하여 중간 결과를 계속 업데이트하면서 최종 결과를 얻습니다.

// 일반 재귀
function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n-1);
}

// 꼬리 재귀
function factorial(n, acc = 1){
    if(n === 1){
        return acc;
    }
    return factorial(n - 1, n * acc);
}

참고 사이트