Coding Interview Prep · บทเรียน

หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ

การตรวจจับวัฏจักร ขีดจำกัดความลึก และตัวป้องกันการเรียกซ้ำที่ผู้สัมภาษณ์ตรวจสอบเสมอ

หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คำถามที่ซ่อนอยู่เบื้องหลัง

หลังจากคุณเขียน CTE แบบเรียกซ้ำแล้ว ผู้สัมภาษณ์ที่เชี่ยวชาญอาจถามว่า "จะเกิดอะไรขึ้นหากข้อมูลมีวงวน" คำถามนี้ตรวจสอบว่าคุณเข้าใจหรือไม่ว่าการเรียกซ้ำอาจทำงานตลอดไป และรู้วิธีป้องกันหรือไม่

วงวนเกิดขึ้นเมื่อลำดับชั้นวนกลับมาหาตัวเอง เช่น A รายงานต่อ B และ B รายงานต่อ A ส่วนสมาชิกแบบเรียกซ้ำที่ไม่มีกลไกป้องกันจะสลับไปมาระหว่างทั้งสองอย่างไม่สิ้นสุด

วงวนเกิดขึ้นได้อย่างไร

ตามหลักแล้วโครงสร้างต้นไม้ไม่ควรมีวงวน แต่ข้อมูลจริงมักไม่เป็นระเบียบ การแก้ไขที่ผิดพลาดอาจกำหนดให้พนักงานเป็นผู้จัดการของตนเองโดยอ้อมได้ ส่วนกราฟ เช่น "ผู้ใช้ที่ติดตามผู้ใช้คนอื่น" มีวงวนเป็นธรรมชาติ

เมื่อสมาชิกแบบเรียกซ้ำพบจุดที่เคยเยี่ยมชมแล้วอีกครั้ง ก็จะสร้างจุดนั้นซ้ำ ซึ่งจะเรียกใช้จุดลูกของมันอีกครั้ง และลูปจะไม่มีวันว่าง การเรียกซ้ำจะหยุดก็ต่อเมื่อขั้นตอนหนึ่งไม่คืนแถวใดเลย แต่วงวนรับประกันว่าจะยังคืนแถวอยู่เสมอ

กลไกป้องกัน 1: จำกัดความลึก

กลไกป้องกันที่ง่ายที่สุดคือตัวนับความลึกพร้อมขีดจำกัดในส่วนสมาชิกแบบเรียกซ้ำ แม้จะมีวงวนอยู่ การเรียกซ้ำก็จะหยุดเมื่อถึงขีดจำกัด

นี่เป็นเครื่องมือแบบหยาบ เพราะจำกัดโครงสร้างต้นไม้ที่ลึกจริงด้วย แต่ใช้งานได้รวดเร็วและเหมาะกับการสัมภาษณ์

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.depth < 50
)
SELECT * FROM org;

กลไกป้องกัน 2: เส้นทางที่เยี่ยมชมแล้ว

กลไกป้องกันที่แม่นยำจะติดตามเส้นทางของจุดที่เยี่ยมชมแล้ว และไม่ยอมกลับเข้าไปยังจุดที่อยู่ในเส้นทางนั้นแล้ว สะสมรหัสลงในข้อความหรืออาร์เรย์ แล้วตรวจสอบการเป็นสมาชิกก่อนเรียกซ้ำ

วิธีนี้หยุดวงวนได้อย่างแม่นยำ และยังอนุญาตให้โครงสร้างต้นไม้ที่ถูกต้องมีความลึกเท่าใดก็ได้

