Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Päättymättömän rekursion välttäminen

Syklien tunnistus, syvyysrajat ja rekursion suojaus, jonka jokainen haastattelija tarkistaa

Oppitunti 4/413 vaihetta

Päättymättömän rekursion välttäminen on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Kysymys varsinaisen kysymyksen takana

Kun rekursiivinen CTE on kirjoitettu, tarkkanäköinen haastattelija kysyy: "Mitä tapahtuu, jos datassa on sykli?" Tällä testataan, ymmärretäänkö rekursion voivan jatkua loputtomiin — ja osataanko siltä suojautua.

Sykli syntyy, kun hierarkia kiertyy takaisin itseensä: A raportoi B:lle ja B raportoi A:lle. Naiivi rekursiivinen jäsen vuorottelee niiden välillä loputtomasti.

Miten sykli muodostuu

Puiden pitäisi olla syklittömiä, mutta todellinen data on sotkuista. Virheellinen päivitys voi asettaa työntekijän omaksi (epäsuoraksi) esihenkilökseen. Graafi — kuten "käyttäjät, jotka seuraavat käyttäjiä" — on luonteeltaan syklinen.

Kun rekursiivinen jäsen kohtaa uudelleen solmun, jossa se on jo käynyt, se tuottaa solmun uudelleen. Tämä käynnistää sen lapset uudelleen, eikä silmukka koskaan tyhjene. Rekursio pysähtyy vain, kun jokin vaihe ei palauta rivejä; sykli takaa, että rivejä palautuu aina.

Suojaus 1: syvyysrajoitus

Yksinkertaisin turvaverkko on syvyyslaskuri, jolle asetetaan yläraja rekursiivisessa jäsenessä. Vaikka sykli olisi olemassa, rekursio päättyy rajan saavuttamiseen.

Tämä on karkea menetelmä — se rajoittaa myös aidosti syviä puita — mutta se on nopea ja sopii hyvin haastattelutilanteeseen.

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;

Suojaus 2: käytyjen solmujen polku

Tarkka suojaus seuraa käytyjen solmujen polkua ja estää palaamisen solmuun, joka on jo polulla. Tunnukset kerätään merkkijonoon tai taulukkoon, ja niiden kuuluminen polulle tarkistetaan ennen rekursion jatkamista.

Näin syklit pysäytetään täsmällisesti, mutta laillisten puiden mielivaltainen syvyys sallitaan edelleen.

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;

Miksi polkutarkistus toimii

Ehto path NOT LIKE '%,' || e.id || ',%' tarkoittaa, että "seurataan tätä yhteyttä vain, jos lapsen tunnus ei ole jo polulla". Pilkut toimivat erottimina, joten tunnus 1 ei osu virheellisesti tunnuksen 15 sisällä olevaan osaan.

Jos sykli johtaisi solmun kohtaamiseen uudelleen, WHERE-ehto suodattaa kyseisen rivin pois, rekursiivinen jäsen ei lopulta palauta mitään ja rekursio päättyy hallitusti.

Suojaus 3: sisäänrakennettu CYCLE-lauseke

Moderni Postgres (14+) ja SQL-standardi tarjoavat sisäänrakennetun CYCLE-lausekkeen, joka automatisoi polkutarkistuksen ja merkitsee syklit. Se on siistein ratkaisu, kun tietokantamoottori tukee sitä.

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;

SQL Serverin MAXRECURSION

SQL Server käyttää oletusarvoisesti enintään 100 rekursiotasoa. Jos sykli tai syvä puu ylittää rajan, kysely päättyy virheeseen loputtoman silmukan sijaan — kyseessä on epäsuora turvamekanismi.

Raja voidaan nostaa tai poistaa käyttämällä OPTION (MAXRECURSION n) -määrettä, jossa 0 tarkoittaa rajoittamatonta. Rajoituksen poistaminen ilman polkutarkistusta palauttaa kuitenkin syklisen datan aiheuttaman loputtoman silmukan riskin.

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

Syklien tunnistaminen ja estäminen

Haastatteluissa voidaan erottaa kaksi tavoitetta:

Estäminen — ohitetaan syklinen yhteys hiljaisesti, jotta kysely valmistuu (polkutarkistuksen WHERE-ehto).
Tunnistaminen ja raportointi — tuodaan esiin, mitkä rivit kuuluvat sykliin, jotta datatiimi voi korjata virheellisen datan (CYCLE-lausekkeen is_cycle-lippu).

Molempien tunteminen ja sen ymmärtäminen, milloin kumpaakin käytetään, on kokeneen kehittäjän osaamista.

Suorituskykynäkökohdat

Rekursio voi olla kallista myös ilman syklejä. Haastattelijat arvostavat esimerkiksi seuraavia vinkkejä:

Liitossarake kannattaa indeksoida, esimerkiksi manager_id, jotta kunkin iteraation liitos on nopea.
Suodata ankkurissa varhain, jotta mukaan otetaan vain tarvittava alipuu eikä koko taulua.
Vältä SELECT * -valintaa — kuljeta mukana vain rekursion tarvitsemat sarakkeet sekä depth- ja path-sarakkeet.

Turvallinen mallipohja

Yhdistä suojaukset mallipohjaksi, jonka voi tuottaa paineen alla: syvyyssarake toimii varmistuksena ja polkutarkistus täsmällisenä suojauksena. Vaikka molemmat olisivat siistissä datassa liioittelua, niiden esittäminen osoittaa huolellisuutta.

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;

Yleiset haastattelun sudenkuopat

Viimeiset sudenkuopat, joita on vältettävä:

MAXRECURSION-rajoituksen poistaminen SQL Serverissä ilman muuta suojausta — tämä avaa jälleen mahdollisuuden loputtomaan silmukkaan.
Polkumerkkijonolle varattu sarake on liian lyhyt, mikä aiheuttaa katkaisun ja rikkoo suojauksen huomaamatta.
Tunnusten täsmäyttäminen ilman pilkuilla erotettuja rajaajia, jolloin tunnus 1 osuu virheellisesti tunnuksen 21 sisällä olevaan osaan.
Oletetaan datan olevan syklitöntä vain siksi, että sen "pitäisi" olla sitä — asia on aina varmistettava.

Pikatarkistus

Valitse suojaus, joka pysäyttää syklit täsmällisesti rajoittamatta laillista syvyyttä.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Jokaisessa rekursiivista CTE:tä koskevassa vastauksessa on käsiteltävä turvallisuus:

Syklit estävät rekursiivista jäsentä palauttamasta tyhjää tulosta, joten rekursio ei koskaan pääty.
Syvyysrajoitus = nopea varmistus; käytyjen solmujen polkutarkistus = tarkka syklien esto; CYCLE-lauseke = sisäänrakennettu tunnistus moderneissa moottoreissa.
SQL Serverin MAXRECURSION 100 on epäsuora turvamekanismi — sitä ei pidä poistaa ilman muuta suojausta.
Indeksoi liitossarake ja rajaa ankkurin lähtöjoukko tarkasti suorituskyvyn vuoksi.

Nyt osaat kirjoittaa, läpikäydä, muodostaa ja suojata rekursiivisia CTE:itä alusta loppuun.

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Päättymättömän rekursion välttäminen” ilmainen?

Kyllä – oppitunnin ”Päättymättömän rekursion välttäminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Päättymättömän rekursion välttäminen”?

Syklien tunnistus, syvyysrajat ja rekursion suojaus, jonka jokainen haastattelija tarkistaa Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Päättymättömän rekursion välttäminen”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin