Rekurencja – alternatywa dla pętli w JavaScript

 Rekurencja – na czym polega i czy warto ją znać

 Rekurencja (rekursja) – definicja i przykłady

Rekurencja to odwołanie się funkcji/procedury/definicji do samej siebie. Funkcja rekurencyjna zatem po prostu wywołuje samą siebie. Brzmi jak przepis na zapętlenie przeglądarki/terminala? Owszem, może się tak stać, jeśli nie uwzględnimy warunku, którego niespełnienie zatrzyma ponowne wywołanie.

Przykładem rekurencji z życia wziętym jest odbicie lustra w lustrze lub obrazu z kamerki skierowanej na pulpit, na którym wyświetlany jest obraz z kamerki.

function showPreview() {
    showPreview()
}

Nawet Google pomaga nam zrozumieć definicję: po wpisaniu w wyszukiwarkę słowa rekurencja, wyświetla zapytanie Czy chodziło Ci o: rekurencja. Kliknięcie w proponowane słowo rekurencja powoduje ponowne wyświetlenie strony z zapytaniem Czy chodziło Ci o: rekurencja.

function askUser() {
    if(user.click) {
        askUser()
    }
}

 Rekurencja w JavaScript a pętla

Czy powyższe przykłady kojarzą Ci się z pętlą? Jeśli tak, to słusznie – dane problemy możemy bowiem zapisać zarówno w formie funkcji rekurencyjnej, jak i pętli. Rozpatrzmy taki przykład: mamy tablicę liczb. Chcemy sumować kolejne liczby i po tym usuwać je z tablicy – robimy to tak długo, aż tablica będzie pusta (może być to np. gra, w której kolejne liczby po zsumowaniu znikają z ekranu).

Założenie brzmi: wykonuj działanie dodawania tak długo, póki tablica posiada elementy.

Pętla do-while

Przypomina to pętlę do-while. I rzeczywiście możemy to zapisać np. w taki sposób:

const arr = [1, 2, 3, 4, 5];
let sum = 0;

function sumNums(arr) {
    do {
        sum += arr[arr.length - 1]; // do 0 dodaj ostatni element z tablicy
        arr.pop(); // usuń ostatni element z tablicy
    } while (arr.length > 0); // powtórz działanie, jeśli tablica nie jest pusta
}

sumNums(arr)

Rekurencja

Rekurencja nie różni się znacznie, prócz tego, że funkcja sumująca będzie musiała wywołać samą siebie:

const arr = [1, 2, 3, 4, 5];
let sum = 0;

function add(arr) {
    if (arr.length > 0) {
        // jeśli tablica nie jest pusta
        sum += arr[arr.length - 1]; // do 0 dodaj ostatni element z tablicy
        arr.pop(); // usuń ostatni element z tablicy
        add(arr); // wywołaj funkcję ponownie
    }
}

add(arr);

Rekurencja vs pętla – wydajność

Skoro można coś wykonać na dwa podobne sposoby, to pojawia się pytanie o wydajność. To rekurencja jest mniej wydajna niż pętla.

Dlaczego tak się dzieje? Wszystkiemu winny jest stos wywołań (ang. call stack). Interpreter JavaScriptu zapamiętuje wywołanie funkcji nr 1, następnie zapamiętuje funkcję nr 2 wywołaną w funkcji nr 1, następnie zapamiętuje funkcję nr 3 wywołaną w funkcji nr 2 i tak dalej, aż funkcje przestaną się wywoływać lub wystąpi błąd (stack overflow error) z powodu braku miejsca przeznaczonego dla tego stosu wywołań.

W naszej funkcji rekurencyjnej sumującej liczby interpreter stworzy więc sobie stos wywołań tak „wysoki” jak długa jest tablica – tyle raz bowiem ponownie wywoła funkcję add().

W przypadku pętli interpreter powtarza te same kroki tak długo, jak długo warunek jest prawdziwy. Zabiera to mniej miejsca i czasu.

W takim razie po co stosować rekurencję? Może się zdarzyć, że rozwiązanie skomplikowanego problemu za jej pomocą będzie prostsze i bardziej zrozumiałe niż użycie pętli, np. jak w przypadku wież Hanoi.

 Przykład użycia rekurencji w JavaScript

 Struktura danych na podstawie magazynu

Rozumienie rekurencji jest nieraz sprawdzane w zadaniach rekrutacyjnych, warto więc poznać jej działanie na bardziej życiowym przykładzie: konkretnej strukturze danych.

Załóżmy, że kontrolujemy stan magazynu, w którym regały mają oznakowane półki, na półkach są kontenery, a w kontenerach ruchome pojemniki, w których przechowujemy produkty.

W magazynie zawsze może dojść do jakiegoś przemeblowania – np. zlikwiduje się jedną półkę, by niżej zmieścić wysokie kontenery. Wówczas wszystkie kontenery, które stały na zlikwidowanej półce, muszą zostać przypisane do innej półki. Zauważ, że w tej sytuacji pojemniki znajdujące się w przenoszonym kontenerze nie zmieniają lokalizacji – tzn. nadal pozostają w tym przenoszonym kontenerze (rodzicu).

