Recursion
แนะนำใหม่| English | ความหมาย |
|---|---|
| Recursion/rɪˈkɜːʃn/ | การเรียกซ้ำ |
| base case/beɪs keɪs/ | กรณีฐาน |
| recursive case/rɪˈkɜːsɪv keɪs/ | กรณีเรียกซ้ำ |
| unwind/ʌnˈwaɪnd/ | ถอยกลับ |
A method that calls itself
- Recursion คือเมื่อ method เรียกตัวเอง เพื่อแก้ปัญหาเวอร์ชันที่เล็กลงของปัญหาเดิม
- Every recursion ต้องมีสองส่วน: base case และ recursive case
- Base case หยุด recursion — input เล็กที่ method ตอบได้โดยตรง
- Recursive case เรียก method อีกครั้งบน input ที่เล็กลง
The base case
- หากไม่มีกรณีฐาน ฟังก์ชันจะเรียกตัวเองซ้ำ ตลอดกาล — ซึ่งเรียกว่า
StackOverflowError - Base case จัดการ input ที่เล็กที่สุด โดยไม่มีการ call อื่น
- Example:
factorial(0)returns1directly — no more calls. - ตรวจสอบเสมอ: ทุกเส้นทางจะไปถึง base case ในที่สุดหรือไม่?
กรณีแบบเรียกซ้ำ
- กรณีแบบเรียกซ้ำจะทำงานเล็กน้อย แล้วเรียกตัวเองกลับเข้าไปใหม่ด้วย อินพุต ที่มีขนาด เล็กลง.
factorial(n)จะส่งค่าn * factorial(n - 1)กลับ — ซึ่งทำให้ขนาดของอินพุตลดลงหนึ่งหน่วยในแต่ละครั้งที่เรียกใช้.- การเรียกใช้แต่ละครั้งจะ รอ ให้การเรียกใช้ที่มีขนาดเล็กกว่าเสร็จสิ้นก่อนจึงจะดำเนินการต่อ.
- การเรียกใช้จะถูกวางซ้อนกัน (stack) จนกว่าจะเจอกรณีพื้นฐาน (base case) จากนั้นจึง คืนค่า ย้อนกลับขึ้นไปด้านบนทีละชั้น.
การซ้อนของการเรียกใช้
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)ส่งค่า1กลับ; จากนั้นส택จะคืนค่าย้อนกลับ:1, 1, 2, 6.- การเรียกใช้แต่ละครั้งจะเก็บสำเนาพารามิเตอร์ของตัวเองไว้จนกว่าจะส่งค่ากลับออก.
- การติดตามการทำงานแบบเรียกซ้ำ (tracing) คือการติดตามการเรียกใช้ ลง ไปยังกรณีพื้นฐาน แล้วติดตามการส่งค่า ขึ้น กลับมา.
การเรียกซ้ำทุกชนิดจำเป็นต้องมีกรณีพื้นฐานเพื่อหยุดการทำงาน — และการเรียกซ้ำแต่ละครั้งต้องเคลื่อนที่เข้าหากรณีนั้น (โดยมีอินพุตที่เล็กกว่า) หากขาดกรณีพื้นฐาน หรือเรียกใช้ด้วยอินพุตเดิมหรือที่ใหญ่ขึ้น วิธีนี้จะเรียกซ้ำไปเรื่อยๆ จนเกิด StackOverflowError. สามารถติดตามได้โดยการไล่ตามการเรียกใช้ลงสู่กรณีพื้นฐาน แล้วดูการส่งค่าย้อนกลับขึ้นมา.
sum(n) = 1 + 2 + … + n โดยใช้วิธีการเรียกซ้ำ:
- กรณีพื้นฐาน:
if (n == 0) return 0; - กรณีแบบเรียกซ้ำ:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
การเรียกซ้ำ (Recursion) คือการที่เมทოდ เรียกตัวเอง ด้วย อินพุต ที่มีขนาด เล็กลง ต้องมี กรณีพื้นฐาน (หยุดโดยตรง ไม่มีการเรียกเพิ่ม) และ กรณีแบบเรียกซ้ำ (ทำงานเล็กน้อยแล้วเรียกซ้ำกับอินพุตที่เล็กกว่า) การเรียกใช้จะซ้อนลงสู่กรณีพื้นฐาน แล้ว คืนค่า ย้อนกลับขึ้นไป ขาดกรณีพื้นฐานไปจะได้ StackOverflowError.
factorial(3) จะคืนค่าจากกรณีฐานขึ้นสู่ด้านบน
fact(0) ส่งกลับ 1 (กรณีฐาน); แต่ละ parent จะคูณ: 1, 1, 2, 6
ฟังก์ชันแบบ rekursion คือฟังก์ชันที่...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Recursion = ฟังก์ชันที่เรียกตัวเอง
กรณีฐานคือ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
กรณีฐานหยุดการเรียก rekursion
Rekursionที่ไม่มีกรณีฐานที่เข้าถึงได้จะทำให้เกิด...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
มันเรียก rekursionต่อไปเรื่อยๆ จนสแต็กเต็ม
เคส rekursionต้องเรียกตัวเองกับ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
每一次การเรียกต้องหดตัวเข้าใกล้กรณีฐาน
ถ้า factorial(0)=1 และ factorial(n)=n*factorial(n-1), ค่าของ factorial(3) คืออะไร?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
3 * 2 * 1 * 1 = 6.
每一次การเรียก rekursion เก็บสำเนาพารามิเตอร์ของตัวเองไว้จนกว่าจะส่งกลับ
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เรียกสแต็กอย่างอิสระ, แล้วค่อยคืนค่า