Iteration & Recursion

Recursion คืออะไร

Recursion (การเรียกซ้ำ) คือเทคนิคที่ฟังก์ชันเรียกตัวเองเพื่อแก้ปัญหาเดิมในขนาดที่เล็กลง — จนถึงจุดที่แก้ได้ทันที (base case) แล้วค่อยรวมคำตอบย้อนกลับขึ้นมา

มองแบบง่าย: "ย่อยปัญหาใหญ่ให้เล็กลงเรื่อย ๆ จนแก้ได้ทันที แล้วค่อยประกอบคำตอบกลับ" — กระบวนการนี้เรียกว่า divide and conquer ในระดับแนวคิด

แนวคิด: ย่อยปัญหาให้เล็กลงจนแก้ได้ทันที

หัวใจของ recursion คือการมองปัญหาผ่านมุมมองที่ "ปัญหาเดิม" = "ปัญหาที่เล็กลง + อีกนิดหน่อย" — เช่น factorial(5) = 5 × factorial(4) และ factorial(1) = 1 (แก้ได้ทันที)

วิธีคิด recursive: 1. ถามตัวเอง: กรณีไหนแก้ได้ทันทีโดยไม่ต้องเรียกซ้ำ? → นั่นคือ base case 2. ถามตัวเอง: กรณีทั่วไปสามารถเขียนในรูปของตัวเองแต่ขนาดเล็กลงได้อย่างไร? → นั่นคือ recursive case 3. เช็กว่า recursive case นั้นพาเข้าใกล้ base case จริง (ขนาดปัญหาลดลงทุกครั้ง)

• Recursion = 1 ปัญหา 2 ส่วน: base case (หยุด) + recursive case (ย่อยต่อ)
• ไม่จำเป็นต้องเข้าใจทุกชั้นการเรียก — เชื่อว่า recursive call ที่เล็กกว่าทำงานถูกต้อง
• ต้องลดขนาดปัญหาทุกครั้งที่เรียกซ้ำ — ไม่งั้นไม่มีทางถึง base case

Base Case และ Recursive Case

ทุก recursion function มี 2 ส่วนที่ขาดไม่ได้ — ถ้าขาดส่วนใดส่วนหนึ่ง ฟังก์ชันจะทำงานผิดพลาด

• Base Case — เงื่อนไขหยุดที่แก้ได้ทันทีโดยไม่ต้องเรียกซ้ำต่อ เช่น n <= 1, n === 0, หรืออาเรย์ว่าง
• Recursive Case — ส่วนที่เรียกฟังก์ชันตัวเองอีกครั้งด้วย input ที่มีขนาดเล็กลงหรือเข้าใกล้ base case มากขึ้น

กฎเหล็ก: ถ้าไม่มี base case → recursion เรียกไม่หยุด (stack overflow) ถ้า recursive case ไม่พาเข้าใกล้ base case → recursion เรียกไม่หยุดเช่นกัน

ตัวอย่าง: countdown(n) — Recursion ที่ง่ายที่สุด

countdown เป็นตัวอย่าง recursion ที่เรียบง่ายที่สุด — ไม่มีการคืนค่าซับซ้อน ไม่ต้อง unwind หลายชั้น แค่พิมพ์ค่าแล้วเรียกตัวเองต่อด้วยค่าน้อยลง

function countdown(n) {
  if (n === 0) {
    console.log("จบการนับถอยหลัง");
    return;
  }

  console.log(n);
  countdown(n - 1);
}

countdown(3);
// 3
// 2
// 1
// จบการนับถอยหลัง

ลำดับขั้นของ countdown(3):

• เรียก countdown(3) → พิมพ์ 3 → เรียก countdown(2)
• เรียก countdown(2) → พิมพ์ 2 → เรียก countdown(1)
• เรียก countdown(1) → พิมพ์ 1 → เรียก countdown(0)
• เรียก countdown(0) → n === 0 → พิมพ์ "จบการนับถอยหลัง" → หยุด

ตัวอย่าง: factorial(n) — Recursion แบบคืนค่ากลับ

factorial เป็นตัวอย่างคลาสสิกที่แสดงการ unwind — เราเรียกซ้ำจนถึง base case แล้วค่อยคูณค่าย้อนกลับขึ้นมาทีละชั้น

