Iteration & Recursion

ความต่างหลักระหว่าง Iteration และ Recursion

Iteration และ Recursion เป็นสองวิธีคิดในการแก้ปัญหาแบบทำซ้ำ — ต่างกันที่ "ควบคุมการวนซ้ำอย่างไร" และ "จัดการ state ไว้ที่ไหน"

เปรียบเทียบผ่านโจทย์เดียวกัน: factorial(n)

ใช้โจทย์ factorial(n) เป็นตัวเปรียบเทียบ — ทั้งสองแบบให้ผลลัพธ์เท่ากัน แต่แนวคิดและกลไกภายในต่างกันอย่างสิ้นเชิง

// Iteration: ใช้ for loop คูณสะสมทีละรอบ
function factorialIteration(n) {
  let result = 1;

  for (let i = 2; i <= n; i += 1) {
    result *= i;
  }

  return result;
}

// Recursion: เรียกตัวเองด้วย n-1 จนถึง base case
function factorialRecursion(n) {
  if (n <= 1) {
    return 1;
  }

  return n * factorialRecursion(n - 1);
}

ทั้งสองแบบใช้ Time O(n) เท่ากัน — แต่ Recursion ใช้ Space O(n) ในขณะที่ Iteration ใช้แค่ O(1)

Loop State vs Call Stack — เห็นภาพการทำงาน

เวลาทำงาน Iteration กับการ Recursion — สิ่งที่เกิดขึ้นเบื้องหลังต่างกันโดยสิ้นเชิง

Iteration (Loop State): ตัวแปร result ถูกอัปเดตทับค่าเดิมไปเรื่อย ๆ — แต่ละรอบมีแค่ result ตัวเดียว

• รอบที่ 1: i = 2, result = 2
• รอบที่ 2: i = 3, result = 6
• รอบที่ 3: i = 4, result = 24
• รอบที่ 4: i = 5, result = 120

Recursion (Call Stack): แต่ละครั้งที่เรียกตัวเอง จะสร้าง frame ใหม่บน stack — ถ้าเรียก factorial(5) จะมี 5 frames ซ้อนกัน

• factorial(5) — เรียก factorial(4) และรอ
• factorial(4) — เรียก factorial(3) และรอ
• factorial(3) — เรียก factorial(2) และรอ
• factorial(2) — เรียก factorial(1) และรอ
• factorial(1) → base case! เริ่มคืนค่ากลับขึ้น

Time Complexity เทียบกัน

สำหรับปัญหาที่ต้องทำงาน n ครั้ง (เช่น factorial, sum, findMax) — ทั้ง Iteration และ Recursion ต่างก็ต้องทำงานประมาณ n ขั้นตอนเหมือนกัน จึงมี Time Complexity = O(n) เท่ากัน

แต่ในทางปฏิบัติ Iteration มักมี overhead น้อยกว่า — เพราะไม่ต้อง push/pop stack ทุกครั้งที่เรียกฟังก์ชัน ส่วน Recursion มีค่าใช้จ่ายแฝงจากการจัดการ call stack (function call overhead)

Space Complexity เทียบกัน — จุดแตกต่างใหญ่ที่สุด

นี่คือข้อแตกต่างที่สำคัญที่สุดระหว่าง Iteration และ Recursion — การใช้หน่วยความจำ

Iteration ใช้ Space O(1) — ตัวแปรแค่ไม่กี่ตัวใน scope เดียว ไม่เพิ่มชั้นการเรียกใหม่ ไม่ว่าจะวนกี่รอบก็ตาม

Recursion ใช้ Space O(n) — ทุกครั้งที่เรียกตัวเอง จะเพิ่ม frame ใหม่บน call stack — ถ้า n = 10,000 จะมี 10,000 frames ซึ่งอาจทำให้เกิด Stack Overflow ได้

เลือกใช้อย่างไรในทางปฏิบัติ

• ถ้าโจทย์เดินข้อมูลแบบเส้นตรงและต้องการประหยัด memory → เลือก Iteration
• ถ้าโจทย์มีโครงสร้างแบบต้นไม้ (tree), กราฟ, หรือ backtracking → Recursion มักเขียนง่ายกว่าและอ่านเข้าใจกว่า
• ถ้าความลึกของการเรียกมีโอกาสสูงมาก (n > 10,000) → เลือก Iteration หรือใช้ tail-call optimization (ถ้า engine รองรับ)
• ถ้าต้องการโค้ดที่กระชับและตรงกับนิยามทางคณิตศาสตร์ → Recursion (เช่น factorial, Fibonacci)
• ถ้าทีมไม่คุ้นเคยกับ recursion → เริ่มที่ Iteration ก่อนเพื่อลดความสับสนในการ debug

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

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

แบบฝึกหัด: สลับเขียนทั้งสองแบบ

2 ข้อนี้จะให้คุณเขียนฟังก์ชันเดียวกันด้วยทั้ง Iteration และ Recursion — เพื่อสัมผัสความต่างของแนวคิดทั้งสองโดยตรง

สรุปท้ายบท — จำง่ายในหนึ่งลมหายใจ

• Iteration = วนลูปใน scope เดียว ใช้ตัวแปรเดิมอัปเดต → Space O(1)
• Recursion = เรียกตัวเองด้วยปัญหาที่เล็กลง เก็บ state ใน call stack → Space O(n)
• Time Complexity เท่ากันในโจทย์เส้นตรง — เลือกตาม Readability และ Space
• Recursion เหมาะกับโครงสร้างแบบต้นไม้ กราฟ และ Divide & Conquer
• Iteration เหมาะกับงานปริมาณมากที่ต้องการประหยัด memory
• ไม่ต้องเลือกข้าง — ใช้ทั้งสองแบบตามสถานการณ์ของแต่ละฟีเจอร์