พื้นฐานบทที่ 4พื้นฐาน Recursion

Recursion พื้นฐาน: เข้าใจจากศูนย์แบบทีละขั้น

บทนี้ออกแบบสำหรับผู้เริ่มต้น โดยเริ่มจากภาพรวมก่อน แล้วค่อยลงรายละเอียด base case, recursive case, call stack, การคืนค่าทีละชั้น พร้อมตัวอย่างโค้ด JavaScript และแบบฝึกหัดพร้อมแนวเฉลย

1. Recursion คืออะไร

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

มองแบบง่าย ๆ: "ย่อยปัญหาใหญ่ให้เล็กลงเรื่อย ๆ จนแก้ได้ทันที"

2. แนวคิดของฟังก์ชันที่เรียกตัวเอง

ฟังก์ชัน recursion มักมีแนวคิดหลัก 2 ส่วน: ส่วนที่หยุด (base case) และส่วนที่เรียกซ้ำ (recursive case) โดย recursive case ต้องส่งปัญหาที่เล็กลงให้ตัวเองเสมอ

3. Base case คืออะไร

Base case คือเงื่อนไขหยุด recursion เมื่อถึงกรณีที่แก้ได้ทันทีโดยไม่ต้องเรียกซ้ำต่อ

4. Recursive case คืออะไร

Recursive case คือส่วนที่เรียกฟังก์ชันเดิมอีกครั้ง โดยใช้ข้อมูลที่เล็กลงหรือเข้าใกล้ base case มากขึ้น

5. ทำไม recursion ต้องมี base case

ถ้าไม่มี base case ฟังก์ชันจะเรียกตัวเองต่อไปเรื่อย ๆ แบบไม่สิ้นสุด จนหน่วยความจำ call stack เต็มและโปรแกรมพัง

6. ตัวอย่างง่าย ๆ: countdown

JavaScript: countdown(n)JS

ตัวอย่าง recursion ที่เห็น base case และ recursive case ชัดที่สุด

function countdown(n) {
  // Base case: ถึง 0 แล้วให้หยุด recursion
  if (n === 0) {
    console.log("จบการนับถอยหลัง");
    return;
  }

  console.log(n);

  // Recursive case: เรียกตัวเองด้วยปัญหาที่เล็กลง (n - 1)
  countdown(n - 1);
}

countdown(3);

7. ตัวอย่าง factorial

JavaScript: factorial(n)JS

นิยามมาตรฐานของ factorial ด้วย recursion

function factorial(n) {
  // Base case: 0! = 1 และ 1! = 1
  if (n <= 1) {
    return 1;
  }

  // Recursive case: n! = n * (n - 1)!
  return n * factorial(n - 1);
}

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

8. อธิบายการทำงานทีละ step

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

เรียก countdown(3)
พิมพ์ 3 แล้วเรียก countdown(2)
พิมพ์ 2 แล้วเรียก countdown(1)
พิมพ์ 1 แล้วเรียก countdown(0)
เจอ base case ที่ n === 0 แล้วหยุด

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

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 (base case)
ย้อนกลับ: factorial(2) = 2 * 1 = 2
ย้อนกลับ: factorial(3) = 3 * 2 = 6
ย้อนกลับ: factorial(4) = 4 * 6 = 24

9. อธิบาย call stack แบบเข้าใจง่าย

Call stack คือ "กองงาน" ของฟังก์ชันที่กำลังทำอยู่ เรียกใหม่ก็วางกองเพิ่มด้านบน พอเสร็จก็ยกออกจากด้านบนก่อน (LIFO: เข้าทีหลังออกก่อน)

ภาพการเรียกฟังก์ชันซ้อนกันใน call stack

ตัวอย่างตอนกำลังคำนวณ factorial(4)

factorial(1)

factorial(2)

factorial(3)

factorial(4)

ด้านบนคือ call ล่าสุด และเมื่อเจอ base case จะค่อย ๆ คืนค่าลงกลับทีละชั้น

10. แสดงลำดับการเรียกซ้อนและการคืนค่ากลับ

ภาพ base case และการคืนค่ากลับ (unwind)

ชั้น 1:factorial(1)1 (base case)

ชั้น 2:factorial(2)2 * 1 = 2

ชั้น 3:factorial(3)3 * 2 = 6

