Coding Interview Prep · บทเรียน

สมาชิกหลักและสมาชิกแบบเรียกซ้ำ

โครงสร้างสองส่วนของ CTE แบบเรียกซ้ำ และวิธีการสิ้นสุดการเรียกซ้ำ

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

เหตุใดจึงพบ CTE แบบเรียกซ้ำบ่อย

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

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

โครงสร้างสองส่วน

CTE แบบเรียกซ้ำจะมีคีย์เวิร์ด WITH RECURSIVE เสมอ (PostgreSQL, SQLite, MySQL 8+; เซิร์ฟเวอร์เอสคิวแอลไม่ใส่ RECURSIVE) และมีส่วนเนื้อหาที่ประกอบด้วยคิวรีสองชุดซึ่งรวมกันด้วย UNION ALL:

สมาชิกตั้งต้น — แถวเริ่มต้น ซึ่งทำงานหนึ่งครั้ง
สมาชิกแบบเรียกซ้ำ — อ้างถึงชื่อ CTE เอง และทำงานซ้ำหลายครั้ง

จดจำโครงสร้างนี้ให้ขึ้นใจ เพราะผู้สัมภาษณ์มักขอให้คุณเขียนตั้งแต่ต้น

WITH RECURSIVE cte AS (
    -- anchor member
    SELECT ...
    UNION ALL
    -- recursive member
    SELECT ... FROM cte JOIN ...
)
SELECT * FROM cte;

หน้าที่ของสมาชิกตั้งต้น

สมาชิกตั้งต้น คือคิวรีทั่วไปที่ไม่มีการอ้างถึง CTE โดยจะสร้างแถวตั้งต้น ซึ่งเป็นจุดเริ่มต้นระดับศูนย์ สำหรับแผนผังองค์กร โดยทั่วไปคือ CEO (แถวที่ผู้จัดการเป็น NULL) ส่วนชุดลำดับตัวเลขก็คือตัวเลขแรก

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

-- Anchor: the top of the hierarchy
SELECT id, name, manager_id, 1 AS depth
FROM employees
WHERE manager_id IS NULL

หน้าที่ของสมาชิกแบบเรียกซ้ำ

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

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

-- Recursive: children of the rows found so far
SELECT e.id, e.name, e.manager_id, c.depth + 1
FROM employees e
JOIN cte c ON e.manager_id = c.id

นำทุกส่วนมาประกอบกัน

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

ต่อไปนี้คือตัวอย่างการเดินแผนผังองค์กรแบบสมบูรณ์ที่เรียกใช้ได้จริง และติดตาม depth ไปด้วย

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
)
SELECT id, name, depth FROM org ORDER BY depth, id;

การทำงานของการสิ้นสุด

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

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

UNION ALL กับ UNION

ผู้สัมภาษณ์มักถามว่าทำไมเราจึงใช้ UNION ALL แทนที่จะใช้ UNION มีเหตุผลสองข้อ:

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

ใช้ UNION เฉพาะเมื่อโครงสร้างเป็นกราฟและคุณต้องการยุบโหนดที่ซ้ำกันโดยตั้งใจเท่านั้น แต่เพื่อความปลอดภัยจากวงวน การใช้ตัวป้องกันอย่างชัดเจนจะดีกว่า (จะกล่าวถึงในภายหลัง)

การติดตามระดับความลึกและเส้นทาง

คอลัมน์เพิ่มเติมสองคอลัมน์จะทำให้ผลลัพธ์แบบเรียกซ้ำมีประโยชน์ขึ้นมาก และเป็นสิ่งที่ผู้สัมภาษณ์มักขอ:

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

