310-112 · Algorithms & Basic Programming · หน่วยที่ 6

RECURSIONเรียกตัวเอง

ฟังก์ชันที่เรียกใช้ตัวเอง — ฟังดูงงแต่จริงๆ ง่ายมาก · หน้านี้ทำมาเพื่อคนที่ไม่เคยเขียนโปรแกรมมาก่อน เริ่มจากศูนย์ ค่อยๆ ไป มีภาพให้ดูทุกขั้น แล้วมีควิซให้ลองตอบเช็คว่าเข้าใจจริงไหม

SOURCE Recursion.pdf — Factorial + Fibonacci + Call Stack เหมาะกับ คนไม่มีพื้นฐาน
01

Recursion คืออะไร — เริ่มจากศูนย์

ยังไม่ต้องดูโค้ด · เข้าใจแนวคิดก่อน

ก่อนอื่น — ฟังก์ชันคืออะไร?
  • ฟังก์ชัน = กล่องงานที่เราตั้งชื่อไว้ · ใส่อะไรเข้าไป แล้วมันคืนอะไรกลับมา
  • เหมือนเครื่องปั่นน้ำ — ใส่ผลไม้เข้าไป (input) ได้น้ำผลไม้ออกมา (output)
  • ปกติฟังก์ชัน A เรียกฟังก์ชัน B ได้ · Recursion คือฟังก์ชัน A เรียก A เอง — แค่นั้นเลย
นึกภาพง่ายๆ 3 แบบ
🪆
ตุ๊กตาแม่ลูกดก
เปิดตัวใหญ่ เจอตัวเล็กข้างใน · เปิดตัวเล็ก เจอตัวเล็กกว่า · ทำแบบเดิมซ้ำๆ จนเจอตัวเล็กสุดที่เปิดไม่ได้แล้ว = จุดหยุด
🧍🧍🧍
ถามคนข้างหน้าในแถว
อยากรู้ว่าตัวเองยืนอันดับที่เท่าไหร่ → ถามคนข้างหน้าว่า "คุณอันดับเท่าไหร่" แล้ว +1
คนข้างหน้าก็ถามคนถัดไปอีก จนถึงคนหน้าสุดที่ตอบได้เลยว่า "ฉันที่ 1"
🪞
กระจกส่องกระจก
เห็นภาพซ้อนกันไปไม่รู้จบ — นี่คือ recursion ที่ไม่มีจุดหยุด = สิ่งที่เราต้องระวัง
ภาพรวมทั้งหมดของ recursion — ดูอันนี้อันเดียวเข้าใจ 80%
งานใหญ่ (n = 4)
เล็กลง (n = 3)
เล็กลงอีก (n = 2)
เล็กสุด (n = 1) ★
⬇ ช่วงที่ 1 — เรียกลงไป
ปัญหายังใหญ่อยู่ ตอบไม่ได้ → ส่งต่อให้ตัวเองที่เล็กลง แล้วค้างรอไว้ ★ ชน Base Case แล้ว!
เล็กสุดแล้ว ตอบได้เลยทันที ไม่ต้องส่งต่อใครอีก → เริ่มเดินทางกลับ ⬆ ช่วงที่ 2 — คืนค่ากลับ
ค่าเดินทางกลับขึ้นไปทีละชั้น แต่ละชั้นเอาไปคำนวณต่อ จนถึงชั้นบนสุด = คำตอบ
ขาลง — ยังตอบไม่ได้ ค้างรอ ขากลับ — ได้ค่าแล้ว ส่งขึ้น
recursion มี 2 ช่วงเสมอ — คนส่วนใหญ่งงเพราะนึกออกแค่ช่วงแรก แล้วลืมว่ามันต้องเดินทางกลับด้วย
นิยามจากเอกสาร
  • กระบวนการที่ฟังก์ชัน "เรียกใช้งานตัวเอง" ซ้ำไปเรื่อยๆ เพื่อแก้ปัญหา
  • แต่ละรอบต้อง ลดขนาดของปัญหาลง จนถึงจุดที่เล็กที่สุดซึ่งตอบได้ทันที
  • ข้อดี: โค้ดที่ซับซ้อนดูสะอาดตาและสั้นลง
