JavaScript에서 재귀를 활용해 부분 합 배열 만들기 – map·reduce와 재귀 함수 두 가지 방법

다음과 같은 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [10, 5, 6, 12, 7, 1];

배열의 첫 번째 요소부터 시작해 매 단계마다 한 개씩 요소를 줄여가며 남은 요소들을 모두 더하면 아래와 같은 결과가 나옵니다.

[10, 5, 6, 12, 7, 1] = 10 + 5 + 6 + 12 + 7 + 1 = 41;
[5, 6, 12, 7, 1] = 5 + 6 + 12 + 7 + 1 = 31;
[6, 12, 7, 1] = 6 + 12 + 7 + 1 = 26;
[12, 7, 1] = 12 + 7 + 1 = 20;
[7, 1] = 7 + 1 = 8;
[1] = 1 = 1;

따라서 최종 출력은 다음과 같은 배열이 되어야 합니다.

[ 41, 31, 26, 20, 8, 1 ]

즉, 이렇게 주어진 배열을 입력받아 각 위치에서 시작하는 부분 합(partialSum) 배열을 반환하는 함수를 작성하는 것이 목표입니다.

방법 1: map()과 reduce() 함께 사용하기

아이디어는 아주 간단합니다. 배열의 모든 요소에 대해 각각 하나의 값을 반환해야 하므로, 바로 이 작업을 수행해 주는 Array.prototype.map() 메서드를 활용할 수 있습니다.

여기에 map() 내부에서 인덱스를 비교해 필요한 범위의 요소 합을 reduce()로 계산해 반환하도록 하면 원하는 결과를 손쉽게 얻을 수 있습니다.

예제 코드

const arr = [10, 5, 6, 12, 7, 1];
const partSum = arr.map((item, index) => {
    return arr.reduce((acc, val, ind) => {
        return ind >= index ? acc + val : acc;
    }, 0);
});
console.log(partSum);

방법 2: 재귀 함수 사용하기

이번에는 두 개의 재귀 함수를 활용합니다.

sumRecursively(arr, start): arr의 start 인덱스부터 배열 끝까지의 요소 합을 재귀적으로 계산해 반환합니다.
partSumRecursively(): 앞에서 구한 합계를 재귀적으로 배열에 이어 붙이다가, 배열의 끝에 도달하면 완성된 부분 합 배열을 반환합니다.

예제 코드

const arr = [10, 5, 6, 12, 7, 1];

const sumRecursively = (arr, start = 0, res = 0) => {
    if (start < arr.length) {
        return sumRecursively(arr, start + 1, res + arr[start]);
    }
    return res;
};

const partSumRecursively = (arr, partSum = [], start = 0, end = arr.length - 1) => {
    if (start <= end) {
        return partSumRecursively(arr, partSum.concat(sumRecursively(arr, start)), ++start, end);
    }
    return partSum;
};

console.log(partSumRecursively(arr));

실행 결과

두 방법 모두 콘솔에 동일한 결과가 출력됩니다.

[ 41, 31, 26, 20, 8, 1 ]

정리

두 방법 모두 시간 복잡도는 O(n²)로 동일하지만, map()과 reduce()를 조합한 방식이 코드가 더 간결하고 가독성이 좋습니다. 반면 재귀 방식은 호출 깊이 제한으로 인해 스택 오버플로가 발생할 수 있으므로 아주 긴 배열에는 적합하지 않습니다. 대용량 데이터를 다룬다면 뒤에서부터 누적합을 미리 계산해 O(n)으로 처리하는 반복문 방식을 고려해 보는 것도 좋은 선택입니다.