การสร้าง path เป็นสตริงยังใช้เป็นเครื่องมือตรวจจับวงวนได้ในภายหลังด้วย

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth,
           CAST(name AS VARCHAR(1000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1,
           o.path || ' > ' || e.name
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT name, depth, path FROM org;

ชนิดข้อมูลของคอลัมน์ต้องตรงกัน

จุดที่มักพลาดเล็กน้อยคือ สมาชิกตั้งต้นและสมาชิกแบบเรียกซ้ำต้องคืนค่าจำนวนคอลัมน์เท่ากันและมีชนิดข้อมูลที่เข้ากันได้ หากคุณสร้างสตริง path ค่าเริ่มต้นของสมาชิกตั้งต้นต้องแปลงชนิดให้กว้างพอ (เช่น VARCHAR(1000)) ไม่เช่นนั้นระบบอาจตัดทอนค่าหรือแสดงข้อผิดพลาดชนิดข้อมูลไม่ตรงกันในรอบถัด ๆ ไป

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

ตัวอย่างบัญชีรายการวัสดุ

โครงสร้างเดียวกันนี้ใช้แก้ปัญหาบัญชีรายการวัสดุได้ด้วย: เมื่อกำหนดชิ้นส่วนหนึ่งชิ้น ให้แสดงชิ้นส่วนย่อยทุกชิ้นในทุกระดับ สมาชิกตั้งต้นเลือกชุดประกอบด้านบนสุด ส่วนสมาชิกแบบเรียกซ้ำเดินตามลิงก์จาก parent_part ไปยัง child_part

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

WITH RECURSIVE bom AS (
    SELECT child_part, parent_part, 1 AS lvl
    FROM parts WHERE parent_part = 'ENGINE'
    UNION ALL
    SELECT p.child_part, p.parent_part, b.lvl + 1
    FROM parts p JOIN bom b ON p.parent_part = b.child_part
)
SELECT child_part, lvl FROM bom;

หมายเหตุแยกตามระบบฐานข้อมูล

สรุปเปรียบเทียบระหว่างระบบฐานข้อมูลฉบับย่อที่ผู้สัมภาษณ์ชื่นชอบ:

PostgreSQL, เอสคิวไลต์, MySQL 8+: WITH RECURSIVE name AS (...)
เซิร์ฟเวอร์เอสคิวแอล: ใช้เพียง WITH name AS (...) — คีย์เวิร์ด RECURSIVE เป็นนัยอยู่แล้ว และกำหนดค่าเริ่มต้นของ MAXRECURSION ไว้ที่ 100
ออราเคิล: รองรับทั้ง CTE แบบเรียกซ้ำและไวยากรณ์แบบเก่า CONNECT BY

การพูดว่า "เซิร์ฟเวอร์เอสคิวแอลไม่ใช้คำว่า RECURSIVE" แสดงให้เห็นว่าคุณมีความรู้รอบด้านจริง

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

ทดสอบความเข้าใจโครงสร้างสองส่วนของคุณ

สรุป

ตอนนี้คุณเข้าใจโครงสร้าง CTE แบบเรียกซ้ำแล้ว:

WITH RECURSIVE + สมาชิกตั้งต้น + UNION ALL + สมาชิกแบบเรียกซ้ำ
สมาชิกตั้งต้นสร้างข้อมูลระดับศูนย์และทำงานหนึ่งครั้ง
สมาชิกแบบเรียกซ้ำเชื่อมรอบก่อนหน้าเข้ากับตารางหลัก และทำงานต่อจนกว่าจะคืนค่าไม่มีแถว
ใช้ UNION ALL ติดตาม depth กับ path และรักษาชนิดข้อมูลของคอลัมน์ให้เข้ากันได้

ถัดไป: ใช้โครงสร้างนี้เดินแผนผังองค์กรจริงทั้งลงด้านล่างและขึ้นด้านบน

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

บทเรียน “สมาชิกหลักและสมาชิกแบบเรียกซ้ำ” ฟรีหรือไม่

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

คุณจะเรียนรู้อะไรในบทเรียน “สมาชิกหลักและสมาชิกแบบเรียกซ้ำ”

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

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

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

บทเรียน “สมาชิกหลักและสมาชิกแบบเรียกซ้ำ” ใช้เวลานานแค่ไหน

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

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

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

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

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