ชั้น 4:factorial(4)4 * 6 = 24

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

จุดสำคัญใน countdown

- `if (n === 0)` คือ base case
- `countdown(n - 1)` คือ recursive case
- ต้องลด n ลงเรื่อย ๆ เพื่อเข้าใกล้ base case

จุดสำคัญใน factorial

- `if (n <= 1) return 1` คือ base case
- `return n * factorial(n - 1)` คือ recursive case
- ผลลัพธ์จริงจะได้ตอน unwind กลับจากชั้นลึกสุด

12. ข้อดีของ recursion

- โค้ดกระชับและอ่านตามนิยามปัญหาได้ง่าย โดยเฉพาะปัญหาแบบแบ่งย่อย
- เหมาะกับโครงสร้างข้อมูลแบบต้นไม้หรือปัญหาที่มีรูปแบบซ้ำกัน
- ช่วยให้คิดปัญหาแบบ top-down ได้เป็นระบบ

13. ข้อเสียของ recursion

- ใช้หน่วยความจำเพิ่มจาก call stack ทุกครั้งที่เรียกซ้อน
- ถ้าลึกมากอาจเกิด stack overflow
- บางโจทย์เวอร์ชัน loop อ่านง่ายหรือเร็วกว่า

14. ปัญหาที่อาจเกิด เช่น stack overflow

ถ้าลึกเกินไปหรือไม่มี base case ที่ถูกต้อง call stack จะโตจนเต็มและเกิด stack overflow

วิธีลดความเสี่ยง: ออกแบบ base case ให้ชัด, ลดความลึก, หรือเปลี่ยนเป็น iteration เมื่อเหมาะสม

15. กรณีที่ recursion เหมาะสม

- ปัญหาแบบแบ่งย่อยซ้ำรูปแบบเดิม (Divide and Conquer)
- โครงสร้างข้อมูลแบบต้นไม้ เช่น DFS traversal
- ปัญหา backtracking ที่ต้องลองทางเลือกและย้อนกลับ

16. สรุปท้ายบทแบบจำง่าย

- Recursion = ฟังก์ชันเรียกตัวเองด้วยปัญหาที่เล็กลง
- ต้องมี base case เสมอ ไม่งั้นไม่หยุด
- Recursive case ต้องพาเข้าใกล้ base case
- Call stack จะเก็บการเรียกซ้อน และคืนค่ากลับทีละชั้น

17. แบบฝึกหัด 4 ข้อ ใช้ Playground พร้อม expected output

โจทย์ 1: countdown(n)

คืนอาเรย์ลำดับนับถอยหลังจาก n ถึง 0 ด้วย recursion (ห้ามใช้ console เป็นผลลัพธ์หลัก)

Expected Output

ตัวอย่าง: countdown(3) -> [3, 2, 1, 0]

โจทย์ 2: factorial(n)

คืนค่าแฟกทอเรียลด้วย recursion โดยกำหนดรับ n >= 0 และเคสติดลบต้องจัดการอย่างปลอดภัย

Expected Output

ตัวอย่าง: factorial(5) -> 120, factorial(0) -> 1

โจทย์ 3: sumTo(n)

คืนผลรวมตั้งแต่ 1 ถึง n ด้วย recursion และถ้า n <= 0 ให้คืน 0

Expected Output

ตัวอย่าง: sumTo(5) -> 15, sumTo(-3) -> 0

โจทย์ 4: findMaxRecursive(values)

หาเลขมากสุดในอาเรย์ด้วย recursion และถ้าอาเรย์ว่างให้คืน undefined

Expected Output

ตัวอย่าง: findMaxRecursive([3, 9, 2, 7]) -> 9

เช็กข้อผิดพลาดที่พบบ่อยก่อนส่งงาน recursion:

- ลืมเขียน base case ทำให้เรียกไม่สิ้นสุด
- เขียน base case ผิดเงื่อนไข เช่น n < 0 ทั้งที่ควรหยุดที่ n === 0
- recursive case ไม่ลดขนาดปัญหา เช่น เรียก recursion ด้วยค่าเดิม
- สับสนลำดับการคำนวณตอน unwind ทำให้ผลลัพธ์ผิด

ไปทำ Recursion Lab

พื้นฐานบทที่ 4พื้นฐาน Recursion

