Coding Interview Prep · Lekcja

Unikanie nieskończonej rekurencji

Wykrywanie cykli, limity głębokości i zabezpieczenie rekurencji sprawdzane przez każdego rekrutera

Unikanie nieskończonej rekurencji to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Pytanie stojące za pytaniem

Po napisaniu rekurencyjnego CTE osoba prowadząca rozmowę kwalifikacyjną może zadać trafne pytanie: „Co się stanie, jeśli dane zawierają cykl?”. Sprawdza w ten sposób, czy rozumiesz, że rekurencja może trwać w nieskończoność — oraz czy wiesz, jak się przed tym zabezpieczyć.

Cykl występuje wtedy, gdy hierarchia zapętla się sama w sobie: A podlega B, a B podlega A. Naiwna część rekurencyjna będzie nieskończenie przechodzić między nimi.

Jak powstaje cykl

Drzewa powinny być acykliczne, ale rzeczywiste dane bywają nieuporządkowane. Błędna aktualizacja może ustawić pracownika jako swojego własnego (pośredniego) menedżera. Graf — na przykład „użytkownicy obserwujący innych użytkowników” — z natury może zawierać cykle.

Gdy część rekurencyjna ponownie napotka odwiedzony już węzeł, generuje go ponownie, co z kolei ponownie uruchamia jego elementy podrzędne, a pętla nigdy się nie kończy. Rekurencja zatrzymuje się tylko wtedy, gdy pewien krok nie zwróci żadnych wierszy; cykl gwarantuje, że wiersze będą zwracane zawsze.

Zabezpieczenie 1: limit głębokości

Najprostszym zabezpieczeniem jest licznik głębokości z limitem w części rekurencyjnej. Nawet jeśli istnieje cykl, rekurencja zatrzyma się po osiągnięciu limitu.

To dość ogólne rozwiązanie — ogranicza również poprawne, głębokie drzewa — ale jest szybkie i dobrze sprawdza się podczas rozmowy kwalifikacyjnej.

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;

Zabezpieczenie 2: odwiedzona ścieżka

Precyzyjne zabezpieczenie śledzi ścieżkę odwiedzonych węzłów i nie pozwala ponownie wejść do węzła, który już się na niej znajduje. Identyfikatory można gromadzić w ciągu znaków lub tablicy, a przed wykonaniem rekurencji sprawdzać ich przynależność.

W ten sposób cykle są zatrzymywane dokładnie, a poprawne drzewa mogą mieć dowolną głębokość.

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;

Dlaczego sprawdzanie ścieżki działa

Warunek path NOT LIKE '%,' || e.id || ',%' oznacza „podążaj za tą krawędzią tylko wtedy, gdy identyfikator elementu podrzędnego nie znajduje się jeszcze na ścieżce”. Przecinki pełnią funkcję separatorów, dzięki czemu identyfikator 1 nie zostanie omyłkowo dopasowany wewnątrz identyfikatora 15.

Jeśli cykl spowodowałby ponowne odwiedzenie węzła, klauzula WHERE odfiltruje ten wiersz, część rekurencyjna ostatecznie nie zwróci żadnych wierszy, a rekurencja zakończy się prawidłowo.

Zabezpieczenie 3: natywna klauzula CYCLE

Nowsze wersje Postgres (14+) oraz standard SQL oferują wbudowaną klauzulę CYCLE, która automatyzuje sprawdzanie ścieżki i oznacza cykle. Jest to najczystsze rozwiązanie, gdy dany silnik je obsługuje.

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 w SQL Server

SQL Server narzuca domyślny limit 100 poziomów rekurencji. Jeśli cykl lub głębokie drzewo go przekroczy, zapytanie zakończy się błędem, zamiast działać w nieskończonej pętli — jest to niejawne zabezpieczenie.

Limit można zwiększyć lub usunąć za pomocą OPTION (MAXRECURSION n), gdzie 0 oznacza brak ograniczenia. Usunięcie limitu bez zabezpieczenia w postaci sprawdzania ścieżki ponownie stwarza ryzyko nieskończonej pętli w przypadku danych zawierających cykle.

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

