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

이번 포스트에서는 미래의 내가 풀어주는 재귀의 마법 같은 힘에 대해 알아보겠습니다.

---

1. 재귀의 카테고리

재귀에 관련된 문제를 풀이하다보면 해당 문제들이 비슷한 패턴을 띄고 있는 것을 발견할 수 있습니다.

그 패턴에 대해 알아보며 비슷한 문제를 발견 했을때 해결할 수 있는 힘을 길러 보겠습니다.

 

(1) 패턴 1 - 반복 실행

 반복적으로 하나의 작업을 실행하는 카테고리 입니다.

기저 조건을 가지고 단순히 하나의 작업을 기저 조건을 만족 할 때까지 반복 합니다.

이전 포스트에서 다뤘던 CountDown 함수가 그러 합니다.

function countdown(number) {
    if (number < 0) return;
    console.log(number);
    countdown(number - 1);
}

 만일 배열과 같은 현재 실행 정보를 담지 않은 데이터를 가지고 재귀 호출을 하려면 어떻게 해야 할까요? 

호출 함수의 인자에 현재 실행 정보를 담는 인자를 추가로 정의해 줍니다.

function doubleArray(arr, n = 0) {
    if (arr.length === n) return;
    arr[n] *= 2
    doubleArray(arr, n + 1)
}

(2) 패턴 2 - 계산

재귀는 하위 문제에 기반해 계산을 수행하는 문제에서 매우 강력한 힘을 발휘합니다.

앞선 포스트에서 예를 들었던 Factorial 함수가 바로 그 예입니다.

function factorial(n) {
    if (n === 1) {
        return 1;
    }
    return n * factorial(n - 1)
}

위의 예에서는 하위 문제인 factorial(n-1) 를 기반으로 하여 함수를 구현해 내었습니다.

 

---

2. 하향식 사고 방식

 재귀는 하향식 풀이 방식을 구현하는데 매우 탁월합니다.

하향식 사고 방식은 문제를 해결하는 새로운 사고 전략 ( mental strategy )를 제공하기 때문입니다.

따라서 재귀적 하향 방식은 문제를 완전히 다른 방식으로 생각하게 해줍니다.

하향식으로 문제를 풀 때는 풀이를 뒤로 미룹니다.

이게 무슨 의미 일까요?

위의 factorial 예시에서 우리는 하위문제 factorial(n-1)이 어떻게 동작하는지 알지 못해도 함수를 작성해 낼 수 있습니다.

내가 함수 작성자이지만 "세부적인 내용은 하위 문제에서 다루게 두자"라는 생각으로 접근 할 수 있습니다.

하향식 문제 풀이 방식입니다.

1. 작성 중에 함수는 누군가가 이미 작성해 놓았다고 생각합니다.
2. 문제의 하위 문제를 찾습니다.
3. 하위 문제에서 함수를 호출하면 어떻게 될지 생각합니다.

위의 단계를 바탕으로 함수를 구현해 보겠습니다.

주어진 문자열 내에서 'x' 문자의 갯수를 구하는 함수를 구현합니다

function countX(str) {
    if (str.length === 0) return 0;
    if (str[0] === 'x') {
        return 1 + countX(str.slice(1, str.length))
    } else {
        return countX(str.slice(1, str.length))
    }
}

---

마치며

재귀는 다양한 문제를 해결할 수 있는 훌룡한 도구이지만 주의 깊게 사용하지 않으면 현저히 효율성이 떨어지게 되므로 사용할 때 항상 주의 하도록 합니다.

 

관련글

재귀 (1) : Call me

 

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