Recursion คืออะไร?

Introduction

ในบทนี้เราจะมาพูดคุยกันถึงเรื่องของ ‘Recursion’ ซึ่งเป็นอีกหนึ่งคอนเซ็ปสำคัญที่เราสามารถหยิบนำไปใช้แก้ปัญหาได้หลากหลายมาก

แต่ก่อนที่เราจะไปลงรายละเอียดกัน เรามาเริ่มที่คำถามง่าย ๆ กันก่อน (เช่นเคย) ก็คือคำถามที่ว่า “Recursion คืออะไร?”

คิวที่เท่าไหร่?

“ณ ร้านอาหารแห่งหนึ่งคุณกำลังต่อคิวเพื่อที่จะซื้ออาหารเช้า แต่ด้วยความที่คิวยาวมาก คุณจึงอยากรู้ว่าเหลืออีกกี่คิวถึงจะถึงคิวของตัวเอง; ‘เราอยู่คิวที่เท่าไหร่?’”

คำถามคือเราจะแก้ปัญหานี้ยังไง?

เราอาจจะบอกว่าลองเดินออกไปไล่นับก็ได้ว่ามีทั้งหมดกี่คน แต่อีกวิธีการนึงที่ง่ายกว่า สะดวกกว่า ที่เราสามารถทำได้ก็คือการ “ถามคนด้านหน้าว่าอยู่คิวที่เท่าไหร่ จากนั้นพอได้คำตอบมาก็บวกหนึ่งกลายเป็นคิวของตัวเอง”

แต่แน่นอนว่าคนด้านหน้าก็ไม่รู้คิวของตัวเองเหมือนกัน ดังนั้นสิ่งที่คนด้านหน้าเราทำได้ก็คือการ “ถามคนด้านหน้าว่าอยู่คิวที่เท่าไหร่ จากนั้นพอได้คำตอบมาก็บวกหนึ่งกลายเป็นคิวของตัวเอง”

ถามกันไปเรื่อย ๆ จนกระทั้งถึงคนหน้าสุด ซึ่งแน่นอนว่าคนหน้าสุดก็ต้องรู้คิวตัวเองอยู่แล้วว่าอยู่คิวที่ 1 (จะไปถามคนขายต่อก็แปลก ๆ ใช่ไหมหละ) คิวแรกเลยหันไปบอกด้านหลังว่าตัวเองอยู่คิวที่ 1 นะ และพอคนด้านหลังได้รับคำตอบก็รู้ทันทีว่าตัวเองอยู่คิวที่ 2 จากนั้นก็บอกกลับต่อไปเรื่อย ๆ จนกระทั้งเรารู้คิวจากคนก่อนหน้าเรา เราก็จะได้คำตอบแล้วว่าเราอยู่คิวที่เท่าไหร่

Recursion คืออะไร?

จากเรื่องราวข้างต้นเชื่อว่าหลาย ๆ คนน่าจะสังเกตเห็น pattern อะไรบางอย่าง

เราจะเห็นว่า “คำตอบของคำถามที่เราถามตัวเอง ขึ้นอยู่กับคำตอบของ ‘คำถามเดียวกัน’ ที่เราถามคนก่อนหน้า” ซึ่งเราสามารถ define ความสัมพันธ์นี้ออกมาง่าย ๆ ได้ว่า

เรา ‘คิวที่เราไหร่?’ = คนก่อนหน้า ‘คิวที่เราไหร่?’ + 1

จะเห็นว่า definition ที่เราเขียนออกมานี้มันมีการ ‘อ้างอิงถึงสิ่งที่มีหน้าตาเหมือนตัวมันเอง’ อยู่ และสิ่งที่เราเขียนออกมานี้เองคือสิ่งที่เราเรียกมันว่า ‘Recursive definition’ ซึ่งเป็นสิ่งที่ใช้ในการอธิบาย ‘Recursion’ (หรือ process ที่เกิดขึ้นเหมือนในภาพตัวอย่าง) นั่นเอง

“Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself.” — Wikipedia, Informal Definition

แต่แน่นอนว่าการที่เรา define ความสัมพันธ์ออกมาแบบนี้มันทำให้เกิดอีกคำถามนึงตามมาก็คือ “แล้วมันจะไปจบที่ไหน?” ไม่ใช่ว่าเราสามารถรันตาม definition ไปได้เรื่อย ๆ ไม่มีจุดจบหรอ?