WITH RECURSIVE org AS (
    SELECT id, name, manager_id,
           CAST(',' || id || ',' AS VARCHAR(2000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.path || e.id || ','
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.path NOT LIKE '%,' || e.id || ',%'
)
SELECT id, name, path FROM org;

เหตุใดการตรวจสอบเส้นทางจึงทำงานได้

เงื่อนไข path NOT LIKE '%,' || e.id || ',%' หมายความว่า "ให้ตามเส้นเชื่อมนี้ต่อเมื่อรหัสของจุดลูกยังไม่อยู่ในเส้นทาง" เครื่องหมายจุลภาคทำหน้าที่เป็นตัวคั่น เพื่อไม่ให้รหัส 1 ถูกจับคู่ผิดภายในรหัส 15

หากวงวนจะทำให้กลับมาเจอจุดเดิมอีกครั้ง WHERE จะกรองแถวนั้นออก ส่วนสมาชิกแบบเรียกซ้ำจะไม่คืนแถวใดในท้ายที่สุด และการเรียกซ้ำจะจบลงอย่างเรียบร้อย

กลไกป้องกัน 3: อนุประโยค CYCLE ในตัว

Postgres รุ่นใหม่ (14 ขึ้นไป) และมาตรฐาน SQL มีอนุประโยค CYCLE ในตัว ซึ่งตรวจสอบเส้นทางและทำเครื่องหมายวงวนให้คุณโดยอัตโนมัติ นี่เป็นคำตอบที่สะอาดที่สุดเมื่อระบบรองรับ

WITH RECURSIVE org AS (
    SELECT id, name, manager_id FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e JOIN org o ON e.manager_id = o.id
)
CYCLE id SET is_cycle USING cycle_path
SELECT id, name, is_cycle FROM org;

MAXRECURSION ของ SQL Server

SQL Server กำหนดขีดจำกัดเริ่มต้นไว้ที่ 100 ระดับการเรียกซ้ำ หากวงวนหรือโครงสร้างต้นไม้ที่ลึกเกินขีดจำกัดนี้ คำสั่งจะเกิดข้อผิดพลาดแทนที่จะทำงานไม่รู้จบ จึงทำหน้าที่เป็นกลไกนิรภัยโดยปริยาย

คุณสามารถเพิ่มหรือลบขีดจำกัดนี้ได้ด้วย OPTION (MAXRECURSION n) โดยค่า 0 หมายถึงไม่จำกัด แต่การลบขีดจำกัดโดยไม่มีการตรวจสอบเส้นทางจะทำให้ข้อมูลที่มีวงวนกลับมาเสี่ยงเกิดลูปไม่รู้จบอีกครั้ง

-- Cap recursion at 200 levels in SQL Server
SELECT * FROM org
OPTION (MAXRECURSION 200);

การตรวจจับกับการป้องกันวงวน

ผู้สัมภาษณ์อาจแยกเป้าหมายออกเป็นสองแบบ:

ป้องกัน — ข้ามเส้นเชื่อมที่เป็นวงวนอย่างเงียบ ๆ เพื่อให้คำสั่งทำงานจนจบ (ใช้ WHERE ตรวจสอบเส้นทาง)
ตรวจจับและรายงาน — แสดงให้เห็นว่าแถวใดเป็นส่วนหนึ่งของวงวน เพื่อให้ทีมข้อมูลแก้ไขข้อมูลที่ผิดพลาดได้ (ใช้ค่าสถานะ is_cycle ของอนุประโยค CYCLE)

การรู้จักทั้งสองแบบและรู้ว่าแต่ละแบบเหมาะกับสถานการณ์ใด แสดงถึงความเข้าใจในระดับผู้มีประสบการณ์

ข้อควรพิจารณาด้านประสิทธิภาพ

การเรียกซ้ำอาจใช้ทรัพยากรมากแม้ไม่มีวงวน เคล็ดลับที่ผู้สัมภาษณ์มักอยากได้ยินมีดังนี้:

สร้างดัชนีให้คอลัมน์ที่ใช้เชื่อม เช่น manager_id เพื่อให้การเชื่อมในแต่ละรอบทำงานได้รวดเร็ว
กรองตั้งแต่ต้นในจุดตั้งต้น เพื่อเริ่มจากเฉพาะโครงสร้างย่อยที่ต้องการ ไม่ใช่ทั้งตาราง
หลีกเลี่ยง SELECT * — เก็บไว้เฉพาะคอลัมน์ที่การเรียกซ้ำต้องใช้ รวมถึง depth และ path

แม่แบบที่ปลอดภัย

รวมกลไกป้องกันเข้าด้วยกันเป็นแม่แบบที่คุณสามารถนำมาใช้ได้แม้อยู่ภายใต้ความกดดัน: ใช้คอลัมน์ความลึกเป็นกลไกสำรอง และใช้การตรวจสอบเส้นทางเป็นกลไกป้องกันที่แม่นยำ แม้ข้อมูลสะอาดจะไม่จำเป็นต้องใช้ทั้งสองอย่าง การแสดงให้เห็นว่าคุณใช้ทั้งคู่ก็แสดงถึงความรอบคอบ

WITH RECURSIVE walk AS (
    SELECT id, parent_id, 1 AS depth,
           CAST(',' || id || ',' AS VARCHAR(4000)) AS path
    FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, w.depth + 1,
           w.path || n.id || ','
    FROM nodes n JOIN walk w ON n.parent_id = w.id
    WHERE w.depth < 100
      AND w.path NOT LIKE '%,' || n.id || ',%'
)
SELECT id, depth FROM walk;

ข้อผิดพลาดที่พบบ่อยในการสัมภาษณ์

ข้อผิดพลาดสุดท้ายที่ควรหลีกเลี่ยง:

ลบ MAXRECURSION บน SQL Server โดยไม่มีกลไกป้องกันอื่น — ทำให้ความเสี่ยงของลูปไม่รู้จบกลับมาอีก
กำหนดคอลัมน์ข้อความของเส้นทางให้สั้นเกินไป จนเกิดการตัดข้อมูลและทำให้กลไกป้องกันเสียโดยไม่แสดงข้อผิดพลาด
จับคู่รหัสโดยไม่มีตัวคั่นเป็นเครื่องหมายจุลภาค ทำให้รหัส 1 ถูกจับคู่ผิดภายในรหัส 21
คิดว่าข้อมูลไม่มีวงวนเพียงเพราะข้อมูลนั้น "ควรจะ" ไม่มีวงวน — ควรถามเรื่องนี้เสมอ

ตรวจสอบความเข้าใจ

เลือกกลไกป้องกันที่หยุดวงวนได้อย่างแม่นยำโดยไม่จำกัดความลึกที่ถูกต้องตามปกติ

สรุปทบทวน

คำตอบเกี่ยวกับ CTE แบบเรียกซ้ำทุกคำตอบควรกล่าวถึงความปลอดภัย:

วงวนทำให้สมาชิกแบบเรียกซ้ำไม่คืนผลลัพธ์ว่าง ดังนั้นการเรียกซ้ำจึงไม่หยุด
ขีดจำกัดความลึก = กลไกสำรองที่รวดเร็ว; การตรวจสอบเส้นทางที่เยี่ยมชมแล้ว = การป้องกันวงวนที่แม่นยำ; อนุประโยค CYCLE = การตรวจจับในตัวของระบบรุ่นใหม่
MAXRECURSION 100 ของ SQL Server เป็นกลไกจำกัดโดยปริยาย อย่าลบออกโดยไม่มีกลไกป้องกันอื่น
สร้างดัชนีให้คอลัมน์ที่ใช้เชื่อม และเริ่มจากข้อมูลเฉพาะส่วนที่ต้องการเพื่อประสิทธิภาพ

ตอนนี้คุณสามารถเขียน ไล่ตาม สร้าง และทำให้ CTE แบบเรียกซ้ำปลอดภัยได้ตั้งแต่ต้นจนจบ

คำถามที่พบบ่อย

บทเรียน “หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ”

การตรวจจับวัฏจักร ขีดจำกัดความลึก และตัวป้องกันการเรียกซ้ำที่ผู้สัมภาษณ์ตรวจสอบเสมอ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “หลีกเลี่ยงการเรียกซ้ำไม่รู้จบ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ Coding Interview Prep