Dijkstra miał rację — rekurencja nie powinna być trudna

Niemal każdy język programowania ma rozmaite struktury sterujące, takie jak bloki if…else/switch…case, oraz struktury iteracyjne, takie jak pętle for i while. Większość początkujących programistów najpierw poznaje struktury iteracyjne.

Ale jest jeszcze jedna bardzo potężna struktura sterująca: rekurencja. Rekurencja to jedna z najważniejszych idei w informatyce, ale zwykle uchodzi za jedną z trudniejszych do przyswojenia części programowania. Książki wprowadzają ją często dużo później niż struktury iteracyjne.

Liczba pytań w sieci o to, dlaczego rekurencja czy programy rekurencyjne są tak trudne do zrozumienia, może sprawiać wrażenie, że rekurencja faktycznie jest techniką zaawansowaną. Ale nie musi być trudna.

Choć rozpoznanie rekurencyjnej natury problemu i wymyślenie rozwiązania wymaga pewnego wyczucia, można je wyrobić praktyką. Ten artykuł przedstawi i wyjaśni szereg zagadnień oraz pomysłów, które pomogą Ci przy ćwiczeniu zadań rekurencyjnych.

Po co używać rekurencji?

Może słyszałeś ten żart — żeby zrozumieć rekurencję, musisz najpierw zrozumieć rekurencję. Współgra on z powszechną definicją rekurencji jako funkcji, która wywołuje samą siebie.

Taka definicja może sugerować, że takie wywołania prowadzą do nieskończonego cofania się, ale poprawnie zdefiniowane rozwiązanie rekurencyjne nigdy nie jest nieskończone. Dzieje się tak dlatego, że rekurencyjna podfunkcja nigdy nie rozwiązuje dokładnie tego samego problemu co funkcja pierwotna, lecz zawsze prostszą wersję problemu pierwotnego. W pewnym momencie ta wersja staje się na tyle prosta, że da się ją rozwiązać od ręki — i wtedy rekurencja się kończy.

Prowadzi nas to do najważniejszego zastosowania rekurencji: używaj rekurencji, by zmniejszyć złożoność problemu, przed którym stoisz.

Zobaczmy przykład. Załóżmy, że chcesz obliczyć sumę wszystkich elementów tablicy, która zawiera zagnieżdżone podtablice. Tak, by gdy funkcja otrzyma następujące zagnieżdżone tablice:

[1,[11,42,[8, 1], 4, [22,21]]]

zwróciła sumę wszystkich elementów:

1+11+42+8+1+4+22+21 = 110.

Sztuczka polega na tym, by wskazać i rozwiązać prostszy problem, a następnie wyrazić problem pierwotny w kategoriach tego prostszego przypadku. Potem stosujesz rekurencję, aż ten przypadek zostanie osiągnięty i rozwiązany. A wraz z nim rozwiązane zostają wszystkie pozostałe kroki rekurencyjne aż po problem pierwotny.

Najprostszym przypadkiem naszego problemu jest tablica bez zagnieżdżonych podtablic. Dla takiej tablicy funkcja obliczeniowa może wyglądać tak:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        result += a[i];
    }
    return result;
}

assert.equal(sum([1, -5, 100]), 96);

Mamy teraz funkcję sum, która przyjmuje tablicę i zwraca sumę wszystkich jej elementów. Rozwiążmy pierwotny, trudniejszy problem. Mówi on, że niektóre elementy mogą być tablicami, podczas gdy bieżąca implementacja zakłada, że wszystkie elementy tablicy są liczbami. Wystarczy więc sprawdzić, czy element jest tablicą, a jeśli tak — mamy już funkcję sum, żeby obliczyć sumę wszystkich elementów tej tablicy. Podrasujmy trochę naszą funkcję sum:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        if (Array.isArray(a[i])) {
            result += sum(a[i])
        } else {
            result += a[i];
        }
    }
    return result;
}

assert.equal(sum([1,[11,42,[8, 1], 4, [22,21]]]), 110);

I to wszystko. Najpierw rozwiązaliśmy prostszy problem, a potem użyliśmy tego rozwiązania do rozwiązania trudniejszego. To zadanie da się rozwiązać także iteracyjnie, ale wychodzi to znacznie bardziej skomplikowanie, bo musielibyśmy zagnieżdżać pętle for, nie wiedząc, jak głębokie jest zagnieżdżenie. Nieznana liczba zagnieżdżonych pętli to wspólna cecha wszystkich problemów rekurencyjnych z natury i powinna być dla Ciebie podpowiedzią, że potrzebne jest rozwiązanie rekurencyjne.