คำตอบก็คือใช่ครับ ถ้าเรา define มันออกมาไม่ดีเราอาจจะเจอกับ ‘Infinite Recursion’ ได้ ดังนั้นโดยปกติแล้วเวลาที่เราจะเขียน recursive definition แบบนี้ออกมา เราต้องคำนึงถึงคุณสมบัติหลัก ๆ สองอย่างคือ

1. Recursive Case คือเคสที่เรานิยามสิ่ง ๆ หนึ่งโดยอ้างอิงถึงอีกสิ่ง ‘ที่มีหน้าตาเหมือนตัวมันเองในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า’
2. Base Case คือเคสสิ้นสุด เป็นเคสที่นิยามของเรา ‘ไม่ได้ขึ้นอยู่กับสิ่งที่มีหน้าตาเหมือนกับตัวเองอีกแล้ว’

ซึ่งจากตัวอย่างข้างต้น เราสามารถเขียน ‘Recursive case’ และ ‘Base case’ ออกมาได้ดังนี้

1. Recursive Case: เรา ‘คิวที่เราไหร่?’ = คนก่อนหน้า ‘คิวที่เราไหร่?’ + 1
2. Base Case: คนอยู่หน้าสุดไม่ต้องถามใครแล้ว ตอบได้เลยว่าอยู่คิวที่ 1

หรือเราจะเขียนนิยามของ ‘Recursive function’ ออกมาก็ได้เช่นกัน โดยกำหนดให้ \(F(n)\) = เลขคิวของคนที่ \(n\) (โดยที่ \(n\) เป็นจำนวนเต็มบวกที่มากกว่า 1):

1. Recursive Case: \(F(n) = F(n-1) + 1\)
2. Base Case: \(F(1) = 1\)

แล้วเราก็สามารถเอา definition ข้างต้นมาเขียนออกมาเป็นโค้ดได้ดังนี้เลย

1
function F(n) {
2
  if (n == 1) return 1;
3
  return F(n - 1) + 1;
4
}

โดยสรุปแล้วถ้าหากว่าเราจะเขียน recursive definition เพื่อใช้ในการแก้ปัญหาใดปัญหาหนึ่ง เราต้องแน่ใจให้ได้ว่าสิ่งที่เราเขียนหรือนิยามออกมามันต้องมีจุดจบหรือจุดสิ้นสุด หรือพูดง่าย ๆ ก็คือเราต้องแน่ใจว่า ‘recursive case ที่เรานิยาม มันต้องเล็กลงเรื่อย ๆ และวิ่งเข้าสู่ base case ในที่สุด’

Recursion In Programming

เชื่อว่าหลาย ๆ คนน่าจะเห็นภาพของคำว่า recursion กันแล้ว ดังนั้นเพื่อให้เข้าใจมากขึ้น เดี๋ยวเรามาลองดูตัวอย่างปัญหาในการเขียนโปรแกรมที่เราสามารถแก้ได้โดยใช้ recursion กันบ้างดีกว่า

Reverse String

ให้เขียน function reverse(str) ที่รับ input เป็น string และรีเทิร์นผลลัพธ์ที่เป็นการกลับด้านของ string ดังกล่าว (แนะนำให้ลองแก้ปัญหาโดยใช้ recursion ก่อนดูเฉลย)

จากหัวข้อที่แล้วเราคุยกันว่า การกำหนด recursive case ตอนที่เราจะเขียน recursive definition นั้น เราจะเขียนอยู่ในรูปแบบที่ “นิยามของสิ่ง ๆ หนึ่ง อ้างอิงถึงอีกสิ่งที่มีหน้าตาเหมือนตัวมันเองในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า”

ซึ่งแน่นอนว่าเราจะไม่มีทางเขียนนิยามดังกล่าวออกมาได้เลยถ้าเราไม่กำหนดกันก่อนว่าไอ้ ‘สิ่ง ๆ หนึ่ง’ ที่ว่ามันมีหน้าตาเป็นอย่างไร

สำหรับการเขียน recursive function นั้น ไอ้สิ่ง ๆ หนึ่งที่ว่าก็คือจุดประสงค์ของ function ที่เราจะเขียนนั่นหละ หรือพูดง่าย ๆ ก็คือ function นี้รับค่าอะไร (input) และรีเทิร์นค่าอะไรออกมา (output)

