Recursion
| English | ไทย |
|---|---|
| recursive/rɪˈkɜːsɪv/ | วนซ้ำ |
| base case/beɪs keɪs/ | กรณีฐาน (Base Case) |
| recursive case/rɪˈkɜːsɪv keɪs/ | กรณีเรียกตัวเอง (Recursive Case) |
| call stack/kɔːl stæk/ | call stack memory |
| stack frame/stæk freɪm/ | stack frame |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | stack overflow error |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | memoization technique |
นิยามที่อ้างอิงถึงตัวเอง
- เราจะนิยามว่าบรรพบุรุษคืออะไรได้อย่างไร? พ่อแม่ของคุณคือบรรพบุรุษ ดังนั้นบรรพบุรุษของพ่อแม่คุณก็ถือเป็นบรรพบุรุษเช่นกัน สองประโยคนี้สร้างสายโซ่ที่ไม่จำกัดขอบเขต และประโยคหลังได้นำคำที่กำลังนิยามมาใช้อ้างอิงด้วย
- นี่ไม่ใช่การให้เหตุผลแบบวงกลม เพราะประโยคแรกกำหนดจุดหยุดของสายโซ่นั้นไว้ หากไม่มีจุดหยุดนี้ การนิยามจะวนลูปไปเรื่อยๆ โดยไม่สิ้นสุด
- โปรแกรมสามารถเขียนได้เช่นเดียวกัน และสำหรับปัญหาที่มีลักษณะเป็นสายโซ่แบบนี้ วิธีแก้แบบ recursive จะสั้นกว่าการใช้ loop อย่างมีนัยสำคัญ
- บทเรียนนี้จะกล่าวถึง base case และ recursive case, วิธีการติดตามการเรียกซ้ำ, และสิ่งที่ call stack กำลังทำงานอยู่เบื้องหลัง
สองกรณีหลัก
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- Base case คือเวอร์ชันของปัญหาที่มีขนาดเล็กพอที่จะตอบได้โดยตรงโดยไม่ต้องมีการเรียกเพิ่มเติม มันคือสิ่งที่หยุดการเรียกซ้ำ
- Recursive case จะเรียกฟังก์ชันอีกครั้งโดยส่ง อินพุต ที่ เล็กลง เข้าไป เพื่อเคลื่อนเข้าใกล้ base case
- ทั้งสองกรณีจำเป็นต่อการทำงาน การเรียกซ้ำที่ไม่มี base case จะไม่ pernahหยุด; ส่วนกรณีที่มีอินพุตไม่หดตัวลง จะไม่เคยไปถึง base case ได้
อัลกอริทึม递归ทั้งหมดต้องมี base case เพราะ:
Base case คือเงื่อนไขที่สิ้นสุด سلسلةการเรียก; หากไม่มีมัน recursion จะรันตลอดกาล
Recursion เหมาะสมกับปัญหาที่มีลักษณะซ้ำกันเอง (trees, divide-and-conquer) แต่แต่ละ call เพิ่ม stack frame — ดังนั้นหากไม่มี base case จะเกิด stack overflow
Loop นับ đơn giảnเหมาะสำหรับการ iterate ทั่วไป; Recursion โดดเด่นเมื่อปัญหามีสำเนาตัวเองขนาดเล็กอยู่ภายใน
_argv递归函数必须具备什么才能终止？选择所有适用的选项。
Base case เพียงอย่างเดียวไม่พอ: หากอินพุตไม่เคยหดตัว base_case จะไม่ถูกเข้าถึง และ frames จะสะสมจน stack overflows
ตัวอย่างฝึกปฏิบัติ: ติดตามการเรียกซ้ำ
- ติดตาม
Factorial(4). - การเรียกซ้อนกัน (Winding up):
Factorial(4)ต้องใช้4 * Factorial(3), ซึ่งต้องใช้3 * Factorial(2), ซึ่งต้องใช้2 * Factorial(1)ยังไม่ได้มีการคูณอะไรเลย; ทุกการเรียกกำลังรอคอย - Base case:
Factorial(1)คืนค่า 1 โดยไม่มีการเรียกอะไรเพิ่ม - การจบการทำงาน (Unwinding): ค่า
2 * 1 = 2ถูกส่งกลับมาก่อน ตามด้วย3 * 2 = 6, แล้วตามด้วย4 * 6 = 24 - แสดงทั้งสองทิศทาง การติดตามที่ดูเฉพาะทางลง หรือกลับมาทางเดียวเพียงอย่างเดียว จะเสียคะแนนไปครึ่งหนึ่ง
Recursion ถอดออกจากใบไม้ขึ้นด้านบน
ผ่าน fib(4) ตามลำดับที่เรียกใช้งานเสร็จจริง: ใบ (base cases) แก้ไขก่อน จากนั้นแต่ละแม่รวมลูกหลานของตน หมายเหตุ fib(2) คำนวณสองครั้ง — งานซ้ำนี้คือเหตุผลว่าทำไม naive recursion จึงช้า
Factorial(4) คืนค่าอะไร?
4 × 3 × 2 × 1 = 24.
สิ่งที่เครื่องกำลังทำ
- ทุก call ต้องมี สำเนา ของ parameters และ local variables ของมันเอง เนื่องจาก
Factorial(3)และFactorial(2)เป็น call ที่แตกต่างกันซึ่งมีค่าnที่ไม่เหมือนกัน - สำเนานี้ resides อยู่ภายใน stack frame บน call stack: มีหนึ่ง frame ต่อ call ที่กำลังดำเนินการ เก็บ parameters, locals และ return address ไว้
- Frame จะถูก push เข้าไปใน stack ทุกครั้งที่มีการ call และ pop ออกเมื่อกลับคืน นี่คือเหตุผลว่าทำไมค่าจึงกลับมาในลำดับย้อนกลับจากลำดับที่ถูกเรียก: call stack เป็น stack พอดี ตาม ADT จากหัวข้อ 10
เรียงเหตุการณ์ในการประเมิน Factorial(4) ให้เป็นลำดับ
ไม่มีอะไรถูกคูณขณะลงไป; ทุก call รออยู่ การคูณทั้งหมดเกิดขึ้นขณะที่ stack ถอดออก
สิ่งที่เกิดขึ้นผิดพลาด
- ไม่มี base case หรือ base_case ที่ไม่สามารถเข้าถึงได้: การเรียกซ้ำจะไม่หยุด Frames จะสะสมเพิ่มขึ้น และ call stack จะหมดพื้นที่จัดเก็บ ข้อมูลนี้เรียกว่า stack overflow
- Deep recursion: แม้การเรียกซ้ำที่ถูกต้องแต่มีความลึกล้านระดับก็ต้องใช้ frames ล้าน帧 ดังนั้นจึงอาจทำให้หน่วยความจำหมด ในขณะที่การใช้ loop จะไม่ใช้หน่วยความจำเสริมเลย
- งานซ้ำซ้อน: การคำนวณ Fibonacci แบบ recursive แบบง่าย (naive) จะคำนวณค่าเดิมซ้ำกันอย่างมีเลขยกกำลังหลายครั้ง แก้ไข bằng loop หรือใช้ memoisation โดยเก็บผลลัพธ์每一次ที่คำนวณครั้งแรก
จับคู่แต่ละคำศัพท์ recursion กับความหมายของมัน
A recursion ต้องการ base_case เพื่อหยุดและ recursive case เพื่อลดขนาดปัญหา; แต่ละ call เพิ่ม stack frame
A stack frame สำหรับ function call เก็บ:
เฟรมแต่ละตัวเก็บพารามิเตอร์ ตัวแปรในสโคป และตำแหน่งที่จะกลับมายังต่อของฟังก์ชันนั้น — ทำให้การเรียกใช้ไม่รบกวนกัน
การเรียกใช้ที่กำลังดำเนินการจะเก็บพารามิเตอร์และตัวแปรไว้ใน ____ ของมันเองบน Call Stack
ถูกดันเข้าไปเมื่อเรียก ใช้ และถูกดึงออกเมื่อคืนค่า นั่นคือเหตุผลที่ค่าที่กลับมาอยู่ในลำดับตรงข้ามกับการเรียกใช้
การเลือก Recursive หรือ Iteration
- Recursion เหมาะกับปัญหาที่มีลักษณะ self-similar คือปัญหาที่ประกอบด้วยส่วนย่อยที่เป็นสำเนาของตัวเอง: การ traverses tree, Divide and Conquer เช่น binary search และ merge sort, และสายโซ่บรรพบุรุษข้างต้น
- Iteration เหมาะกับทุกอย่างอื่น และใช้ หน่วยความจำเพิ่มเติม สำหรับการكرر ไม่มี
- ทุกสิ่งที่ทำด้วย recursion สามารถเขียนเป็น iteration ได้และในทางกลับกัน亦然 การตัดสินใจขึ้นอยู่กับว่า哪种表达方式แสดงปัญหาได้อย่างชัดเจน เมื่อเทียบกับต้นทุนด้านหน่วยความจำของ stack
ฟังก์ชันแบบ Recursive จะเกิด Stack Overflow ซึ่งคำอธิบายใดถูกต้อง?
Stack Overflow เกี่ยวข้องกับเฟรม ไม่ใช่การคำนวณ ตัวเลขที่มากเกิน Register คือ Arithmetic Overflow ซึ่งเป็นเรื่องคนละอย่างกัน
ตัวอย่างฝึกปฏิบัติ: ระบุความเสี่ยง
- นักเรียนเขียน routine แบบ recursive แล้วเกิด crash ด้วย stack overflow. ให้สาเหตุที่เป็นไปได้สองประการ
- ไม่มี base case, หรือ base_case ไม่สามารถเข้าถึงได้เนื่องจากอินพุตไม่ลดขนาดลงในทุก call ทำให้ calls ดำเนินต่อไปตลอดและ frames สะสมเพิ่มขึ้น
- การเรียกซ้ำถูกต้องแต่ ลึกเกินไป: ทุก call จำนวนมากยังคง stack frame ของมันเอง ทำให้ call stack หมดพื้นที่จัดเก็บ ก่อนที่จะถึง base case
- สาเหตุทั้งสองเกี่ยวข้องกับ frames ที่สะสมขึ้นมา บอกว่าอะไรสะสมขึ้นและทำไมมันจึงไม่หยุด
คะแนนที่หลุดหายไป
- การเรียกซ้ำต้องการ ทั้ง base case และอินพุตที่ลดขนาดลง การระบุแค่ base case เป็นเพียงครึ่งหนึ่งของเงื่อนไข
- ในการติดตาม (trace), แสดงการเรียกที่ m้วนขึ้น (winding up) และค่าที่ ม้วนลง (unwinding). ทั้งสองทิศทางให้คะแนน
- แต่ละ call มี parameters และ locals ของมันเอง อยู่ใน stack frame ของมันเอง นี่คือเหตุผลว่าทำไม recursion จึงใช้หน่วยความจำในขณะที่ iteration ไม่ได้
- Stack overflow คือการหมดพื้นที่จัดเก็บของ stack จาก frames ที่มากเกินไป ไม่ใช่ arithmetic overflow
คุณเข้าใจแล้ว
- routine แบบ recursive ต้องการ base case ที่แก้ได้โดยตรงและ recursive case ที่เรียกตัวเองด้วย อินพุต ที่ เล็กลง
- ติดตามในทั้งสองทิศทาง: การเรียก m้วนขึ้นสู่ base case แล้วค่าจะม้วนลงกลับมา
- แต่ละ call มี stack frame ของมันเองบน call stack, ถูก push เข้าเมื่อมีการ call และ pop ออกเมื่อกลับคืน นี่คือเหตุผลว่าทำไม recursion จึงใช้หน่วยความจำ
- ความเสี่ยง: หากไม่มีกรณีฐานที่เข้าถึงได้จะนำไปสู่การเรียกซ้ำแบบไม่มีที่สิ้นสุดและ Stack overflow การเรียกซ้ำที่ลึกเกินไปจะใช้หน่วยความจำหมด และการทำงานซ้ำซ้อนควรใช้ลูปหรือ Memoisation