재귀적으로 생각하기: 배열 합의 호출과 복귀를 따라가기

배열 전체의 합은 마지막 값을 제외한 합에 마지막 값을 더한 결과입니다. 배열을 매번 복사하지 않고 남은 원소 수만 줄이면 같은 생각을 더 분명하게 구현할 수 있습니다.

선수 지식: 재귀의 기저 조건, 배열 인덱스, 함수 반환값

• 한 호출이 맡은 문제와 기다리는 결과를 구분합니다.
• 빈 배열을 합의 기저 조건으로 처리합니다.
• 배열 복사 비용과 호출 스택 비용을 따로 셉니다.

앞의 count개 원소의 합이라는 뜻부터 정합니다

[2, 4, 6]의 합을 구할 때 현재 함수가 모든 덧셈을 한 번에 할 필요는 없습니다. 앞의 두 원소 합이 6이라는 답을 받으면 마지막 값 6을 더해 12를 반환할 수 있습니다. 앞의 두 원소 합도 앞의 한 원소 합 2에 4를 더한 값입니다. 이처럼 크기만 다른 같은 문제로 바꾸는 관점이 재귀적 사고입니다.

내부 함수 solve(count)는 배열의 앞쪽 count개 원소의 합을 뜻합니다. count가 3이면 인덱스 0부터 2까지, count가 1이면 인덱스 0까지만 포함합니다. 따라서 현재 호출이 더할 마지막 값의 인덱스는 count가 아니라 count - 1입니다. 함수 매개변수의 의미를 문장으로 고정하면 배열 범위를 헷갈릴 일이 줄어듭니다.

count가 0이면 포함할 원소가 하나도 없습니다. 이때 합은 0입니다. 빈 배열을 별도의 이상한 입력으로 취급하지 않고 자연스러운 가장 작은 문제로 삼으면, 한 원소짜리 배열도 같은 식으로 처리할 수 있습니다. solve(1)은 solve(0) + values[0]이므로 정확히 첫 값이 됩니다.

내려갈 때는 문제를 줄이고 돌아올 때 값을 더합니다

표는 위에서 아래로 호출을 읽고 아래에서 위로 반환을 읽습니다. solve(3)의 6과 solve(2)의 4는 사라진 값이 아닙니다. 각 호출이 어떤 계산을 마쳐야 하는지 기억한 채 작은 답을 기다립니다. 기저 조건이 반환되면 가장 최근에 대기한 덧셈부터 처리되어, 최종 호출에 12가 돌아옵니다.

재귀 호출 뒤에 더하기가 있으므로 이 코드는 누산기를 전달하는 꼬리 호출 형태가 아닙니다. 호출한 순간에 12를 안다고 생각하거나, 재귀 호출을 한 뒤의 문장이 실행되지 않는다고 생각하면 복귀 과정을 놓칩니다. 종이에 대기하는 식을 한 줄씩 적는 것이 실행 순서를 이해하는 데 도움이 됩니다.

같은 배열을 읽고 남은 크기만 바꿉니다

작은 배열을 만들기 위해 매번 마지막 값을 제외한 slice() 결과를 전달할 수도 있습니다. 그러나 길이 n, n – 1, n – 2인 배열을 계속 복사하면 원소 복사량의 합은 O(n²)이 됩니다. 재귀식 자체는 단순해 보여도 작은 문제를 만드는 데 드는 작업을 분석에서 빼면 안 됩니다.

이 예제는 원래 배열을 그대로 읽고 count만 1씩 줄입니다. 배열에 값을 쓰지 않으므로 호출 뒤에도 입력은 그대로입니다. 각 단계의 인덱스 조회와 덧셈은 상수 작업이며, 검사까지 포함한 전체 시간은 O(n)입니다. 새 부분 배열은 만들지 않지만 대기 중인 함수 호출이 있으므로 추가 공간은 O(n)입니다.

원소를 뒤에서 더하는 것과 뒤에서 호출을 만드는 것은 다릅니다. 이 식은 앞부분의 합을 먼저 완성한 다음 뒤의 값을 붙입니다. Number 소수의 덧셈에는 반올림이 있으므로 순서를 바꾸면 아주 작은 오차가 달라질 수 있습니다. 정수 합이 안전한 정수 범위를 벗어나는 문제에서는 BigInt 같은 다른 수 표현이 필요합니다.

빈 배열은 답이고 잘못된 원소는 오류입니다

함수는 빈 칸 없는 유한 숫자 배열을 받고, 빈 배열에서는 0을 반환합니다. 문자열 숫자, NaN, Infinity와 빈 칸이 있는 희소 배열은 거절합니다. 검사 없이 문자열을 더하면 수의 합이 문자열 이어 붙이기로 바뀔 수 있습니다. 계산 중 합이 Infinity가 되는 경우도 오류로 알리지만, 유한한 결과라고 해서 임의의 큰 정수를 정확히 표현한다는 보장은 없습니다.

입력 길이는 학습용으로 256 이하로 제한합니다. 수학적으로는 길이가 줄어 언제나 끝나더라도 실행 환경의 호출 스택은 유한합니다. 긴 배열의 합은 반복문으로 구하면 호출 스택을 늘리지 않고 추가 공간 O(1)로 처리할 수 있습니다. 여기서는 가장 빠른 합산 도구를 만드는 것보다 작은 문제의 답을 재사용하는 흐름을 읽는 데 집중합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function sumArray(values) {
  if (!Array.isArray(values)) throw new TypeError('숫자 배열이 필요합니다.');
  if (values.length > 256) throw new RangeError('길이는 256 이하여야 합니다.');
  for (let i = 0; i < values.length; i++) {
    if (!Object.hasOwn(values, i) || !Number.isFinite(values[i])) {
      throw new TypeError('빈 칸 없는 유한 숫자 배열이 필요합니다.');
    }
  }
  function solve(count) {
    if (count === 0) return 0;
    const result = solve(count - 1) + values[count - 1];
    if (!Number.isFinite(result)) throw new RangeError('Number 범위를 벗어났습니다.');
    return result;
  }
  return solve(values.length);
}

console.log(sumArray([2, 4, 6]));
console.log(sumArray([]));
console.log(sumArray([-5, 2, 3]));

node javascript-recursive-sum-call-return.mjs

12
0
0

비용과 적용 범위

시간: O(n)

공간: O(n)

분석 조건: n은 0~256인 배열 길이입니다. 입력을 복사하지 않고 count만 줄이며 호출 스택을 공간에 포함합니다. Number의 표현 오차는 별도입니다.

직접 확인해 보기

sumArray([3, -1, 5])에서 solve(2)가 반환하는 값과 solve(3)가 그 값을 이용하는 식은 무엇인가요?

함께 읽을 글

• 1부터 N까지 합 출력하기 풀이 — 같은 합산을 반복문으로 처리하는 방법과 비교합니다.
• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 인덱스 조회와 배열 복사에 드는 비용을 연결합니다.
• 자료구조 스택 쉽게 이해하기: push pop으로 문제 풀이 감 잡기 — 남아 있는 덧셈이 복귀 순서대로 처리되는 이유를 이해합니다.

참고 자료

• MDN JavaScript Guide: Functions — 자기 자신을 호출하는 함수와 재귀 호출의 중첩, 기저 조건을 참고했습니다. 호출·복귀 추적과 입력 계약은 별도로 구성했습니다.
• MDN Glossary: Call stack — 실행 중인 함수 호출을 쌓고 반환할 때 제거하는 호출 스택, 지나친 중첩의 제한을 참고했습니다.