สำหรับในปัญหานี้เราจะกำหนดไว้เลยว่า

“reverse(str) จะ return ค่าที่เป็นการกลับด้านของ str”

คราวนี้พอเรารู้ละว่า ‘สิ่ง ๆ หนึ่ง’ หรือ reverse(str) มันมีหน้าตาเป็นอย่างไร เราก็สามารถถามคำถามที่สำคัญต่อมาได้แล้วว่า “reverse(str) ในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่ามีหน้าตาเป็นอย่างไร? และเราสามารถเอาคำตอบของ reverse(str) ในเวอร์ชั่นก่อนหน้ามาแก้ปัญหาใหญ่ได้อย่างไร?”

หรือถ้าให้สรุปเป็นคำถามเดียวง่าย ๆ

“หนึ่ง step ก่อนหน้าที่จะแก้ปัญหาได้ มีหน้าตาเป็นอย่างไร?”

สิ่งแรกคือเริ่มจากการทำความเข้าใจปัญหาก่อน โดยเราจะเริ่มจากการเขียนเทสเคสต่าง ๆ ออกมา

• reverse(“a”) = “a”
• reverse(“ab”) = “ba”
• reverse(“abc”) = “cba”
• reverse(“abcd”) = “dcba”

ถ้าเราลองสังเกตดูเราก็จะเห็นว่า

• reverse string มันเกิดจากการดึงตัวท้ายมาไว้ด้านหน้าเรื่อย ๆ ดังนั้นหนึ่ง step ก่อนที่จะแก้ปัญหาได้ก็คือดึงตัวท้ายสุดมาไว้ด้านหน้า เช่นถ้า str = “abcd”; step ก่อนหน้าก็คือการดึง “d” ซึ่งเป็นตัวท้ายสุดมาไว้ด้านหน้าของ “cba"
• "cba” มันก็คือส่วนกลับของ “abc” ซึ่งจำที่เรากำหนดไว้ตอนแรกได้ไหมครับว่า “reverse(str) จะ return ค่าที่เป็นการกลับด้านของ str”; ดังนั้นเราก็แค่เรียกใช้ function reverse นี้กับ “abc” ให้มัน take care ผลลัพธ์ให้เรา: reverse("abcd") = d + reverse("abc")
• จะเห็นว่า reverse(str) ในเวอร์ชั่นก่อนหน้าก็คือ reverse(str) ที่ str มีความยาวลดลง 1 หน่วยนั่นเอง โดยจุดสิ้นสุดก็คือ str มีความยาวหนึ่งหน่วย ซึ่งเราก็แค่ return ตัวอักษรนั้นออกมา ไม่จำเป็นต้อง reverse อะไรอีกแล้ว: reverse("a") = a

จากข้อสังเกตข้างต้นนี้เอง เราก็สามารถเขียน recursive case ออกมาได้ดังนี้

ส่วน base case ของเราก็คือกรณีที่ str ของเรามีความยาว 1 หน่วยนั่นเอง

สุดท้ายนี้เราก็เขียนเป็นโค้ดออกมาได้ดังนี้เลย

1
function reverse(str) {
2
  if (str.length <= 1) return str;
3

4
  const last_char = str[str.length - 1];
5
  const without_last_char = str.slice(0, -1);
6
  return last_char + reverse(without_last_char);
7
}

Binary Search

ในบทที่แล้วเราได้คุยถึง search algorithm ตัวหนึ่งที่ทรงพลังมาก ๆ นั่นก็คือ ‘Binary Search’

สำหรับไอเดียมันง่ายมาก สมมุติว่าเราอยากจะหาค่าบางค่าใน ‘sorted array’ เราก็จะเริ่มจากการเช็คค่าตรงกลางของช่วงที่เราหาอยู่ (ในตอนเริ่มต้นช่วงคือทั้ง array ตั้งแต่ 0 ถึง n - 1) จากนั้นก็เทียบว่าค่าตรงกลางนั้นมากกว่าหรือน้อยกว่าค่าที่เรากำลังหา และตัดช่วงที่เรากำลังหาออกครึ่งหนึ่ง; ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งเจอค่าที่เราต้องการ

โดยเราสามารถ define binarySearch ออกมาได้ว่า

“binarySearch(arr, target, left, right) จะ return ค่า index ของ target ที่อยู่ในช่วง left และ right ของ arr; ถ้าหากไม่มี target อยู่ในช่วงนั้นจะ return null”

