JavaScript Data Structure And Algorithm | 재귀

재귀 소개

수학과 언어학, 예술에서 재귀는 자신에 대해 정의한 것이 발생하는 것을 나타낸다.

컴퓨터 과학 분야에서는 재귀함수는 자기 자신을 호출하는 함수이다.

 

재귀 함수는 '분할 정복' 방식을 통해 복잡한 문제를 해결한다. 

 

재귀의 규칙

재귀함수를 잘못 작성하는 경우 심각한 문제를 일으킨다. 프로그램이 어느 한곳에 빠져서 종료되지 않기 때문이다. 무한 재귀 호출은 스택 오버플로(stack overflow)를 초래한다. 스택 오버플로는 프로그램의 콜 스택 개수가 제한된 양의 주소 공간(메모리)을 초과할 때를 나타낸다. 

 

재귀 함수를 올바르게 구현하기 위해서는 스택 오버플로를 피하기 위한 특정 규칙을 따라야 한다. 

 

기저 조건

재귀에는 기저 조건(종료 조건)이 존재한다. 재귀 메소드는 자기 자신을 호출하기 때문에 기저조건에 도달하지 않으면 중단하지 않고 계속 자기 자신을 호출한다.

 

기저 조건에서는 더 이상 재귀함수 호출을 하지 않는다. 

 

n 부터 0까지 세면서 숫자를 출력하는 다음 함수를 살펴보자.

 

function countDownToZero(n) {
	// 기저 조건, 0에서 중단한다.
    if (n < 0) {
    	return
    } else {
    	console.log(n)
        countDownToZero(n - 1)
    }
}

countDownToZero(12)

 

기저 조건 외에도 재귀함수는 분할 정복 방식을 활용한다.

 

분할 정복 방식

컴퓨터 과학에서 분할 정복 방식은 어떤 문제를 작은 단위로 나눠서 해당 작은 단위의 문제들을 모두 해결함으로써 문제를 해결하는 것을 말한다. 위의 숫자 세기 예에서 2가 입력일 때 숫자를 세는 문제는 2를 출력한 다음 1이 입력일 때 숫자를 세는 문제를 호출한다. 여기서 1이 입력일 때 숫자를 세는 문제는 2가 입력일 때 숫자를 세는 문제의 부분 문제이다.

 

이런 식으로 문제는 '분할 정복'에 의해 점점 작아지면서 기저 경우에 도달해야 한다. 그렇지 않으면 재귀 호출에 기저 사례에 수렴하지 못해 스택 오버플로가 발생한다.

 

피보나치 수열

피보나치 수열은 무한한 숫자들의 목록이다. 이때 각 수는 이전 두 수의 합이다. 이를 재귀적으로 프로그래밍하면 다음과 같다.

 

function getNthFibo(n) {
    if (n <= 1) {
        return n
    } else {
    	return getNthFibo(n - 1) + getNthFibo(n - 2)
    }
}

 

기저 경우: 피보나치 수열의 기저 경우는 첫 번째 항목이 1일 때이다.

분할 정복: 피보나치 수열의 정의의 정의에 따르면 N 번째 피보나치 수는 (n - 1)번째 피보나치 수와 (n - 2) 피보나치 수의 합이다. 하지만 이러한 구현의 시간 복잡도는 O(2^n)이다. 꼬리 재귀를 사용해서 피보나치 수열을 개선해보자.

 

피보나치 수열: 꼬리 재귀

꼬리 재귀(tail recursion)은 함수의 재귀 호출이 함수에서 가장 마지막에 실행되는 방식의 재귀 함수다.

 

function getNthFiboBetter(n, lastlast, last) {
    if (n == 0) {
        return lastlast
    }
    if (n == 1) {
    	return last
    }
    return getNthFiboBetter(n - 1, last, lastlast + last)
}

 

시간 복잡도: O(n)

함수는 n 번 실행된다. 재귀 호출이 일어날 때마다 n - 1 씩 감소하기 때문이다.

 

공간 복잡도: O(n)

위의 함수에 사용된 스택 콜 때문에 공간 복잡도 역시 O(n)이다. 

 

파스칼의 삼각형

 

기저 경우: 파스칼의 삼각형의 기저 경우는 최상위 항목(행 = 1, 열 = 1)인 1이다. 나머지 모든 수는 해당 항목으로부터 파생된 것이다. 따라서 열이 1이면 1을 반환하고 행이 0이면 0을 반환한다.

 

분할 정복: 파스칼 삼각형의 수학적 정의에 따르면 파스칼 삼각형의 수는 해당 수의 위쪽수들의 합이다.

 

function pascalTriangle(row, col) {
    if (col === 0) {
        return 1
    } else if (row === 0) {
    	return 0
    } else {
    	return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1)
    }
}

pascalTriangle(5, 2)

 

재귀의 빅오 분석

재귀 알고리즘에 대한 빅오 분석을 수행하기 위해서는 알고리즘의 어떤 식으로 반복되는지 점화식(recurrrence relations)을 분석해야한다.

 

점화식

반복 루프를 사용해 구현된 알고리즘의 경우 빅오 분석이 훨씬 간단하다. 루프가 언제 중단돼야 할지 그리고 각 반복 루프마다 얼마나 증가시켜야 할지를 명확하게 정의하기 때문이다. 재귀 알고리즘을 분석하는 경우 점화식을 사용한다. 점화식은 기저 경우에 대한 빅오와 재귀에 대한 빅오 두 부분에 대한 분석으로 구성된다. 

 

피보나치 수열의 기저 경우의 시간 복잡도는 O(1)이다. 재귀의 경우 자기 자신을 두 번 호출한다. 이를 T(n) = T(n - 1) + T(n - 2) + O(1) 이라고 표현하자. 이는 함수르 ㄹ호출할 때마다 각 함수에 대해 두개의 함수 호출이 일어남을 확인할 수 있다. 즉 이 함수의 시간 복잡도는 O(2^n)이다. 

 

빅오를 계산하는 것은 어렵고 실수하기 쉽다. 다행히도 이를 계산하는데 도움이 되는 마스터 정리(master theorem)라는 개념이 있다.

마스터 정리

마스터 정리는 다음과 같이 기술한다.

a >= 1 이고 b >= 1인 T(n) = aT(n / b) + O(n^c)의 형태를 지닌 점화식이 있을 때 세가지 경우가 존재한다.

 

a는 재귀 호출에 곱해지는 계수다. b는 "로그"항이다. b는 재귀 호출시에 n을 나누는 항이다. 마지막으로 c는 등식의 비재귀 구성요소에 대한 다항식의 항이다.

 

요약

재귀는 복잡한 알고리즘을 구현하기 위한 강력한 도구이다. 모든 재귀 함수는 두 가지 부분으로 구성됨을 기억하자. 바로 기저 경우와 분할 정복 방식(하위 문제 해결하기)이다.