02

2 ส่วนที่ขาดไม่ได้

ขาดอันใดอันหนึ่ง = โปรแกรมพัง · จำแค่ 2 คำนี้ก็เขียนได้แล้ว

① Base Case — จุดหยุดพัก
  • เงื่อนไขที่บอกให้ฟังก์ชัน หยุดเรียกตัวเอง
  • คือกรณีที่ ง่ายจนตอบได้เลย ไม่ต้องคิดต่อ
  • เช่น if (n == 1) return 1; — รู้เลยว่า 1! = 1
  • ไม่มี Base Case = เรียกตัวเองไม่รู้จบ → Infinite Loop โปรแกรมค้าง/แครช
② Recursive Step — ขั้นเวียนเกิด
  • ส่วนที่ฟังก์ชัน เรียกใช้ตัวเอง
  • แต่ต้องส่งค่า ที่เล็กลง เข้าไป — เพื่อวิ่งเข้าหา Base Case
  • เช่น factorial(n - 1) — ส่ง n ที่ลดลงทีละ 1
  • ถ้าส่ง factorial(n) เท่าเดิม = ไม่มีวันถึงจุดหยุด พังเหมือนกัน
ถ้าลืม Base Case จะเป็นแบบนี้
เรียกตัวเอง...
เรียกตัวเอง...
เรียกตัวเอง...
เรียกตัวเอง...
เรียกตัวเอง...
เรียกตัวเอง...
💥 STACK OVERFLOW
  • ไม่มีจุดหยุด → เรียกตัวเองไม่รู้จบ
  • แต่ละครั้งกินหน่วยความจำเพิ่ม (สแตกซ้อนสูงขึ้น)
  • สุดท้ายหน่วยความจำเต็ม → โปรแกรมแครช
  • คอมไพเลอร์ไม่ฟ้อง เพราะโค้ดถูกไวยากรณ์ — พังตอนรันเท่านั้น
◈ ท่องไว้ — สูตรสำเร็จของทุกฟังก์ชัน recursive
ฟังก์ชัน(ปัญหา) {
    ถ้า ปัญหาเล็กพอแล้ว → ตอบเลย            ← Base Case
    ไม่งั้น → เรียกตัวเองด้วย ปัญหาที่เล็กลง   ← Recursive Step
}
เขียนฟังก์ชัน recursive อะไรก็ได้ ให้เริ่มจากถามตัวเอง 2 ข้อ:
1. เคสไหนที่ง่ายจนตอบได้เลย? (= Base Case)
2. จะทำให้ปัญหาเล็กลงยังไง? (= Recursive Step)
03

เขียนโค้ดทีละบรรทัด

สร้างฟังก์ชัน factorial จากศูนย์ · กด ▶ เพื่อเพิ่มทีละบรรทัด พร้อมคำอธิบายว่าบรรทัดนั้นทำอะไร

โจทย์ที่จะเขียน — Factorial
5! (อ่านว่า "ห้าแฟกทอเรียล") = 5 × 4 × 3 × 2 × 1 = 120
สังเกต: 5! = 5 × 4! · 4! = 4 × 3! · … ปัญหาใหญ่ประกอบด้วยปัญหาเดิมที่เล็กลง ← นี่แหละเหตุผลที่ใช้ recursion ได้

lab 03 · ต่อโค้ดทีละบรรทัด

← → เปลี่ยนบรรทัดได้
04

★ ดูการซ้อนกัน — Call Stack

ส่วนที่คนงงมากที่สุด · ดูทีละ step แล้วจะเห็นว่ามันซ้อนลงไปก่อน แล้วค่อยคลายกลับขึ้นมา

  • เมื่อสั่ง factorial(5) คอมพิวเตอร์ ยังไม่ให้คำตอบทันที
  • มันจะสร้าง "คิวงาน" ซ้อนทับกัน เรียกว่า Call Stack — เหมือนกองจานที่วางทับกัน (ตรงกับหน่วยที่ 5 เรื่อง Stack เป๊ะ)
  • ทุกครั้งที่เรียกตัวเอง = วางจานใบใหม่ทับลงไป · งานเก่าค้างรออยู่ข้างล่าง
  • พอถึง Base Case = หยุดวาง แล้วเริ่มคืนค่ากลับขึ้นไปทีละใบ (เรียกว่า Unwinding)