Czasem jednak zdarza się sytuacja, że nie korzysta się z kontenerów – np. nie opłaca się stawiać ich na półce, bo produktów jest niewiele. Wówczas pojemniki stoją na półce „luzem” (ich rodzicem nie jest już więc kontener, lecz bezpośrednio półka).

Być może w głowie zobaczyłeś taką strukturę danych: obiekt (regał), zawierający obiekty (półki), które zawierają kolejne obiekty (kontenery), które zawierają kolejne (pojemniki) i kolejne (produkty).

const regal_I = {
    polka_1: {
        kontener_A: {
            pojemnik_a1: {
                '10A234D': {
                    typ: 'produkty papierowe',
                },
                '10A234F': {
                    typ: 'produkty papierowe',
                },
            },
            pojemnik_b1: {
                '10A234D': {
                    typ: 'produkty papierowe',
                },
                '10A234F': {
                    typ: 'produkty papierowe',
                },
            },
        },
        kontener_B: {
            pojemnik_a2: {
                '11A234D': {                    
                    typ: 'produkty kartonowe',
                },
                '11A234F': {                    
                    typ: 'produkty kartonowe',
                },
            },
        },
    },
    polka_2: {},
};

Tyle poziomów zagnieżdżenia? To zaczyna źle wyglądać.

Jeśli przenosilibyśmy produkt nr 10A234D w inne miejsce, to musielibyśmy dostać się do niego przez zapis:  regal_I.polka_1.kontener_A.pojemnik_a1['10A234D'].

Potem przenoszony obiekt trzeba by usunąć z rodzica – regal_I.polka_1.kontener_A.pojemnik_a1 – i dodać do nowego rodzica, przy czym nowy rodzic NIE ZAWSZE byłby pojemnikiem umieszczonym w kontenerze (bo pojemnik może stać na półce), co dodatkowo komplikuje nam operację (nie jest ona powtarzalna).

Programista, który projektował bazę danych dla magazynu, zdecydował się więc na inne rozwiązanie. Każdy element – czy to półka, kontener, pojemnik, czy produkt – posiada ID i przypisanego rodzica. Elementy te stanowią płaską strukturę: są obiektami umieszczonymi w tablicy.

const stock = [
    {
        id: 1,
        type: "rack",
        indication: "I",
    },
    {
        id: 2,
        type: "rack",
        indication: "II",
    },
    {
        id: 3,
        type: "rack",
        indication: "III",
    },
    {
        id: 4,
        type: "shelf",
        indication: "1A0C",
        parent: 1
    },
    {
        id: 5,
        type: "shelf",
        indication: "2A0C",
        parent: 1
    },
    {
        id: 6,
        type: "shelf",
        indication: "1B1E",
        parent: 2
    },
    {
        id: 7,
        type: "container",
        indication: "Ad-1R",
        parent: 4
    },
    {
        id: 8,
        type: "container",
        indication: "Ab-1Ra",
        parent: 4
    },
    {
        id: 9,
        type: "container",
        indication: "Ad-2R",
        parent: 5
    },
    {
        id: 10,
        type: "box",
        indication: "X-9rc",
        parent: 6
    },
    {
        id: 11,
        type: "box",
        indication: "X-4ah",
        parent: 8
    },
    {
        id: 12,
        type: "box",
        indication: "X-4bh",
        parent: 8
    },
    {
        id: 13,
        type: "product",
        indication: "X-4ah__13",
        parent: 11
    },
    {
        id: 14,
        type: "product",
        indication: "X-4ah__14",
        parent: 11
    },
    {
        id: 15,
        type: "product",
        indication: "X-4bh__15",
        parent: 12
    },
    {
        id: 16,
        type: "product",
        indication: "X-4bh__16",
        parent: 12
    },
];

Teraz wystarczy, że wybranemu kontenerowi, pojemnikowi czy produktowi zmienimy ID rodzica – i gotowe. Nie musimy przejmować się tym, jakich ma i będzie mieć „przodków” (jaką półkę, jaki regał itd.).

 Generowanie drzewa za pomocą rekurencji

Przejdźmy teraz do naszego przykładu z rekurencją w JavaScripcie. Raz w roku odbywa się inwentaryzacja magazynu. Trzeba wydrukować zestawienie. Musimy więc wygenerować strukturę z odpowiednimi zagnieżdżeniami, które będą odzwierciedlać lokalizację elementów.

Rozwiązanie za pomocą rekurencji będzie się prezentować jak poniżej (znajdziesz je w repozytorium na GitHubie, a działanie podejrzysz na stronie z GitHub Pages).

startFromRoot(stock);

