คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ
แบ่งโจทย์เป็นสำเนาที่เล็กลง
คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ความหมายของการเรียกซ้ำ
การเรียกซ้ำ คือฟังก์ชันที่แก้ปัญหาด้วยการเรียกตัวเองกับส่วนที่เล็กลง จนกระทั่งส่วนนั้นเล็กพอที่จะตอบได้โดยตรง 🌀
เชื่อมั่นในปัญหาส่วนที่เล็กกว่า
กรอบความคิดสำคัญคือ การเชื่อมั่นในขั้นย่อย: สมมติว่าการเรียกซ้ำทำงานกับข้อมูลที่เล็กกว่าได้แล้ว จากนั้นสร้างคำตอบของคุณต่อยอดจากผลนั้น
การเรียกซ้ำทุกครั้งต้องมีกรณีฐาน
กรณีฐาน คือข้อมูลนำเข้าขนาดเล็กที่สุดที่คุณตอบได้โดยไม่เรียกซ้ำ หากไม่มีกรณีนี้ ฟังก์ชันจะเรียกตัวเองไปเรื่อย ๆ จนทำงานล้มเหลว
กรณีเรียกซ้ำ
กรณีเรียกซ้ำ จะลดขนาดปัญหาแล้วเรียกตัวเองกับรูปแบบที่เล็กลง การเรียกแต่ละครั้งต้องเข้าใกล้กรณีฐานมากขึ้น
แฟกทอเรียลเป็นตัวอย่างแรก
ตรงนี้ แฟกทอเรียลแสดงให้เห็นทั้งสองส่วน ได้แก่ กรณีฐานที่ศูนย์และการเรียกซ้ำด้วย n ลบหนึ่ง
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)การทำงานของสแตกการเรียก
การเรียกแต่ละครั้งจะรออยู่บนสแตกการเรียกจนกว่าการเรียกภายในจะส่งค่ากลับ การเรียกที่ลึกที่สุดจะเสร็จก่อน จากนั้นคำตอบจะคลี่คลายย้อนกลับขึ้นมา
จับตาความลึกของการเรียกซ้ำ
โดยค่าเริ่มต้น ไพทอนจำกัดความลึกของการเรียกซ้ำไว้ใกล้เคียง 1,000 การเรียกซ้ำที่ลึกในการแข่งขันจำเป็นต้องใช้ sys.setrecursionlimit เพื่อหลีกเลี่ยงข้อผิดพลาดขณะทำงาน
import sys
sys.setrecursionlimit(300000)ทำให้คืบหน้าทุกครั้งที่เรียก
การเรียกซ้ำที่ถูกต้องจะลดขนาดข้อมูลเข้าเข้าใกล้กรณีฐานเสมอ หากขนาดเดิมกลับมาอีกครั้ง ก็จะวนซ้ำไม่สิ้นสุด ⚠️
หาผลรวมของรายการด้วยการเรียกซ้ำ
การหาผลรวมแบบเรียกซ้ำนี้ตัดสมาชิกตัวแรกออก แล้วอาศัยการเรียกเพื่อบวกส่วนที่เหลือของรายการ
def total(a):
if not a:
return 0
return a[0] + total(a[1:])ต้นไม้การเรียกซ้ำแสดงการแตกกิ่ง
เมื่อฟังก์ชันเรียกมากกว่าหนึ่งครั้ง งานจะก่อตัวเป็นต้นไม้การเรียกซ้ำ ขนาดของต้นไม้นี้บอกต้นทุนรวมของงาน
งานซ้ำอาจทำให้ช้า
ฟีโบนัชชีแบบพื้นฐานคำนวณค่าเดิมซ้ำแล้วซ้ำเล่า ทำให้ใช้เวลาแบบเอ็กซ์โพเนนเชียล การจดจำคำตอบเหล่านั้นช่วยแก้ปัญหาได้ทันที
ตรวจสอบความเข้าใจ
จะเกิดอะไรขึ้นหากฟังก์ชันแบบเรียกซ้ำไม่มีกรณีฐาน
สรุปทบทวน: สองส่วน แนวคิดเดียว
ได้เรียนรู้แล้วว่า การเรียกซ้ำต้องมีกรณีฐานเพื่อหยุด และมีกรณีเรียกซ้ำที่ลดขนาดข้อมูลเข้า เชื่อมั่นในการเรียกที่เล็กลง แล้วส่วนที่เหลือจะตามมาเอง 🎯
คำถามที่พบบ่อย
บทเรียน “คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ”
แบ่งโจทย์เป็นสำเนาที่เล็กลง คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- คิดแบบเวียนเกิด: ฐานและการเรียกซ้ำ
- สร้างเซตย่อยทั้งหมด
- การเรียงสับเปลี่ยนและแนวคิด N-Queens
- ตัดกิ่งเพื่อให้อยู่รอดในขีดจำกัดเวลา