lab 04 · factorial(n) — ดูสแตกซ้อนแล้วคลาย

ลองเปลี่ยน n ได้
แนะนำ n = 3–6 จะดูง่ายสุด
05

เมื่อเรียกตัวเอง 2 ครั้ง — Fibonacci แตกกิ่ง

factorial เรียกตัวเอง 1 ครั้ง → เป็นเส้นตรง · fibonacci เรียก 2 ครั้ง → แตกเป็นกิ่งไม้

  • ลำดับฟีโบนัชชี: 0, 1, 1, 2, 3, 5, 8, 13… — แต่ละตัว = ผลบวกของ 2 ตัวก่อนหน้า
  • Base Case มี 2 อัน: fib(0) = 0 และ fib(1) = 1
  • Recursive Step: fib(n) = fib(n-1) + fib(n-2) ← เรียกตัวเอง 2 ครั้งในรอบเดียว
  • ผลคืองานซ้ำเยอะมาก — fib(2) ถูกคำนวณหลายรอบ ยิ่ง n ใหญ่ยิ่งช้าแบบทวีคูณ
int fibonacci(int n) {
    // 1. Base Case
    if (n == 0) return 0;
    else if (n == 1) return 1;
    // 2. Recursive Step
    else return fibonacci(n - 1) + fibonacci(n - 2);
}

lab 05 · fibonacci(n) — ดูต้นไม้แตกกิ่ง

สีเหลือง = Base Case
n = 4 กำลังดี · n = 6 เริ่มเห็นว่างานซ้ำเยอะแค่ไหน
06

ควิซเช็คความเข้าใจ

มีทั้งแบบเลือกตอบ, แบบทายผลลัพธ์, และแบบให้ลองอธิบายด้วยคำพูดตัวเอง — ตอบผิดไม่เป็นไร มีเฉลยอธิบายให้ทุกข้อ

07

โหมดนำเสนอ — เช็คชื่อ + สุ่มคนตอบ

สำหรับตอนขึ้นนำเสนอหน้าชั้น · ใส่รายชื่อครั้งเดียว เครื่องจำไว้ให้ (เปิดใหม่ก็ยังอยู่)

เช็คชื่อ

คลิกที่ชื่อ = สลับ มา / ไม่มา
ยังไม่มีรายชื่อ

สุ่มคนตอบคำถาม

สุ่มเฉพาะคนที่มาเท่านั้น
— กด 🎲 เพื่อเริ่ม —
ประวัติการสุ่ม
— ยังไม่มี —
✦

แผ่นโกง

ทวนก่อนสอบ / ก่อนขึ้นนำเสนอ

RECURSION คือ
ฟังก์ชันเรียกใช้ตัวเอง โดยลดขนาดปัญหาลงทุกรอบ
BASE CASE
จุดหยุด — เคสที่ตอบได้เลย ไม่ต้องเรียกตัวเองต่อ
RECURSIVE STEP
เรียกตัวเองด้วยค่าที่เล็กลง เพื่อวิ่งเข้าหา Base Case
ขาด BASE CASE
Infinite Loop → Stack Overflow โปรแกรมแครช
CALL STACK
กองงานที่ซ้อนทับกัน — เรียกลงไปเรื่อยๆ แล้วคืนค่ากลับขึ้นมา
UNWINDING
ช่วงคืนค่ากลับขึ้นไป หลังชน Base Case แล้ว
FACTORIAL
if(n==1) return 1; else return n * factorial(n-1);
FIBONACCI
if(n==0) return 0; if(n==1) return 1;
else return fib(n-1) + fib(n-2);
เรียก 1 ครั้ง / 2 ครั้ง
1 ครั้ง = เส้นตรง · 2 ครั้ง = แตกกิ่ง งานซ้ำเยอะ
เขียนเองยังไง
ถาม 2 ข้อ: เคสไหนตอบได้เลย? · ทำให้เล็กลงยังไง?