ลองกดเล่นทำความเข้าใจเพิ่มเติมด้านล่างได้เลยครับ ⤵

ถ้าหากว่าเราสังเกตการทำงานของมัน เราก็จะพบว่า

• Step ก่อนหน้าที่จะแก้ปัญหาได้ก็คือ: เช็คตรงกลาง ถ้าตรงกลางตรงกับ target ก็ตอบเลย หรือถ้าไม่ก็ไป “หาคำตอบจากช่วงย่อยที่เล็กลงครึ่งหนึ่ง” มาเป็นคำตอบ
• “หาคำตอบจากช่วงย่อยที่เล็กลงครึ่งหนึ่ง” ก็คือปัญหาเดียวกันกับที่เรา define binarySearch เอาไว้นั่นหละดังนั้นเราก็เรียกใช้ binarySearch เพื่อแก้ปัญหาได้เลย: เช็คตรงกลาง ถ้าตรงกลางตรงกับ target ก็ตอบเลย หรือถ้าไม่ก็ไปเอา binarySearch(ช่วงย่อย) มาเป็นคำตอบ
• จะเห็นว่า binarySearch ในเวอร์ชั่นก่อนหน้าก็คือ binarySearch ที่ช่วงมีความยาวสั้นลงเรื่อย ๆ ครึ่งหนึ่ง ซึ่งถ้าหากว่าช่วงมีความยาวน้อยกว่า 0 แล้ว ก็ควรจะหยุดทำงาน

จากตรงนี้เราสามารถเขียน recursive และ base case ออกมาได้ว่า

1. Recursive Case: \(Bsearch(\text{arr}, \text{target}, \text{left}, \text{right}) = \)
   • If \(\text{mid} > \text{target}\): return \(Bsearch(\text{arr}, \text{target}, \text{left}, \text{mid} - 1)\)
   • If \(\text{mid} < \text{target}\): return \(Bsearch(\text{arr}, \text{target}, \text{mid} + 1, \text{right})\)
2. Base Case:
   • If \(\text{mid} = \text{target}\): return \(\text{mid}\)
   • If \(\text{left} > \text{right}\): return \(\text{null}\)

สุดท้ายนี้เราก็เขียนเป็นโค้ดออกมาได้ดังนี้เลย

1
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
2
  if (left > right) return null;
3

4
  let mid = Math.floor(left + (right - left) / 2);
5
  if (arr[mid] === target) return mid;
6

7
  if (arr[mid] > target) {
8
    return binarySearch(arr, target, left, mid - 1);
9
  } else {
10
    return binarySearch(arr, target, mid + 1, right);
11
  }
12
}

File System

อีกตัวอย่างหนึ่งที่ทุกคนคุ้นเคยกันเป็นอย่างดีก็คือ ‘File System’ หรือระบบจัดการไฟล์ที่เราใช้กันอยู่ทุกวันนี้นั่นเอง ซึ่งประกอบไปด้วย Folder และ File

คำถามก็คือว่าจากภาพข้างต้นเราจะเขียนโปรแกรมเพื่อ “แสดงชื่อไฟล์ทั้งหมดใน folder books” อย่างไร?

ซึ่งนั่นรวมไปถึงคำถามด้วยว่าเราจะเก็บข้อมูลในรูปแบบไหน? ลองจินตนาการว่าเรามีไฟล์เยอะกว่านี้หลายเท่าและมี folder ทับซ้อนกันหลายชั้นมาก ๆ

ถ้าหากว่าเราลองสังเกต structure ของข้อมูลดูเราก็จะพบว่า

1. ในหนึ่ง folder จะมี folder หรือ file อยู่ในนั้นกี่อันก็ได้
2. ใน file จะไม่มี folder หรือ file อยู่ในนั้นอีกแล้ว

ถึงตรงนี้เราอาจจะมองให้มัน general ขึ้นมาหน่อยว่า folder กับ file มันก็คือก้อนข้อมูลก้อนหนึ่งนั่นหละ โดยในที่นี้ขอเรียกว่า ‘Node’ ละกัน โดย node ก็มีได้ 2 ประเภทคือ folder และ file

“Node คือก้อนข้อมูลที่มีสองชนิดคือ folder และ file”

จากการนิยามตรงนี้เองเราสามารถเขียนออกมาได้ว่า