Recursion พื้นฐาน: เข้าใจจากศูนย์แบบทีละขั้น

1. Recursion คืออะไร

มองแบบง่าย ๆ: "ย่อยปัญหาใหญ่ให้เล็กลงเรื่อย ๆ จนแก้ได้ทันที"

2. แนวคิดของฟังก์ชันที่เรียกตัวเอง

3. Base case คืออะไร

4. Recursive case คืออะไร

5. ทำไม recursion ต้องมี base case

6. ตัวอย่างง่าย ๆ: countdown

JavaScript: countdown(n)JS

ตัวอย่าง recursion ที่เห็น base case และ recursive case ชัดที่สุด

function countdown(n) {
  // Base case: ถึง 0 แล้วให้หยุด recursion
  if (n === 0) {
    console.log("จบการนับถอยหลัง");
    return;
  }

  console.log(n);

  // Recursive case: เรียกตัวเองด้วยปัญหาที่เล็กลง (n - 1)
  countdown(n - 1);
}

countdown(3);

7. ตัวอย่าง factorial

JavaScript: factorial(n)JS

นิยามมาตรฐานของ factorial ด้วย recursion

function factorial(n) {
  // Base case: 0! = 1 และ 1! = 1
  if (n <= 1) {
    return 1;
  }

  // Recursive case: n! = n * (n - 1)!
  return n * factorial(n - 1);
}

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

8. อธิบายการทำงานทีละ step

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

เรียก countdown(3)
พิมพ์ 3 แล้วเรียก countdown(2)
พิมพ์ 2 แล้วเรียก countdown(1)
พิมพ์ 1 แล้วเรียก countdown(0)
เจอ base case ที่ n === 0 แล้วหยุด

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

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 (base case)
ย้อนกลับ: factorial(2) = 2 * 1 = 2
ย้อนกลับ: factorial(3) = 3 * 2 = 6
ย้อนกลับ: factorial(4) = 4 * 6 = 24

9. อธิบาย call stack แบบเข้าใจง่าย

ภาพการเรียกฟังก์ชันซ้อนกันใน call stack

ตัวอย่างตอนกำลังคำนวณ factorial(4)

factorial(1)

factorial(2)

factorial(3)

factorial(4)

ด้านบนคือ call ล่าสุด และเมื่อเจอ base case จะค่อย ๆ คืนค่าลงกลับทีละชั้น

10. แสดงลำดับการเรียกซ้อนและการคืนค่ากลับ

ภาพ base case และการคืนค่ากลับ (unwind)

ชั้น 1:factorial(1)1 (base case)

ชั้น 2:factorial(2)2 * 1 = 2

ชั้น 3:factorial(3)3 * 2 = 6

ชั้น 4:factorial(4)4 * 6 = 24

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

จุดสำคัญใน countdown

- `if (n === 0)` คือ base case
- `countdown(n - 1)` คือ recursive case
- ต้องลด n ลงเรื่อย ๆ เพื่อเข้าใกล้ base case

จุดสำคัญใน factorial

- `if (n <= 1) return 1` คือ base case
- `return n * factorial(n - 1)` คือ recursive case
- ผลลัพธ์จริงจะได้ตอน unwind กลับจากชั้นลึกสุด

12. ข้อดีของ recursion

- โค้ดกระชับและอ่านตามนิยามปัญหาได้ง่าย โดยเฉพาะปัญหาแบบแบ่งย่อย
- เหมาะกับโครงสร้างข้อมูลแบบต้นไม้หรือปัญหาที่มีรูปแบบซ้ำกัน
- ช่วยให้คิดปัญหาแบบ top-down ได้เป็นระบบ

13. ข้อเสียของ recursion

- ใช้หน่วยความจำเพิ่มจาก call stack ทุกครั้งที่เรียกซ้อน
- ถ้าลึกมากอาจเกิด stack overflow
- บางโจทย์เวอร์ชัน loop อ่านง่ายหรือเร็วกว่า

14. ปัญหาที่อาจเกิด เช่น stack overflow

ถ้าลึกเกินไปหรือไม่มี base case ที่ถูกต้อง call stack จะโตจนเต็มและเกิด stack overflow

15. กรณีที่ recursion เหมาะสม