function factorial(n) {
  if (n <= 1) {
    return 1;
  }

  return n * factorial(n - 1);
}

console.log(factorial(4)); // 24

ลำดับขั้นของ factorial(4):

• factorial(4) = 4 × factorial(3) — หยุดรอ factorial(3) คำนวณเสร็จ
• factorial(3) = 3 × factorial(2) — หยุดรอ factorial(2)
• factorial(2) = 2 × factorial(1) — หยุดรอ factorial(1)
• factorial(1) = 1 — base case! เริ่มคืนค่ากลับขึ้น
• ย้อนกลับ: factorial(2) = 2 × 1 = 2
• ย้อนกลับ: factorial(3) = 3 × 2 = 6
• ย้อนกลับ: factorial(4) = 4 × 6 = 24

สังเกต: ฟังก์ชันของเราหยุดรอผลลัพธ์จาก recursive call ทุกครั้ง — กระบวนการย้อนกลับแบบนี้เรียกว่า unwind (คลี่คลาย)

Call Stack และกลไกการทำงาน

Call Stack คือ "กองงาน" ของฟังก์ชันที่กำลังทำงานอยู่ — ฟังก์ชันเรียกใหม่ก็วางกองเพิ่มด้านบน (push) ฟังก์ชันทำงานเสร็จก็ยกออกจากด้านบน (pop) ทำงานแบบ LIFO: Last In, First Out

• factorial(1) ← เรียกล่าสุด อยู่บนสุดของ stack
• factorial(2) ← เรียกก่อนหน้า รอ factorial(1) ทำงานเสร็จ
• factorial(3) ← รอ factorial(2)
• factorial(4) ← เรียกแรก อยู่ล่างสุด

เมื่อถึง base case แล้ว ระบบจะ unwind — คืนค่ากลับทีละชั้นจากบนลงล่าง จนกระทั่งฟังก์ชันแรก (ด้านล่างสุด) ได้ผลลัพธ์

ดูโค้ดทำงานทีละขั้นด้วย Code Trace

ข้อสังเกตจาก Code Trace: แต่ละครั้งที่เรียก `factorial(n - 1)` ฟังก์ชันปัจจุบันจะ "หยุดรอ" — state ของ n ในแต่ละชั้นถูกเก็บไว้ใน call stack จนกว่า recursive call จะ return ค่ากลับมา

Time & Space Complexity ของ Recursion

• Best Case: O(1) — ถึง base case ทันที (เช่นเรียก factorial(1) โดยตรง)
• Average Case: O(n) — ต้องเรียกซ้ำประมาณ n ครั้งก่อนถึง base case
• Worst Case: O(n) — ความลึกของการเรียกซ้ำแปรผันตามขนาด input โดยตรง

Space Complexity = O(n) — ฟังก์ชัน recursive แต่ละครั้งสร้าง frame ใหม่บน call stack — factorial(1000) ต้องซ้อน stack 1,000 ชั้น! นี่คือข้อเสียใหญ่ที่สุดของ recursion

ข้อดีของ Recursion

• โค้ดกระชับและอ่านตามนิยามปัญหาได้ง่าย — โดยเฉพาะปัญหาแบบแบ่งย่อย (divide and conquer)
• เหมาะกับโครงสร้างข้อมูลแบบต้นไม้หรือกราฟ — การ traverse เป็น recursive โดยธรรมชาติ
• ช่วยให้คิดปัญหาแบบ top-down ได้เป็นระบบ — โฟกัสที่ "ปัญหาใหญ่" และ "ปัญหาย่อย"
• บางอัลกอริทึมเขียนแบบ iteration ได้ยากมาก — เช่น DFS, backtracking, tower of Hanoi

ข้อควรระวังและความผิดพลาดที่พบบ่อย

กฎสำคัญที่ต้องจำ

ทบทวนความเข้าใจ

แบบฝึกหัด: ฝึกเขียน Recursion

แบบฝึกหัด 3 ข้อนี้จะช่วยให้คุณเขียน Recursion ได้คล่อง — เริ่มจาก countdown คืนอาเรย์ ไปจนถึง sumTo และหาค่าสูงสุดในอาเรย์