Wykrywanie a zapobieganie cyklom

Osoby prowadzące rozmowy kwalifikacyjne mogą rozróżniać dwa cele:

Zapobieganie — ciche pomijanie cyklicznej krawędzi, aby zapytanie mogło się zakończyć (klauzula WHERE sprawdzająca ścieżkę).
Wykrywanie i zgłaszanie — wskazanie w wynikach, które wiersze należą do cyklu, aby zespół zajmujący się danymi mógł naprawić błędne dane (flaga is_cycle klauzuli CYCLE).

Znajomość obu podejść oraz wiedza, kiedy stosować każde z nich, to rozróżnienie na poziomie seniora.

Kwestie wydajnościowe

Rekurencja może być kosztowna nawet bez cykli. Warto wspomnieć o następujących wskazówkach:

Indeksuj kolumnę używaną w złączeniu, na przykład manager_id, aby złączenie w każdej iteracji działało szybko.
Filtruj wcześnie w części kotwiczącej, aby rozpocząć tylko od potrzebnego poddrzewa, a nie od całej tabeli.
Unikaj SELECT * — przenoś tylko kolumny wymagane przez rekurencję oraz depth/path.

Bezpieczny szablon

Połącz zabezpieczenia w szablon, który można odtworzyć pod presją: kolumna głębokości jako dodatkowe zabezpieczenie oraz sprawdzanie ścieżki jako precyzyjna ochrona. Nawet jeśli jedno z nich okaże się zbędne dla poprawnych danych, pokazanie obu świadczy o solidnym podejściu.

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;

Typowe pułapki na rozmowie kwalifikacyjnej

Oto najważniejsze pułapki, których należy unikać:

Usunięcie MAXRECURSION w SQL Server bez innego zabezpieczenia — ponownie otwiera drogę do nieskończonej pętli.
Zadeklarowanie kolumny tekstowej przechowującej ścieżkę jako zbyt krótkiej, co powoduje obcięcie wartości i ciche uszkodzenie zabezpieczenia.
Dopasowywanie identyfikatorów bez przecinków jako separatorów, przez co identyfikator 1 zostaje omyłkowo dopasowany wewnątrz identyfikatora 21.
Zakładanie, że dane nie zawierają cykli tylko dlatego, że „powinny” ich nie zawierać — zawsze warto to sprawdzić.

Szybki test

Należy wybrać zabezpieczenie, które precyzyjnie zatrzymuje cykle bez ograniczania poprawnej głębokości.

Podsumowanie

Każda odpowiedź dotycząca rekurencyjnego CTE powinna uwzględniać bezpieczeństwo:

Cykle sprawiają, że część rekurencyjna nigdy nie zwraca pustego wyniku, więc rekurencja się nie zatrzymuje.
Limit głębokości = szybkie zabezpieczenie; sprawdzanie odwiedzonej ścieżki = precyzyjne zapobieganie cyklom; klauzula CYCLE = natywne wykrywanie w nowoczesnych silnikach.
Wartość MAXRECURSION 100 w SQL Server stanowi niejawne zabezpieczenie — nie należy jej usuwać bez zastosowania innego zabezpieczenia.
Indeksuj kolumnę używaną w złączeniu i ograniczaj zakres danych początkowych, aby uzyskać lepszą wydajność.

Możesz już od początku do końca tworzyć, przeglądać, generować i zabezpieczać rekurencyjne CTE.

Często zadawane pytania

Czy lekcja „Unikanie nieskończonej rekurencji” jest bezpłatna?

Tak — pełny tekst „Unikanie nieskończonej rekurencji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Unikanie nieskończonej rekurencji”?

Wykrywanie cykli, limity głębokości i zabezpieczenie rekurencji sprawdzane przez każdego rekrutera Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Unikanie nieskończonej rekurencji”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

Elementy zakotwiczający i rekurencyjny
Przechodzenie po strukturze organizacyjnej
Generowanie szeregów liczb i dat
Unikanie nieskończonej rekurencji

← Powrót do Coding Interview Prep