Poza pomocą w zmniejszaniu złożoności problemu rekurencja ma jeszcze jedną ważną zdolność — możliwość nawracania (backtracking). Problemy wymagające nawracania zwykle dotyczą przechodzenia drzew i grafów, na przykład różnego rodzaju labiryntów. Takie problemy rozwiązuje się krok po kroku. Oto ogólny algorytm:

1. Jeśli bieżący krok algorytmu jest rozwiązaniem problemu — zwróć wynik.
2. Jeśli bieżący krok nie jest rozwiązaniem — sprawdź, dokąd jeszcze można stąd pójść.
3. Jeśli zostały jakieś miejsca — wybierz jedno i idź tam sprawdzić, czy to rozwiązanie.
4. Jeśli nie ma dokąd iść — nawróć.

Zobaczmy przykład. Dane jest następujące drzewo:

Jest reprezentowane jako węzły z dziećmi:

let tree = {
    name: 'A',
    value: 4,
    children: [
        {
            name: 'B', value: 7,
            children: [{name: 'C', value: 9, children: []}]
        },
        {
            name: 'D', value: 11,
            children: [{name: 'E', value: 9, children: []}]
        },
        {name: 'F', value: 55, children: []},
        {
            name: 'G', value: 65,
            children: [
                {name: 'H', value: 21, children: []},
                {name: 'I', value: 33, children: []}
            ]
        }
    ]
};

A zadaniem jest znaleźć węzeł o wartości 21.

Postąpimy tak:

1. Najpierw sprawdzamy węzeł A.
2. Jeśli to nie to, czego szukamy, możemy przejść do B, a potem do C.
3. Żaden węzeł na naszej drodze nie spełnia równości i nie ma stąd dokąd pójść, więc nawracamy do A.
4. Następnie sprawdzamy D i E. Nic z tego.
5. Nawrót. F.
6. Znowu nawrót. Sprawdzamy G. Wciąż nic.

Ale wciąż mamy dokąd pójść. Wreszcie H. To ten węzeł, którego szukaliśmy.

A oto prosta implementacja:

function find(node, value) {
    if (node.value === value) {
        return node;
    } else {
        for (let i = 0; i < node.children.length; i++) {
            let found = find(node.children[i], value);
            if (found !== null) {
                return found;
            }
        }

        return null;
    }
}

assert.equal(find(tree, 21).name, 'H');

Projektowanie rozwiązania

Częstym błędem początkujących przy projektowaniu rozwiązania problemu rekurencyjnego jest próba wyobrażenia sobie, co dzieje się wewnątrz wywołania rekurencyjnego, zamiast po prostu zaufać, że zwróci ono poprawny wynik. W problemie z zagnieżdżonymi tablicami, patrząc na rozwiązanie

