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

재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어.

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);
  }
}