10장 재귀를 사용한 재귀적 반복

재귀는 이후 나올 보다 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다.

10.1 루프 대신 재귀

카운트 다운 함수를 구현한다고 하자.

function countdown(number) {
  for (let i = number; i >= 0; i--) {
    console.log(i);
  }
}

반복문을 사용할 수도 있지만, 재귀를 사용할 수도 있다.

function countdown(number) {
  console.log(number);
  countdown(number - 1);
}

countdown(10)을 호출한다고 가정하면,
10을 출력하고, countdown(10) 함수가 끝나기 전에 countdown(9) 함수를 호출한다.
countdown(9)는 9를 출력하고, countdown(9) 함수가 끝나기 전에 countdown(8) 함수를 호출한다.
countdown(8)은 8을 출력하고 ...

반복문 없이 단순히 countdown() 함수 호출만으로 10부터 카운트다운해서 각 숫자를 콘솔에 출력하고 있다.

반복문을 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.
쓸 수 있으므로 무조건 재귀를 써야하는 것은 아니다.

10.2 기저 조건

10.1 의 countdown() 함수를 계속 살펴본다.
countdown(0)을 호출하면, 0이 출력되고 countdown(-1)을 호출한다. 즉, 무한대로 음수를 출력한다.
이 함수가 완벽해지려면 카운트다운을 0에서 끝내고 재귀가 영원히 지속되는 것을 막을 방법이 있어야 한다.

number가 0이면 더 이상 countdown()을 호출하지 않는 조건문을 추가하면 된다.

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

재귀에 쓰이는 용어로, 함수가 반복되지 않는 이러한 경우를 기저 조건이라고 한다.
위의 countdown()함수에서는 0이 기저 조건이다.
모든 재귀 함수에는 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다.

10.3 재귀 코드 읽기

팩토리얼을 계산하는 예제를 살펴보자.
3 팩토리얼은 3 * 2* 1 = 6이고, 5 팩토리얼은 5 * 4 * 3 * 2 * 1 = 120이다.

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

재귀 코드가 어떻게 동작하는지 살피는 순서는 다음과 같다.

1. 기저 조건을 찾는다.
2. 기저 조건에서 함수가 어떻게 동작하는지 살핀다.
3. "끝에서 두 번째" 조건, 즉 기저 조건 바로 전 조건을 찾는다.
4. "끝에서 두 번째" 조건에서 함수가 어떻게 동작하는지 살핀다.
5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고, 그 때마다 함수가 어떻게 동작하는지 살핀다.

함수가 자기 자신을 호출하지 않는 부분은 if(number ===1) { return 1 }이므로, number가 1일 때가 기저 조건이다.

기저 조건일 때 함수는 재귀 없이 1을 반환한다. 즉, factorial(1)의 반환 값은 1이다.

factorial(2)는 2 * factorial(1)을 반환한다. factorial(1)은 1을 반환하므로, factorial(2)는 2 * 1, 즉 2를 반환한다.

factorial(3)은 3 * factorial(2)를 반환하므로, 6을 반환한다.

10.4 컴퓨터의 눈으로 바라본 재귀

인간은 10.3의 방식처럼 기저 조건으로부터 재귀를 추론할 수 있다. 하지만 컴퓨터는 함수 내에서 다시 그 함수를 호출하는 복잡한 작업을 수행해야 한다.

factorial(3)은 3 * factorial(2)를 반환하므로, 컴퓨터는 factorial(3)이 끝나기 전에, 즉 실행하는 중에 factorial(2)를 또 실행한다. factorial(2)를 실행하는 중에 factorial(1)이 실행되는 것도 마찬가지다.

컴퓨터는 factorial(1)이 끝나면 다시 돌아가 factorial(2)를 마저 실행해야 한다는 사실, factorial(2)가 끝나면 factorial(3)을 완료해야 한다는 사실을 기억해야 한다.

10.4.1 호출 스택

컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다. 이 스택을 호출 스택이라고 부른다.

factorial(3)을 호출한다. 하지만 이 함수가 종료되기 전에 factorial(2)를 호출한다. 컴퓨터가 factorial(3)가 아직 종료되지 않았음을 알려면 컴퓨터는 factorial(3)을 호출 스택에 푸시해야 한다.

factorial(2)를 실행하면 factorial(1)을 호출한다. factorial(2)가 아직 종료되지 않았음을 알아야하므로 factorial(2) 역시 호출 스택에 푸시한다.

factorial(1)은 기저 조건이므로 factorial() 함수를 호출하지 않고 끝난다. factorial(1)이 끝났는데 호출 스택에 아직 함수들이 남아있다.

호출 스택에 데이터가 있으면 컴퓨터에 아직 해야 할 일이 남았다는 뜻이며, 실행 중인 다른 함수를 마무리해야 한다는 뜻이다.

스택은 LIFO 원칙이다. 호출 스택에 Last In 된 원소는 가장 최근에 호출된 함수, 다음으로 마무리해야 하는 함수다.

컴퓨터는 호출 스택의 함수들 중 가장 위 원소인 factorial(2) 함수를 팝해서 완료한다. 다음 가장 위 원소인 factorial(3) 함수를 팝해서 완료한다. 이제 호출 스택이 비었고, 재귀가 끝난다.

이러한 방법을 호출 스택을 통해 값 위로 전달하기라고 부르기도 한다. 각 재귀 함수는 계산된 값을 부모 함수에 반환하고, 최초에 호출된 함수가 최종 값을 계산한다.

10.4.2 스택 오버플로

무한 재귀에선 컴퓨터가 반복해서 같은 함수를 호출 스택에 푸시한다. 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 호출 스택은 점점 늘어나고, 스택 오버플로 오류가 발생한다. 컴퓨터는 재귀를 강제로 중단한다.

10.5 파일 시스템 순회

재귀와 어울리는 문제 유형은 몇 단계나 깊이 들어가야 하는지 모르는 상황에서 문제를 여러 단계로 파고 들어야 할 때이다.

파일 시스템을 순회하는 예제를 살펴보자. 어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리명을 출력한다. 디렉터리의 하위 디렉터리, 그 디렉터리의 하위 디렉터리에 있는 모든 파일들에 대해 수행되어야 한다.

for 문이나 forEach 메서드를 사용한다면 현재 디렉터리의 바로 다음 하위 디렉터리명만 출력할 것이다. 하위 디렉터리의 하위 디렉터리를 출력하지 않는다.

for 문이나 forEach 메서드를 두 번 중첩한다고 해도 두 단계만 들어갈 수 있을 뿐, 그 밑의 단계까지 들어갈 수 없다. 그렇다고 하위 디렉터리가 얼마나 많이 있을지 알 수 없으므로 무턱대고 계속 중첩할 수도 없다.

이럴 때 재귀를 사용할 수 있다. 파일이 하위 디렉터리라면 해당 하위 디렉터리에 재귀적으로 하위 디렉터리를 찾는 함수를 호출하면 된다.

10.6 마무리

알고리즘이 임의의 단계만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다.