1. ถ้า Node มีชนิดเป็น folder ในนั้นจะมีอีกกี่ Node ก็ได้ (Recursive Case)
2. ถ้า Node มีชนิดเป็น file จะไม่มี Node อยู่ภายในนั้นอีกแล้ว (Base Case)

ซึ่งเราสามารถเขียนออกมาเป็น type ได้ดังนี้ (อันนี้เป็นตัวอย่างภาษา Typescript)

1
type Node =
2
  | {
3
      type: "folder";
4
      name: "string";
5
      contents: Node[];
6
    }
7
  | {
8
      type: "file";
9
      name: "string";
10
    };

โดยเราก็สามารถเก็บข้อมูลลงไฟล์ JSON ออกมาได้ดังนี้

1
{
2
  "type": "folder",
3
  "name": "books",
4
  "contents": [
5
    {
6
      "type": "folder",
7
      "name": "finished",
8
      "contents": [
9
        {
10
          "type": "file",
11
          "name": "reality-is-not-what-it-seems-notes.md"
12
        },
13
        {
14
          "type": "file",
15
          "name": "Reality Is Not What It Seems.png"
16
        }
17
      ]
18
    },
19
    {
20
      "type": "file",
21
      "name": "grokking-algorithm-notes.md"
22
    },
23
    {
24
      "type": "file",
25
      "name": "Grokking Algorithm.png"
26
    }
27
  ]
28
}

รูปแบบการจัดเก็บข้อมูลข้างต้นนี้เราเรียกมันว่า ‘Tree’ ครับ เป็น data structure ตัวหนึ่งที่มีโครงสร้างเป็นลำดับชั้น ซึ่งประกอบไปด้วย node และแต่ละ node ก็อาจจะมี children เป็น node อื่น ๆ อีกกี่ตัวก็ได้ ซึ่ง tree เองก็เป็น data structure แบบหนึ่งที่เราเรียกมันว่า ‘Recursive data structure’ นั่นเอง

คราวนี้กลับมาที่คำถามว่า เราจะเขียนโปรแกรมเพื่อแสดงชื่อไฟล์ทั้งหมดใน folder books ได้อย่างไร?

พอมาถึงตรงนี้ไม่ยากแล้วครับ เพราะสิ่งที่เราต้องทำก็คือ “เขียนโค้ดไปตามรูปแบบของข้อมูล” เราก็แค่ต้องเขียน recursive function ที่มันสอดคล้องตาม recursive structure ของข้อมูลออกมา

โดยกำหนดให้ “print(node) คือการ print file names ทั้งหมดภายใน node นั้นออกมา”

1. Recursive case: print(node_folder) = loop contents { print(content[i]) }
2. Base case: print(node_file) = console.log(file.name)

สุดท้ายนี้เราก็เขียนเป็นโค้ดออกมาได้ดังนี้เลย

1
function print(node) {
2
  // Base case
3
  if (node.type === "file") {
4
    console.log('File name:', node.name);
5
    return;
6
  }
7

8
  // Recursive case
9
  if (node.type === "folder") {
10
    // ทำการ recursive call: Node แต่ละ Node ภายใน contents
11
    for (let i = 0; i < node.contents.length; ++i) {
12
      print(node.contents[i])
13
    }
14
  }
15
}

จะเห็นว่ารูปแบบการเก็บข้อมูลนั้นส่งผลโดยตรงกับ algorithm ที่ใช้ในการจัดการข้อมูลนั้น รูปแบบข้อมูลที่เป็น recursive ย่อมก็เหมาะกับการวิธีจัดการแบบ recursive นั่นเอง

บทสรุป

จากตัวอย่างข้างต้นจะเห็นว่า recursion ในการเขียนโปรแกรมนั้นมีอยู่ทุกที่เลยทั้งในเชิงของลำดับในการแก้ปัญหา (ดูตัวอย่าง Reverse string, Binary Search) หรือทั้งในเชิงของรูปแบบการเก็บข้อมูล (ดูตัวอย่าง File system)

โดยการจะแก้ปัญหาโดยใช้ recursion ได้นั้นเราต้องเขียน recursive definition ออกมาให้ชัดเจนซึ่งประกอบไปด้วย

