제9장 · 재귀로 재귀하기

§ 1 · 자기 호출루프 대신 재귀

재귀(recursion)는 함수가 자기 자신을 호출하는 것의 공식 이름이다. 깜짝 퀴즈 — 아래 blah()를 호출하면?

무한 재귀 — JavaScript

function blah() {
  blah();
}

blah()가 자신을 호출하고, 그것이 다시 자신을 호출하며 무한히 반복한다. 무한 호출은 쓸모없고 위험하지만, 길들인 재귀는 강력한 도구다.

NASA 카운트다운 함수를 떠올려 보자. 10부터 0까지 출력하는 함수. 대부분 for 루프로 짤 것이다. 그러나 재귀로도 짤 수 있다.

재귀 카운트다운 — JavaScript

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

§ 2 · 멈출 곳기저 사례

위 코드는 완벽하지 않다. 0을 지나 -1, -2... 무한히 음수를 출력한다. number가 0이면 멈추도록 조건문을 추가해야 한다.

기저 사례를 가진 카운트다운 — JavaScript

function countdown(number) {
  console.log(number);
  if(number === 0) {
    return;                  // 기저 사례 — 재귀 중단
  } else {
    countdown(number - 1);
  }
}

핵심 메서드가 재귀하지 않는 경우를 기저 사례(base case)라 한다. countdown 함수에서 0이 기저 사례다. 모든 재귀 함수에는 무한 호출을 막을 기저 사례가 반드시 있어야 한다.

§ 3 · 냅킨 기법재귀 코드 읽기

팩토리얼을 보자. 3! = 3×2×1 = 6. 재귀 구현은 이렇다.

팩토리얼 — Ruby

def factorial(number)
  if number == 1
    return 1                # 기저 사례
  else
    return number * factorial(number - 1)
  end
end

재귀 코드를 읽는 법 — ① 기저 사례를 파악한다. ② 기저 사례를 처리한다고 가정하고 함수를 실행한다. ③ 한 단계씩 위로 올라가며 분석한다. 마치 사실을 냅킨에 적어두고 다음 케이스에서 참고하듯이.

§ 4 · 쌓였다 풀린다호출 스택

컴퓨터도 비슷한 방식을 쓴다. 컴퓨터는 호출 스택(call stack)으로 호출 중인 함수를 추적한다. factorial(3)을 호출하면 — 완료되기 전에 factorial(2)를, 그것이 완료되기 전에 factorial(1)을 호출한다.

모션 · factorial(3)의 호출 스택 단계 01 / 0

space 재생 · → 단계 · R 리셋

함정 무한 재귀는 같은 메서드를 호출 스택에 계속 푸시한다. 컴퓨터 메모리가 바닥나면 스택 오버플로(stack overflow) 오류가 발생한다.

§ 5 · 임의의 깊이재귀의 활용

카운트다운과 팩토리얼은 재귀로도 루프로도 풀 수 있다 — 재귀가 특별한 이점을 주지 않는다. 그러나 재귀는 같은 알고리즘을 알고리즘 안에서 반복해야 하는 상황에 자연스럽게 맞는다.

파일 시스템 순회를 보자. 디렉터리 안에는 하위 디렉터리가, 그 안에 또 하위 디렉터리가 있다. 두 단계, 세 단계... 얼마나 깊을지 모른다. 재귀는 임의로 깊이 들어가는 스크립트를 간단하게 짜게 해준다.

파일 시스템 순회 — Ruby

def find_directories(directory)
  Dir.foreach(directory) do |filename|
    if File.directory?("#{directory}/#{filename}") &&
       filename != "." && filename != ".."
      puts "#{directory}/#{filename}"
      find_directories("#{directory}/#{filename}")   # 재귀!
    end
  end
end

모션 · 재귀 디렉터리 순회 단계 01 / 0

space 재생 · → 단계 · R 리셋

§ 6 · 정리이 장이 남긴 것

재귀는 알고리즘이 무언가를 얼마나 깊이 파고들어야 하는지 처음부터 모를 때 훌륭한 선택이다. 이제 재귀를 이해했으니 초능력을 잠금 해제했다 — 다음 장에서는 재귀가 코드를 훨씬 빠르게 만드는 알고리즘의 핵심임을 본다.