Prefix Sums (สร้างอาร์เรย์ผลรวมเพิ่มขึ้น) ด้วย Recursion ใน JavaScript

พิจารณาอาร์เรย์ตัวเลข

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 ของสมาชิกที่ต้องการโดยเปรียบเทียบ index เราจะได้ผลลัพธ์

โค้ด

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: ใช้ฟังก์ชัน Recursive

ที่นี่เราจะใช้สองฟังก์ชัน recursive

• แรกคือ sumRecursively(arr, start) คืนผลรวมสมาชิกของ arr จาก index start จนจบ
• สองคือ partSumRecursively() ที่ recursive concatenate ผลรุมที่ต้องการเข้าไปในอาร์เรย์ และเมื่อถึงท้ายอาร์เรย์ คืนอาร์เรย์ที่ต่อกันแล้ว

โค้ด

ตัวอย่าง

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 ]