1. Recursive Case คือเคสที่เรานิยามสิ่ง ๆ หนึ่งโดยอ้างอิงถึงอีกสิ่ง ‘ที่มีหน้าตาเหมือนตัวมันเองในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า’
2. Base Case คือเคสสิ้นสุด เป็นเคสที่นิยามของเรา ‘ไม่ได้ขึ้นอยู่กับสิ่งที่มีหน้าตาเหมือนกับตัวเองอีกแล้ว’

โดยก่อนหน้าที่จะเขียน case เหล่านี้ออกมาได้ เราจะเป็นต้องเห็นภาพของ ‘สิ่ง ๆ หนึ่ง’ ซะก่อน และพอเราเห็นภาพแล้ว มันก็จะทำให้เราถามคำถามอื่น ๆ ต่อไปที่สุดท้ายแล้วจะนำมาสู่การเขียน recursive definition ได้ เช่น

• ‘สิ่ง ๆ หนึ่ง’ ในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า มีหน้าตาเป็นอย่างไร?
• เราสามารถเอานิยามของ ‘สิ่ง ๆ หนึ่ง’ ในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า มารวมเป็นส่วนหนึ่งของภาพใหญ่หรือนิยามใหญ่ได้อย่างไร
• หนึ่ง step ก่อนที่เราจะแก้ปัญหาได้คืออะไร?

สุดท้ายนี้จะเห็นว่าการที่จะเห็น recursive pattern หรือไม่นั้น ล้วนขึ้นอยู่กับการ define ‘สิ่ง ๆ หนึ่ง’ ด้วยกันทั้งสิ้น ถ้าเรากำหนด ‘สิ่ง ๆ หนึ่ง’ ในแบบที่มันมีอีก ‘สิ่ง ๆ หนึ่ง’ อยู่ในนั้นได้ ก็แสดงว่าเราสามารถเขียน recursive definition ออกมาได้ และอะไรเหล่านี้ล้วนเป็น skill ที่เราต้องฝึกทั้งสิ้น

สำหรับเรามันก็เหมือนกับกระจกสองแผ่นที่วางขนานกันนั่นหละ ถ้าหากว่าเราไปยืนหรือมองอยู่ในจุดที่ถูกต้อง เราก็จะเห็นกระจกที่ทับซ้อนกันแบบไม่รู้จบปรากฏขึ้นมานั่นเอง

Challenge Problem

โจทย์กำหนดให้รับ input มาหนึ่งตัวเป็น array ที่มี element เป็นตัวเลขหรือจะเป็น array แบบเดียวกันซ้อนลึกลงไปกี่ชั้นก็ได้ ให้เขียน function ที่ชื่อว่า flatten ที่จะ return ค่าออกมาเป็น array ของตัวเลขใน array ทั้งหมด โดยจำนวนชั้นความลึกจะต้องเหลือเพียง level เดียวเท่านั้น

Example 1:

Example 2:

Example 3:

Solution #1

ในข้อนี้เราอาจจะเริ่มจากการทำความเข้าใจ recursive structure ของข้อมูลกันก่อน (จะเห็นว่า array อาจจะทับซ้อนกันกี่ชั้นก็ได้) สมมุติว่าถ้าหากเราลองดึงข้อมูลสักตัวจาก \(\text{arr}\) ออกมาดูเช่น \(\text{arr[0]}\) เราจะเห็นว่า element ที่ดึงออกมามีอยู่ 2 ชนิดที่เป็นไปได้

1. เป็น array: ซึ่งภายใน array นั้นถ้าเราลองดึง \(\text{arr[0]}\) ออกมาก็อาจจะเป็น array หรือ number อยู่ภายในนั้นก็ได้
2. เป็น number (เราอาจจะมองว่าเป็น base case ของข้อมูล)

เราอาจจะลองแก้ปัญหาเล็ก ๆ ออกมาดูก่อน โดยการเขียน recursive function ที่ flatten เฉพาะแค่ element ตัวแรกของ \(\text{arr}\) ซึ่งในที่นี้จะขอเรียก element นี้ว่า ‘head’ (ถ้าเราสามารถ flatten element ตัวแรกได้เราก็สามารถเอาไป apply กับ element ตัวอื่น ๆ ใน \(\text{arr}\) ได้ เพราะตัวอื่น ๆ มันก็คือปัญหาเดียวกันนั่นหละ)

โดยเราสามารถเขียนโค้ดออกมาได้ดังนี้

