재귀 (3) : 효율적인 재귀 사용

지난 포스트에서는 재귀 호출의 구현에 대해 알아보았습니다.
재귀 호출의 마법 같은 힘은 정말 대단하지만 주의해서 사용하지 않으면 아주 큰 비용을 치러야 할 수 있습니다.
오늘은 재귀 호출의 비용 이야기와 함께 재귀 호출의 효율성을 증대시킬 수 있는 방법에 대해 알아보고자 합니다.

---

1. 불필요한 재귀호출

여기 배열의 최댓값을 찾는 재귀 함수가 있습니다

 

function max(array) {
    if (array.length === 1) return array[0];

    if (array[0] > max(array.slice(1))) {
        return array[0];
    } else {
        return max(array.slice(1))
    }
}

 

각 배열을 하위 함수로 전달하며 반환 값을 배열의 첫번째 원소와 비교하고 있습니다.
지금 이 함수에는 매우 위험한 부분이 존재합니다.

 

 if (array[0] > max(array.slice(1))) {

 

이 부분입니다. 

왜 위험한 걸까요?

재귀 함수를 조건절에서 한 번 호출하고 이 조건을 충족하는지 여부와 관계없이 반환하면서 재귀 함수를 한번 더 호출합니다.
$ max([1,2,3,4]) $를 비교한다고 했을 때 재귀 함수의 호출은 무려 15번이나 일어나게 됩니다.

그렇다면 이 함수를 어떻게 개선할 수 있을까요?

 

function max(array) {
    if (array.length === 1) return array[0];
    const prevMaxValue = max(array.slice(1));
    if (array[0] > prevMaxValue) {
        return array[0];
    } else {
        return prevMaxValue;
    }
}

 

코드에서 하위 함수 계산 이 후 해당 값을 변수로 저장합니다.
이렇게 함으로써 $ max([1,2,3,4]) $ 함수가 재귀 함수 호출이 단 4번으로 줄어들게 됩니다.
이처럼 중복되는 재귀 함수 호출이 보일 시에는 중복 호출을 줄이는 것이 바람직합니다.

 

---

 

2. 하위 문제 중첩

피보나치수열은 다음과 같이 무한히 이어지는 수열입니다.

 

$ 0,1,1,2,3,5,8,13,21,34,55 .... $

 

이어지는 수는 앞의 두 수의 합과 같습니다.

재귀 함수로로 구현해 볼까요?

 

function fib(n) {
    if(n === 0 || n === 1) return n;
    return fib(n - 1) + fib(n - 2)
}

 

점화식으로 자기 자신에 대한 호출이 두 번 보입니다. 

이는 매우 큰 $ 2^n $ 의 시간 복잡도를 가지게 됩니다.

앞서 본 방법으로 개선해보고자 했지만 위의 max 문제와 달리 하나의 결과 값이 아닌 여러 개의 결과 값이 사용되고 있기에 쉽지 않습니다.

위와 같은 경우를 하위 문제의 중첩 (Overlapping Subproblem)이라 부릅니다.

하위 문제가 중첩되는 이유는 fib(n-2)와 fib(n-1)이 결과적으로 같은 함수를 여러 차례 중복해서 호출하기 때문입니다.
그렇다면 해결할 방법이 없는걸까요?

---

 

3. 메모이제이션을 통한 동적프로그래밍

바로 동적 프로그래밍(Dynamic programming, DP)이라는 방법을 통해 해결할 수 있습니다.
동적 프로그래밍을 통한 알고리즘 최적화에는 일반적으로 두 가지 방법이 쓰입니다.
첫 번째 기법은 메모이제이션(memoization)입니다.
메모이제이션은 먼저 계산한 함수 결과를 기억하는 방법으로 중복 재귀 호출을 제거합니다.
매번 재귀 함수 호출 시 함수 호출 결과 값을 해시테이블에 기록합니다.

예를 들어 만약 fib(3)을 호출하고 난 후라면 비어있던 해시테이블은 아래와 같은 상태가 됩니다.

{ 3 : 2 }

 

후에 재귀 호출 중 fib(3)을 호출하게 될 상황이 생기면 해시테이블의 해당 값으로 대신합니다.

 기록된 해시테이블 사용을 위해서 함수 내에서 재귀 함수  항상 해시테이블에 호출하고자 하는 함수 인자의 값이 존재하는지 확인하고 재귀 호출 여부를 결정하도록 합니다.

 

function fib(n, memo = {}) {
    if (n === 0 || n === 1) return n

    if (!memo[n]) {
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    }
    return memo[n]
}

 

위 함수의 시간 복잡도는 $ O(2N - 1) = O(N) $  으로 위 함수와 비교하였을 때 훨씬 더 효율적인 함수가 되었습니다.

---

4. 상향식 동적프로그래밍

상향식은 반복을 통해 함숫값을 아래부터 도출해 나갑니다.

function fib(n) {
    if (n === 0) return 0;
    let a = 0
    let b = 1
    for (let i = 1; i < n; i++) {
        let temp = a
        a = b
        b = temp + a
    }
    return b
}

---

 

5. 메모이제이션 VS 상향식

보통 문제의 형태 그리고 왜 재귀를 사용하는지에 따라 사용처가 나뉘게 됩니다.
재귀가 주어진 문제에 대한 직관적인 해법이면 메모이제이션을, 반복적 방식이 직관적이면 반복을 사용하면 됩니다
하지만 메모이제이션 사용이 반복에 비해 더 비용이 든다는 것을 잊지 말아야 합니다. ( 호출 메모리 + 메모이제이션 테이블 )
때문에 재귀가 매우 직관적이지 않은 이상 상향식을 선택하는 것이 나은 선택입니다.

 

---

 

6. Dynamic Programming 문제 해결 조건

 

실제 알고리즘 문제 풀이 시 해당 문제가 DP로 풀이가능한 문제인지 어떻게 판별해야 할까요?

아래와 같은 조건을 만족한다면 DP로 풀이 가능한 문제입니다.

 

1. Overlapping Subproblem

겹치는 문제란 어떠한 문제가 여러 부분문제로 쪼개질 수 있을 때 사용하는 용어입니다.

부분문제란 항상 새로운 문제가 아닌 같은 문제가 여러 번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가리킵니다.
겹치는 부분문제가 있다면, 큰 문제는 작은 문제들을 통해 정답을 구할 수 있습니다.

 

2. Optimal Subsctrucure

최적 부분구조는 어떤 문제의 최적의 해결책이 그 부분문제의 최적의 해결책으로부터 설계될 수 있는 경우를 말합니다.

 

 

---

 

7. Dynamic Programming 풀이의 순서

1. 먼저, 문제에서 구하려고 하는 답을 문장으로 나타냅니다.
   • (예: 피보나치 수를 구하는 문제 -> N번째 피보나치 수)
2. 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 캐시 배열을 만듭니다.
3. Top-down인 경우에는 재귀 호출의 인자의 개수가 됩니다.
4. 이제 문제를 작은 문제로 나누고, 수식(점화식)을 이용해서 문제를 표현 합니다.

 

마치며

오늘은 재귀의 효율성에 대해서 알아보았습니다.
앞서 말씀드렸듯이 재귀는 어떻게 사용하느냐에 따라 의도치 않게 막대한 비용을 치르는 함수가 만들어질 수 있습니다.
때문에 항상 재귀 사용 시 올바른 사용처인가 중복 호출이 일어나지는 않는가에 대한 많은 고민이 필요합니다.

 

 

관련글

 

재귀 (1) : Call me

 

재귀 (2) : 미래의 나야, 부탁해~