if (Array.isArray(a[i])) {
    result += sum(a[i])

nie zastanawiaj się, co się stanie, gdy funkcja sum zostanie wykonana. To nie jest użyteczny sposób myślenia o rekurencji. Zamiast tego zaufaj, że zwróci ona poprawną sumę wszystkich elementów tablicy a[i]. Ponadto nie myśl o programie rekurencyjnym jak o serii kroków wykonania i nie próbuj odtwarzać drzewa wykonania w głowie. Przy niektórych złożonych problemach będzie to bardzo trudne i nie pomoże Ci dojść do rozwiązania.

Gdy zabierasz się za rozwiązanie, pomyśl, jak problem pierwotny da się przedstawić jako prostszy problem plus kilka dodatkowych operacji. Wskazanie tego prostszego problemu to prawdopodobnie najtrudniejsza część rozwiązywania problemu rekurencyjnego. Przy łatwych problemach, jak te z powyższych przykładów, bywa to trywialne, ale przy wielu trudniejszych dostrzeżenie wzorca wymaga wprawy. Im więcej ćwiczysz, tym lepiej Ci to wychodzi.

Gdy już wskażesz prostszy problem, przejdź do znalezienia najprostszego problemu, jaki Twoja funkcja będzie musiała rozwiązać. Ten najprostszy problem nazywa się przypadkiem bazowym. Zwykle przybiera postać warunku kończącego rekurencję. W naszych wcześniejszych przykładach ma on formę pętli for sprawdzającej, czy w tablicy zostały elementy (sum) albo czy węzeł ma dzieci (find). Czasem, w łatwych problemach, prostszy problem, który pomaga rozwiązać ten pierwotny, jest zarazem przypadkiem bazowym. Ale nie dotyczy to trudniejszych problemów, jak słynna „wieża Hanoi”:

Masz trzy pręty i pewną liczbę krążków różnej wielkości, które można przekładać na dowolny pręt. Zaczynasz z krążkami ułożonymi w schludny stos, rosnąco według rozmiaru, na jednym pręcie. Celem gry jest przeniesienie wszystkich krążków na wieżę 3. Ale możesz przekładać tylko jeden krążek naraz i nie możesz położyć większego krążka na mniejszym.

Prostszy problem, który trzeba tu dostrzec, wygląda tak:

1. Przenieś n-1 krążków na pręt pomocniczy.

2. Przenieś ostatni krążek z pręta źródłowego na docelowy.

3. Gdy ostatni krążek jest już przeniesiony, pozostałe krążki z pręta pomocniczego można przenieść na docelowy.

Ważne, żeby nie rozpisywać sobie kroków przenoszenia krążków na pręt pomocniczy, tylko założyć, że jeśli już tam są, to możemy przenieść ostatni krążek, a potem pozostałe. Napiszmy kod dla tego przypadku:

function move(n, src, aux, dest) {

    // przenosimy wszystkie krążki poza ostatnim z pręta źródłowego
    // na pomocniczy; dlatego w wywołaniu funkcji pręty aux i dest
    // są zamienione miejscami, żeby aux stał się docelowym
    move(n - 1, src, dest, aux);

    // przenosimy ostatni krążek z pręta źródłowego na docelowy
    dest.push(src.pop());

    // przenosimy pozostałe krążki z pręta pomocniczego na docelowy;
    // dlatego w wywołaniu funkcji pręty aux i src są zamienione
    // miejscami, żeby pomocniczy stał się źródłowym
    move(n - 1, aux, src, dest);
}

Skoro mamy już prostszy problem, musimy znaleźć najprostszy przypadek bazowy. I chyba łatwo go wypatrzyć:

Jeśli został jeden krążek, po prostu przenieś go na pręt docelowy:

function move(n, src, aux, dest) {
    if (n === 1) {
        dest.push(src.pop());
    } else {
        move(n - 1, src, dest, aux);
        dest.push(src.pop());
        move(n - 1, aux, src, dest);
    }
}

I to jest przypadek bazowy kończący rekurencję. A nie jest to ten sam prostszy problem, który pomaga rozwiązać problem pierwotny.

Spróbuj teraz zastosować to, czego się nauczyłeś, do poniższych zadań:

1. Znajdowanie sumy zagnieżdżonych tablic

Napisz funkcję, która sumuje wszystkie liczby w tablicy mogącej zawierać zagnieżdżone podtablice. Nie używaj pętli.

2. Generowanie ciągów binarnych

Napisz funkcję, która generuje wszystkie możliwe kombinacje 1 i 0 dla n bitów. Na przykład jeśli funkcja otrzyma 2 jako liczbę bitów, powinna wyprodukować następujące 4 kombinacje: 00,01,10,11. Nie możesz używać żadnych operatorów matematycznych.

Próbując wymyślić rozwiązanie, staraj się myśleć przez wskazanie prostszego problemu i przypadku bazowego, a nie przez konstruowanie krok po kroku przepływu wykonania. Spróbuj też wyobrazić sobie, że patrzysz właśnie na krok pośredni: jaką następną operację należy wykonać, żeby zbliżyć się do rozwiązania?

Rozwiązania i wyjaśnienia znajdziesz na końcu artykułu.

Optymalizacja wywołań ogonowych

Być może słyszałeś termin stos wywołań. Używa się go głównie podczas debugowania, żeby zrozumieć, skąd została wywołana funkcja, która wygenerowała błąd. Jeśli więc masz w pliku index.js taki kod:

function a(n) {
    let a = 1;
    return a + n;
}

function b(n) {
    let b = 5;
    let value = a(n);  // linia B
    return b + value;
}

function c() {
    let c = 3;
    let v = b(c);  // linia C
    console.log(v);
}

c();  // linia A

i postawisz punkt wstrzymania wewnątrz a, stos wywołań będzie wyglądał mniej więcej tak:

a() (return to: {b(): B}, locals: {a=1, n=3})
b() (return to: {c(): C}, locals: {b=5, n=3})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Mówi on, że funkcja a została wywołana z b, a b z c. Stąd bierze się nazwa „stos wywołań” — stos wywołań funkcji. Każdy wpis na stosie nazywa się ramką stosu (stack frame) i przechowuje między innymi: zmienne lokalne oraz adres powrotu (dokąd wrócić, gdy bieżąca funkcja się zakończy). Ważne, że liczba i rozmiar ramek na stosie są ograniczone. Oznacza to, że jeśli będziesz wywoływać funkcje wystarczająco długo, dostaniesz błąd przepełnienia stosu. Ten limit nie jest stały, różni się między środowiskami i zależy od rozmiaru ramki każdej pojedynczej funkcji.

Funkcja rekurencyjna wielokrotnie wywołuje samą siebie, więc istnieje potencjalne ryzyko błędu przepełnienia stosu. Na przykład ta prosta funkcja rekurencyjna oblicza silnię liczby:

function fact(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * fact(n - 1);
}

Jeśli przekażemy dość dużą liczbę, na przykład 100 000, w większości środowisk dostaniemy błąd. Tej rekurencyjnej implementacji silni zwykle nie poleca się jako przykładu rekurencji, bo ten sam wynik znacznie łatwiej osiągnąć rozwiązaniami iteracyjnymi. Poza potencjalnym błędem przepełnienia stosu to rozwiązanie rekurencyjne obciąża wydajność, zużywając dodatkowe ramki stosu, a w konsekwencji więcej pamięci.

Mimo to dla wielu języków funkcyjnych, takich jak Lisp i Scheme, jest to rozwiązanie preferowane. Jak więc unikają one wspomnianych problemów? Odpowiedzią jest optymalizacja wywołań ogonowych. Spójrzmy na przerobiony kod powyższego przykładu ze stosem:

function a(n, p) {
    let a = 1;
    return a + n + p;
}

function b(n) {
    let b = 5;
    return a(n, b);
}

function c() {
    let c = 3;
    let v = b(c);  // linia C
    console.log(v);
}

c();  // linia A

Teraz wydaje się, że nie ma sensu tworzyć ramki stosu dla funkcji b, bo wszystko, co ona robi, to wywołanie a i nie wykonuje potem żadnej akcji. Kompilator to zauważa i optymalizuje takie wywołania, nie tworząc ramki stosu dla b. Zoptymalizowany stos wygląda teraz tak:

a() (return to: {c(): C}, locals: {a=1, n=3, p=5})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Spójrz na różnice w funkcji b przed przeróbką i po niej:

// bez optymalizacji wywołań ogonowych
let value = a(n);
return b + value;

// z optymalizacją wywołań ogonowych
return a(n, b);

Główna różnica polega więc na tym, że po powrocie z funkcji a nie ma już żadnej akcji. Przepiszmy naszą funkcję silni tak, by kwalifikowała się do optymalizacji wywołań ogonowych:

function fact(acc, n) {
    if (n === 1) {
        return acc;
    } else {
        return fact(acc * n, n - 1);
    }
}

Jak widzisz, zamiast brać wartość zwracaną i obliczać wynik po powrocie z wywołania rekurencyjnego, obliczamy go najpierw i przekazujemy dalej do kolejnego wywołania rekurencyjnego. Tak więc w pierwszej, niezoptymalizowanej ogonowo implementacji najpierw wykonujesz wywołania rekurencyjne, a potem bierzesz zwróconą wartość i obliczasz wynik. Przy takim podejściu nie dostaniesz wyniku obliczeń, dopóki nie wrócisz z każdego wywołania rekurencyjnego.

Żeby przekształcić implementację w rekurencję ogonową, najpierw wykonujesz obliczenia, a potem wywołanie rekurencyjne, przekazując wyniki bieżącego kroku do następnego kroku rekurencyjnego. Skutkuje to tym, że ostatnie wywołanie rekurencyjne po prostu zwraca nagromadzoną wartość, gdy warunek zostanie spełniony. W gruncie rzeczy wartość zwracana przez dowolny krok rekurencyjny jest taka sama jak wartość zwracana przez kolejne wywołanie rekurencyjne. Konsekwencją jest to, że gdy tylko jesteś gotów wykonać następny krok rekurencyjny, bieżąca ramka stosu przestaje być potrzebna.

W niektórych językach funkcyjnych optymalizację wywołań ogonowych można uzyskać także przez styl przekazywania kontynuacji (CPS) — czyli przez callbacki. Przy użyciu callbacków instrukcje return nie są potrzebne, więc kompilator może zoptymalizować wywołania rekurencyjne. Choć JavaScript bardzo dobrze wspiera model callbacków, obecnie nie wspiera optymalizacji wywołań ogonowych przez CPS.

Rozwiązania

A więc pierwsze zadanie:

Napisz funkcję, która sumuje wszystkie liczby w tablicy mogącej zawierać zagnieżdżone podtablice. Nie używaj pętli.

Możemy zacząć od wskazania prostszego problemu — czyli tablicy bez zagnieżdżonych podtablic. Zadajmy te same pytania, żeby rozwiązać ten prostszy problem:

1. Jaki jest prostszy problem? Prostszy problem to sytuacja, w której mam sumę n-1 elementów i muszę tylko dodać do niej bieżący element.
2. Jaki jest najprostszy przypadek? Najprostszy przypadek to brak elementów do dodania — zwróć 0.

Oto implementacja:

function sum(a, i) {
    if (i < 0) {
        return 0;
    } else {
        return a[i] + sum(a, i - 1);
    }
}

let input = [1, 2, 0, 3];
assert.equal(sum(input, input.length - 1), 6);

Rozwiązaliśmy więc prostszy problem bez zagnieżdżonych tablic. Teraz musimy uwzględnić tablice zagnieżdżone. Trzeba sprawdzić, czy element jest tablicą, a jeśli tak — po prostu uruchomić na nim funkcję sum. Ważne, żeby nie zapomnieć pobrać sumy elementów zagnieżdżonej podtablicy i dodać jej do wyniku. Oto ostateczna implementacja:

function sum(a, i) {
    if (i < 0) {
        return 0;
    }

    let current = a[i];

    if (Array.isArray(a[i])) {
        current = sum(a[i], a[i].length - 1);
    }

    return current + sum(a, i - 1);
}

let input = [1, 2, [1, 2], 3, [5]];
assert.equal(sum(input, input.length - 1), 14);

Przyjrzyjmy się teraz drugiemu zadaniu:

Napisz funkcję, która generuje wszystkie możliwe kombinacje 1 i 0 dla n bitów. Na przykład jeśli funkcja otrzyma 2 jako liczbę bitów, powinna wyprodukować następujące 4 kombinacje: 00,01,10,11. Nie możesz używać żadnych operatorów matematycznych.

Jaki jest tu najprostszy przypadek? Musimy wyprodukować ciągi tylko dla jednego bitu. Będą to dwa ciągi: 1 i 0. Mamy więc funkcję, która wypisuje 1 i 0, jeśli liczba bitów wynosi 1. Zapiszmy ją, zakładając, że istnieje globalna zmienna a przechowująca tablicę:

function binary(n) {
    if (n === 1) {

        a[n - 1] = 0;
        console.log(a.join(''));

        a[n - 1] = 1;
        console.log(a.join(''));
    }
}

Bieżąca implementacja zawiera zduplikowaną instrukcję console.log, więc możemy poprawić kod, wykonując wypisywanie jako ostatnią operację, gdy nie ma już bitów do ustawienia. Przepiszmy implementację:

function binary(i) {
    if (i === 0) {
        console.log(a.join(''));
    } else {
        a[i - 1] = 0;
        binary(i - 1);
        a[i - 1] = 1;
        binary(i - 1);
    }
}

Zobaczmy teraz, jakie kombinacje wyjdą dla 2 bitów.

Zaczynamy więc bez ustawionych bitów. Potem ustawiamy bit n na 0. Potem robimy to samo dla bitu n-1. Podążamy za tym wzorcem, aż nie zostanie już bitów do ustawienia. Wypisujemy kombinację i nawracamy o jeden poziom wyżej. Następnie ustawiamy bit n na 1. Widać wyraźnie, że na każdym kroku funkcja zajmuje się tylko ustawieniem bieżącego bitu i wywołaniem funkcji do obsługi pozostałych bitów.

A to właśnie mamy już w naszej implementacji obsługującej jeden bit. Jak się okazuje, przez samą przeróbkę przypadku bazowego doszliśmy do rozwiązania, które zadziała dla dowolnej liczby bitów.