1
function flatten(arr) {
2
  // ในกรณีที่เป็น empty arr ก็ให้ return [] ออกมา
3
  if (arr.length === 0) return [];
4
  // Base case: ถ้าหากว่า head เป็น number ก็ให้ return [head] ออกไปและจบการทำงาน
5
  const head = arr[0];
6
  if (typeof head === "number") return [head];
7
  // Recursive case: ส่วนในกรณีที่  head เป็น array ก็ให้ทำการ flatten head นั้นต่อไป
8
  else return flatten(head)
9
}

ถ้าเราลองรันดูเราก็จะพบว่าตอนนี้เราสามารถ flatten array ในกรณีที่ array มีตัวเดียวได้แล้วเช่น flatten([[[]]]) → [] หรือ flatten([[[10]]]) → [10] แต่ก็จะเห็นว่าคำตอบของเรามันไม่ได้ include element ตัวอื่น ๆ เข้ามาด้วยเช่น flatten([[[10], 20]]) → [10]

ด้วยความที่ element ตัวที่เหลือก็เป็นปัญหาเดียวกันกับที่เราพึ่งแก้ไป (เป็น \(\text{arr}\) ที่ด้านในมี array หรือ number) ยกตัวอย่างเช่นถ้าให้ arr = [1, [2], [[3]]]

• 1 ก็คือ head ส่วน [[2], [[3]]] ก็คือตัวที่เหลือ (ในที่นี้จะขอเรียกว่า tail ละกัน)
• ซึ่งเราจะเห็นว่า tail จริง ๆ แล้วมันก็คือปัญหาใหม่ที่เล็กลงนั้นหละ (เพราะถูกตัด head ออกไป) เราอาจจะมองลึกไปได้อีกว่า [[2], [[3]]] = [2] (head) รวมกับ [[3]] (tail)

ดังนั้นเราก็สามารถ apply flatten ลงไปใน tail ได้เลยจากนั้นก็นำคำตอบที่ได้มารวมเข้ากับ head ที่เรา flatten มันไปแล้วนั่นเอง ซึ่งถ้าหากเราลอง breakdown ดูเราก็จะเห็นเป็นภาพประมาณนี้ครับ

1. flatten([1, [2], [[3], 4], [[[[5]]]]]) = flatten([1]) + flatten([[2], [[3], 4], [[[[5]]]]])
2. flatten([[2], [[3], 4], [[[[5]]]]]) = flatten([[2]]) + flatten([[[3], 4], [[[[5]]]]])
3. flatten([[3], 4], [[[[5]]]]) = flatten([[3], 4]]) + flatten([[[[5]]]])
4. flatten([3], 4]) = flatten([[3]]) + flatten([4])

โดยเราสามารถเขียนนิยามของ recursive function นี้ออกมาได้ว่า

1. Recursive case: flatten(arr) = flatten(head) + flatten(tail)
2. Base case: ในกรณีที่ head เป็น number ก็ไม่จำเป็นต้อง flatten อีกต่อไปแล้ว เราก็แค่เอา head ไปรวมเข้ากับ flatten(tail) ได้เลย; flatten(arr) = [head] + flatten(tail)
   • ซึ่ง tail ก็จะเล็กลงไปเรื่อย ๆ จนกระทั้งกลายเป็น empty array

และจากนิยามข้างต้นเราก็สามารถเขียนเป็นโค้ดได้ดังนี้เลยครับ

1
function flatten(arr) {
2
  if (arr.length === 0) return [];
3

4
  const head = arr.shift(); // ดึงตัวแรกสุดของ arr ออกมา
5
  const tail = arr; // arr ที่เหลือที่ถูกดึง head ออกไปแล้ว
6

7
  // Base Case
8
  if (typeof head === "number") return [head, ...flatten(tail)];
9
  // Recursive Case
10
  else return [...flatten(head), ...flatten(tail)]
11
}

เพิ่มเติม: ในส่วนของโค้ดจะเห็นว่ามีเครื่องหมาย ‘…’ อยู่หน้าตัวแปร เราเรียกมันว่า ‘Spread Operator’ ซึ่งเราสามารถใช้มันในการ spread หรือกระจายค่าภายใน array ออกมารวมกันได้เช่น a = [1,2], b = [3,4] ถ้าเราให้ c = [...a, ...b] ตัวแปร c จะมีค่าเท่ากับ [1,2,3,4]