function startFromRoot(data) {
    const parentEl = document.querySelector('ul'); // wyszukaj w drzewie DOM element <ul>, do którego trafią elementy z bazy danych
    data.forEach(root => {
        if (!root.parent) {
            // jeśli element nie ma właściwości .parent, stwórz z niego osobny element <li>
            // taki element jest korzeniem, czyli od niego rozchodzą się gałęzie (dzieci)
            generateTree(root, data, parentEl); // zagnieżdżaj w nim jego dzieci
        }
    });
}

function generateTree(item, data, destinationEl) {
    // stwórz element <li> dla pojedynczego elementu i umieść go w rodzicu
    const itemEl = document.createElement('li');
    itemEl.innerText = `${item.type}: ${item.indication}`;
    destinationEl.appendChild(itemEl);

    // sprawdź, czy element ma przypisane dzieci
    const children = data.filter(potentialChild => {
        return potentialChild.parent && potentialChild.parent === item.id;
    });

    if (children.length > 0) {
        // jeśli ma dzieci, to stwórz nową <ul> i umieść ją w elemencie <li>
        const ulElNested = document.createElement('ul');
        itemEl.appendChild(ulElNested);

        children.forEach(child => {
            generateTree(child, data, ulElNested); // zagnieżdżaj w elemencie jego dzieci
        });
    }
}

Jeśli komentarze utrudniają Ci zrozumienie kodu, otwórz plik bez komentarzy.

Pomińmy teraz tworzenie elementów HTML dla wyświetlenia listy na stronie i omówmy logikę zagnieżdżania dzieci.

W naszym rozwiązaniu zaczynamy działanie od elementów, które nie mają przypisanego rodzica (u nas są to regały). Potem w funkcji rekurencyjnej generateTree() sprawdzamy, czy regały mają dzieci (u nas to półki). Jeśli mają, to dla każdej półki sprawdzamy, czy z kolei ona ma dzieci (i tu uwaga: mogą to być zarówno kontenery, jak i pojemniki – dzięki naszemu rozwiązaniu nie jesteśmy uzależnieni od typu rodzica). Jeśli półka ma dzieci, to przechodzimy do jej kontenerów/pojemników i znów sprawdzamy, czy one też mają dzieci. Wszystko to dzieje się dzięki ponownym wywołaniom funkcji generateTree() przez samą siebie.

Gdy docieramy do produktu (który przecież nie ma dzieci), nie dochodzi już do kolejnego wywołania funkcji generateTree(). Zamiast tego interpreter JavaScriptu wraca „wyżej”, czyli do kolejnego elementu tablicy, po której iterujemy za pomocą metody forEach(). Wygląda to np. tak:

1. znajdź pierwszy regał (element bez rodzica) -> czy regał ma dzieci? -> ma
2. weź półkę regału -> czy półka ma dzieci? -> ma
3. weź kontener z półki -> czy kontener ma dzieci? -> ma
4. weź pojemnik z kontenera -> czy pojemnik ma dzieci? -> ma
5. weź produkt z pojemnika -> czy produkt ma dzieci -> nie ma (koniec iteracji, załóżmy, że to jedyny produkt w pojemniku)
6. weź kolejny pojemnik z kontenera -> czy pojemnik ma dzieci? -> nie ma (koniec iteracji, załóżmy, że kontener miał dwa pojemniki, w tym drugi był pusty)
7. weź kolejny kontener z półki -> czy kontener ma dzieci? -> ma [powtarzamy schemat zagnieżdżania dla każdego kontenera (punkty 3-7) aż dochodzimy do końca iteracji – gdy nie ma już więcej kontenerów na półce]
8. weź kolejną półkę regału -> czy półka ma dzieci? -> ma [powtarzamy schemat zagnieżdżania dla każdej półki (punkty 2-8) aż dochodzimy do końca iteracji – gdy nie ma już więcej półek na regale]
9. znajdź kolejny regał (element bez rodzica) -> czy regał ma dzieci? -> ma [powtarzamy schemat zagnieżdżania dla każdego regału (punkty 1-9) aż dochodzimy do końca iteracji – gdy nie ma już żadnych regałów, program kończy pracę]

W sumie przypomina to działania pracownika, który sprawdza stany magazynowe 😉

Chcesz sprawdzić, czy nasze rozwiązanie działa bez względu na kolejność obiektów w tablicy? Możesz te elementy pomieszać za pomocą poniższego kodu (wystarczy, że odkomentujesz linię nr 100):

stock.sort(() => (Math.random() > 0.5 ? 1 : -1));

Zauważysz pewnie, że zagnieżdżenia tworzą się prawidłowo, lecz regały zmieniły kolejność. Możesz w ramach zadania dodatkowego stworzyć kod, który będzie je ustawiał w odpowiedniej kolejności.

Znasz już działanie rekurencji i możesz ją stosować np. tam, gdzie rozwiązanie za pomocą pętli będzie mniej czytelne, a struktura danych nie zagrozi stworzeniem zbyt dużego stosu wywołań (pamiętaj, że kończy się to obniżeniem wydajności lub błędem). Choć początkowo zrozumienie funkcji samowywołującej się może sprawiać problemy, warto zgłębić ten temat – czasem bowiem pojawia się na rekrutacji.