- ปัญหาแบบแบ่งย่อยซ้ำรูปแบบเดิม (Divide and Conquer)
- โครงสร้างข้อมูลแบบต้นไม้ เช่น DFS traversal
- ปัญหา backtracking ที่ต้องลองทางเลือกและย้อนกลับ

16. สรุปท้ายบทแบบจำง่าย

- Recursion = ฟังก์ชันเรียกตัวเองด้วยปัญหาที่เล็กลง
- ต้องมี base case เสมอ ไม่งั้นไม่หยุด
- Recursive case ต้องพาเข้าใกล้ base case
- Call stack จะเก็บการเรียกซ้อน และคืนค่ากลับทีละชั้น

17. แบบฝึกหัด 4 ข้อ ใช้ Playground พร้อม expected output

โจทย์ 1: countdown(n)

คืนอาเรย์ลำดับนับถอยหลังจาก n ถึง 0 ด้วย recursion (ห้ามใช้ console เป็นผลลัพธ์หลัก)

Expected Output

ตัวอย่าง: countdown(3) -> [3, 2, 1, 0]

โจทย์ 2: factorial(n)

Expected Output

ตัวอย่าง: factorial(5) -> 120, factorial(0) -> 1

โจทย์ 3: sumTo(n)

คืนผลรวมตั้งแต่ 1 ถึง n ด้วย recursion และถ้า n <= 0 ให้คืน 0

Expected Output

ตัวอย่าง: sumTo(5) -> 15, sumTo(-3) -> 0

โจทย์ 4: findMaxRecursive(values)

หาเลขมากสุดในอาเรย์ด้วย recursion และถ้าอาเรย์ว่างให้คืน undefined

Expected Output

ตัวอย่าง: findMaxRecursive([3, 9, 2, 7]) -> 9

เช็กข้อผิดพลาดที่พบบ่อยก่อนส่งงาน recursion:

- ลืมเขียน base case ทำให้เรียกไม่สิ้นสุด
- เขียน base case ผิดเงื่อนไข เช่น n < 0 ทั้งที่ควรหยุดที่ n === 0
- recursive case ไม่ลดขนาดปัญหา เช่น เรียก recursion ด้วยค่าเดิม
- สับสนลำดับการคำนวณตอน unwind ทำให้ผลลัพธ์ผิด

ไปทำ Recursion Lab

Data Structures & Algorithms

Recursion พื้นฐาน: เข้าใจจากศูนย์แบบทีละขั้น

1. Recursion คืออะไร

2. แนวคิดของฟังก์ชันที่เรียกตัวเอง

3. Base case คืออะไร

4. Recursive case คืออะไร

5. ทำไม recursion ต้องมี base case

6. ตัวอย่างง่าย ๆ: countdown

7. ตัวอย่าง factorial

8. อธิบายการทำงานทีละ step

9. อธิบาย call stack แบบเข้าใจง่าย

10. แสดงลำดับการเรียกซ้อนและการคืนค่ากลับ

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

12. ข้อดีของ recursion

13. ข้อเสียของ recursion

14. ปัญหาที่อาจเกิด เช่น stack overflow

15. กรณีที่ recursion เหมาะสม

16. สรุปท้ายบทแบบจำง่าย

17. แบบฝึกหัด 4 ข้อ ใช้ Playground พร้อม expected output

Loading

Data Structures & Algorithms

Recursion พื้นฐาน: เข้าใจจากศูนย์แบบทีละขั้น

1. Recursion คืออะไร

2. แนวคิดของฟังก์ชันที่เรียกตัวเอง

3. Base case คืออะไร

4. Recursive case คืออะไร

5. ทำไม recursion ต้องมี base case

6. ตัวอย่างง่าย ๆ: countdown

7. ตัวอย่าง factorial

8. อธิบายการทำงานทีละ step

9. อธิบาย call stack แบบเข้าใจง่าย

10. แสดงลำดับการเรียกซ้อนและการคืนค่ากลับ

11. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

12. ข้อดีของ recursion

13. ข้อเสียของ recursion

14. ปัญหาที่อาจเกิด เช่น stack overflow

15. กรณีที่ recursion เหมาะสม

16. สรุปท้ายบทแบบจำง่าย

17. แบบฝึกหัด 4 ข้อ ใช้ Playground พร้อม expected output