Persediaan Temu Duga Pengaturcaraan · Pelajaran

Ahli Sauh dan Rekursif

Struktur dua bahagian CTE rekursif dan cara penamatan berfungsi

Pelajaran 1 daripada 413 langkah

Ahli Sauh dan Rekursif ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Mengapa CTE Rekursif Sering Ditanya

Apabila penemu duga memberikan anda carta organisasi, senarai bahan atau pepohon kategori lalu meminta setiap keturunan, mereka sedang menguji sama ada anda akan menggunakan CTE rekursif. Cantuman biasa hanya boleh menelusuri bilangan aras yang tetap; rekursi boleh menelusuri kedalaman sewenang-wenangnya.

Frasa petunjuk dalam soalan ialah "hingga apa-apa kedalaman" atau "sehingga ke bahagian paling bawah". Itulah petunjuk anda. Dalam pelajaran ini, anda akan mempelajari struktur dua bahagian yang dikongsi oleh setiap CTE rekursif: ahli sauh dan ahli rekursif.

Rangka Dua Bahagian

CTE rekursif sentiasa mempunyai kata kunci WITH RECURSIVE (Postgres, SQLite, MySQL 8+; SQL Server tidak menyertakan RECURSIVE) dan badan yang terdiri daripada dua kueri yang digabungkan dengan UNION ALL:

Ahli sauh — baris permulaan, dijalankan sekali.
Ahli rekursif — merujuk nama CTE itu sendiri, dijalankan berulang kali.

Hafalkan rangka ini; penemu duga gemar meminta anda menulisnya dari awal.

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

Fungsi Ahli Sauh

Ahli sauh ialah kueri biasa yang tidak merujuk CTE. Ahli ini menghasilkan baris benih — titik permulaan aras sifar. Bagi carta organisasi, biasanya ahli ini ialah CEO (baris yang pengurusnya ialah NULL); bagi siri nombor, ahli ini ialah nombor pertama.

Ahli sauh dijalankan tepat sekali. Keluarannya menjadi kelompok baris pertama yang disalurkan ke langkah rekursif.

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

Fungsi Ahli Rekursif

Ahli rekursif merujuk CTE berdasarkan namanya. Pada setiap lelaran, ahli ini mencantumkan baris yang dihasilkan oleh lelaran sebelumnya dengan jadual asas untuk mencari aras seterusnya ke bawah.

Ahli ini tidak melihat keseluruhan CTE setakat itu — hanya baris yang ditambahkan dalam langkah sebelumnya. Inilah model mental utama yang diuji oleh penemu duga.

-- 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

Menggabungkannya

Gabungkan ahli sauh dan ahli rekursif dengan UNION ALL, kemudian enjin akan melakukan lelaran secara automatik. Setiap pusingan menambahkan aras seterusnya sehingga ahli rekursif mengembalikan sifar baris, lalu rekursi berhenti.

Berikut ialah penjejakan carta organisasi yang lengkap dan boleh dijalankan, serta menjejaki 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;

Cara Penamatan Berfungsi

Rekursi berhenti apabila ahli rekursif menghasilkan tiada baris baharu. Tiada pembilang gelung eksplisit diperlukan — cantuman secara semula jadi kehabisan padanan apabila anda sampai ke daun pepohon.

Dalam contoh organisasi, apabila anda sampai kepada pekerja yang tiada bawahan langsung, cantuman pada lelaran seterusnya tidak menemui anak, mengembalikan hasil kosong dan enjin berhenti. Memahami tingkah laku berhenti sendiri ini ialah soalan susulan klasik.

UNION ALL berbanding UNION

Penemu duga sering bertanya mengapa kita menggunakan UNION ALL dan bukannya UNION. Ada dua sebab:

Prestasi — UNION membuang pendua pada setiap lelaran, yang mahal dari segi pengiraan.
Ketepatan — dalam pepohon, baris pendua biasanya tidak boleh berlaku, jadi kerja membuang pendua itu sia-sia.

Gunakan UNION hanya apabila strukturnya ialah graf dan anda sengaja mahu menggabungkan nod berulang — tetapi untuk keselamatan daripada kitaran, pengawal eksplisit adalah lebih baik (diterangkan kemudian).

Menjejak Kedalaman dan Laluan

Dua lajur tambahan menjadikan hasil rekursif jauh lebih berguna dan sering diminta dalam temu duga:

kedalaman — mulakan pada 1 dalam ahli sauh, kemudian tambah 1 dalam ahli rekursif.
laluan — kumpulkan rangkaian id atau nama supaya anda dapat melihat laluan dari punca ke nod.

Membina path sebagai rentetan juga boleh digunakan sebagai alat pengesanan kitaran kemudian.

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;

Jenis Lajur Mesti Sepadan

Satu perangkap halus: ahli sauh dan ahli rekursif mesti mengembalikan bilangan lajur yang sama dengan jenis yang serasi. Jika anda membina rentetan path, nilai awal ahli sauh mesti ditetapkan kepada jenis yang cukup besar (contohnya VARCHAR(1000)), jika tidak enjin mungkin memotong nilai itu atau melaporkan ralat ketidakpadanan jenis pada lelaran seterusnya.

Inilah jenis perincian yang sengaja diselitkan oleh penemu duga untuk melihat sama ada anda benar-benar pernah menjalankan CTE rekursif, bukannya sekadar membaca tentangnya.

Contoh Senarai Bahan

Rangka yang sama menyelesaikan masalah senarai bahan: diberikan satu komponen, senaraikan setiap subkomponen pada apa-apa kedalaman. Ahli sauh memilih pemasangan peringkat teratas; ahli rekursif menelusuri pautan daripada parent_part kepada child_part.

Perhatikan bahawa strukturnya sama seperti carta organisasi — hanya nama lajurnya berubah. Menyedari bahawa satu rangka boleh digunakan untuk banyak masalah ialah kemahiran temu duga yang sebenar.

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;

Nota Dialek

Helaian ringkas merentas dialek yang dihargai penemu duga:

PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
SQL Server: hanya WITH name AS (...) — kata kunci RECURSIVE tersirat, dan sistem ini menguatkuasakan nilai lalai MAXRECURSION sebanyak 100.
Oracle: menyokong CTE rekursif dan sintaks CONNECT BY yang lebih lama.

Menyebut "SQL Server tidak menggunakan perkataan RECURSIVE" menunjukkan keluasan pengetahuan sebenar.

Semakan Pantas

Uji pemahaman anda terhadap struktur dua bahagian.

Jawab dalam pelajaran interaktif

Ringkasan

Kini anda menguasai rangka CTE rekursif:

WITH RECURSIVE + ahli sauh + UNION ALL + ahli rekursif.
Ahli sauh memulakan aras sifar dan dijalankan sekali.
Ahli rekursif mencantumkan lelaran sebelumnya dengan jadual asas dan terus dijalankan sehingga tiada baris dikembalikan.
Gunakan UNION ALL, jejak depth dan path, serta pastikan jenis lajur serasi.

Seterusnya: gunakan rangka ini untuk menelusuri carta organisasi sebenar ke bawah dan ke atas.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 90
Pelajaran: 360

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Ahli Sauh dan Rekursif” percuma?

Ya — teks penuh “Ahli Sauh dan Rekursif” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Ahli Sauh dan Rekursif”?

Struktur dua bahagian CTE rekursif dan cara penamatan berfungsi Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Ahli Sauh dan Rekursif” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

← Kembali ke Persediaan Temu Duga Pengaturcaraan