재귀적으로 작성하는 법을 보다 쉽게 익힐 수 있는 기법을 소개한다.

11.1 재귀 카테고리: 반복 실행

반복적으로 한 작업을 실행하는 알고리즘에 재귀 함수를 적용할 수 있다.

이전에 다뤘던 카운트 다운 함수를 예시로 들어보자.

function countdown(number) {
  console.log(number);

  if (number === 0) {
    return;
  } else {
    countdown(number - 1);
  }
}

반복 실행 카테고리에 속하는 문제들은 함수의 마지막 줄에서 단순히 그 함수를 다시 한 번 호출한다. 위의 예제에선 coundown(number - 1)이다.

11.1.1 재귀 트릭: 추가 인자 넘기기

숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성하려고 한다. 단, 새 배열을 만드는 것이 아니라 배열 자체에서 수정해야 한다.

function doubleArray(array, index) {
  if (index >= array.length) {
    return;
  }

  array[index] *= 2;
  doubleArray(array, index + 1);
}

const array = [1, 2, 3, 4];
doubleArray(array, 0);

console.log(array);		// [2, 4, 6, 8]

배열 내 각 숫자의 인덱스를 기록하고 증가하기 위해 함수의 인자로 index를 추가로 전달한다.

function doubleArray(array, index = 0) {
  if (index >= array.length) {
    return;
  }

  array[index] *= 2;
  doubleArray(array, index + 1);
}

const array = [1,2,3,4]
doubleArray(array)

console.log(array);		// [2, 4, 6, 8]

인자 index는 항상 0부터 시작해야 한다. 이 때 인자의 기본값으로 0을 할당해주면 함수를 처음 호출할 대 인덱스 인자를 전달하지 않아도 된다.

11.2 재귀 카테고리: 계산

재귀가 유용하게 쓰이는 한 가지 영역이 임의의 단계 만큼 깊이 들어가는 문제를 풀 때라고 배웠지만, 유용하게 쓰이는 또 하나의 영역은 하위 문제의 계산 결과에 기반해 계산할 수 있을 때다.

이전에 다뤘던 팩토리얼 함수가 예시이다.

팩토리얼 함수를 구현할 대는 1부터 n까지 순차적으로 곱하는 전형적인 반복문을 사용할 수도 있다.

function factorial(n) {
  let product = 1;

  for (let i = 1; i <= n; i++) {
    product *= i;
  }

  return product;
}

반복문이 아니라 하위 문제에 기반해 팩토리얼을 계산할 수 있다.

하위 문제는 입력을 더 작게 한 똑같은 문제다.