지금까지 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠지만 재귀로 확실히 어떤 문제는 해결할 수 있어도 제대로 사용하지 않으면 또 다른 문제가 발생한다.

재귀는 종종 O(2ⁿ)같은 가장 느린 빅 오 카테고리의 주된 요인이 된다.

12.1 불필요한 재귀 호출

다음의 재귀 함수는 배열의 최대값을 찾는다.

function max(array) {
  if (array.length === 1) return array[0];

  if (array[0] > max(array.slice(1))) {
    return array[0];
  } else {
    return max(array.slice(1));
  }
}

만약 배열의 요소가 하나면 그 값이 최대값이 된다.

각 재귀 호출의 핵심은 하나의 수 (array[0])와 나머지 배열의 최대값 간의 비교다.

if-else 조건을 보면, 조건문 앞 뒤로 max() 함수가 두 번 나온다. 이는 비효율적이다.

[1, 2, 3, 4]를 예시로 들면, 1과 [2, 3, 4]의 최댓값을 비교한다. 이어서 2와 [3, 4]의 최댓값을 비교한다. 이어서 3과 [4]를 비교하고, [4]의 최댓값을 찾는 것이 기저 조건이다.

코드가 어떻게 실행되는지 제대로 알려면 바닥 호출부터 분석해 호출 사슬을 따라 올라가야 한다.

12.1.1 max 재귀 분석

max([4])를 호출하면 함수는 단순히 숫자 4를 반환한다. 배열에 원소가 하나일 때가 기저 조건이기 때문이다.

호출 사슬 위로 올라가서 max([3, 4])를 호출하면, 배열의 요소가 1개가 아니므로 3과 max([4])를 비교하면서 max([4])를 호출한다.

3은 4보다 크지 않으므로 else문인 max(array.slice(1))을 실행하고, max([4])가 반환되며 두 번째로 호출된다.

즉, max([3, 4])는 max([4])를 두 번 호출한다.

max([2, 3, 4])는 2와 max([3, 4])를 호출하고, max([3, 4])는 앞서 봤던 것처럼 max([4])를 두 번 호출한다. 그리고 else문에 따라 max([3, 4])를 호출하고, max([4])는 추가로 두 번 더 호출된다.

max([1, 2, 3, 4])를 호출하면 실제로 max함수를 총 15번 호출하게 된다. 이때 모든 15번의 호출이 필요한 것은 아니다. max([4])는 한 번만 호출되면 충분한데도 8번이나 호출되고 있다.

12.2 빅 오를 위한 작은 개선

추가적인 재귀 호출을 전부 없애기 위해서, 코드에서 max를 딱 한 번만 호출하고 그 결과를 변수에 저장하는 방법을 쓴다.