บทที่ 9 recursion
จบบทนี้ น้องจะเขียนฟังก์ชันที่เรียกตัวเองได้ และคิดโจทย์แบบ "ถ้ารู้คำตอบของปัญหาที่เล็กกว่านี้หนึ่งขั้น จะได้คำตอบของปัญหานี้ยังไง" ได้ วิธีคิดนี้ทำให้โจทย์บางแบบที่เขียนด้วยลูปแล้วยุ่งมาก เหลือไม่กี่บรรทัด เช่น หา ห.ร.ม. แบบยุคลิด ค้นหาในข้อมูลที่เรียงแล้วด้วยการแบ่งครึ่ง หอคอยฮานอย และพิมพ์ทุกรูปแบบที่เป็นไปได้ อย่างสตริงฐานสองทุกแบบหรือการเรียงสับเปลี่ยนทุกแบบ บทนี้เป็นฐานของ backtracking divide and conquer และ dynamic programming ที่ค่าย 2 ใช้เกือบทุกวัน และยังได้เห็นสองเรื่องที่ทำให้ recursion พังจริงบนเครื่อง คือเรียกซ้ำจนช้าเกินไป กับลึกจน stack ไม่พอ
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 9.1 ฟังก์ชันที่เรียกตัวเอง | กรณีฐานกับกรณีเรียกซ้ำ พิมพ์ก่อนหรือหลังเรียกตัวเอง call stack แฟกทอเรียล และ stack overflow ที่เกิดจริง |
| 9.2 แบ่งเป็นปัญหาที่เล็กลง | สามคำถามก่อนเขียน ผลรวมหลัก ยกกำลังแบบช้าและแบบแบ่งครึ่ง และ ห.ร.ม. แบบยุคลิด |
| 9.3 ฟีโบนัชชีและการจำคำตอบ | นับว่า fib(40) เรียกตัวเองกี่ครั้ง จับเวลาจริง แล้วแก้ด้วยอาเรย์จำคำตอบ |
| 9.4 recursion กับอาเรย์ | ผลรวม กลับลำดับ ค้นหาแบบแบ่งครึ่ง และเมื่อไรควรใช้ลูปแทน |
| 9.5 พิมพ์ทุกรูปแบบ | หอคอยฮานอย สตริงฐานสองยาว n ทุกแบบ และการเรียงสับเปลี่ยนทุกแบบ |