Kurs JavaScript i TypeScript · Moduł 12: Programowanie funkcyjne

Rekurencja w programowaniu funkcyjnym

6 min czytania ·
W tej lekcji4

Taksonomia dinozaurów to drzewo: Dinosauria dzielą się na dwie wielkie grupy, te na mniejsze, a na końcach gałęzi wiszą gatunki. Nie wiesz z góry, ile poziomów ma takie drzewo, więc nie wiesz, ile pętli zagnieździć. Potrzebna jest funkcja, która obsłuży jeden węzeł, a z jego dziećmi poradzi sobie, wywołując samą siebie.

Rekurencja to technika, w której funkcja wywołuje samą siebie. W Parku Jurajskim rekurencja jest jak eksploracja drzewa genealogicznego dinozaurów - aby poznać pełne pochodzenie gatunku, musisz cofać się pokolenie po pokoleniu, aż dotrzesz do najstarszego przodka.

Podstawy rekurencji

Każda funkcja rekurencyjna potrzebuje dwóch elementów:

  1. Przypadek bazowy (base case) - warunek kończący rekurencję
  2. Przypadek rekurencyjny - wywołanie funkcji z uproszczonym problemem

Każde wywołanie przebiega według tego samego schematu: sprawdź warunek bazowy i jeśli jest spełniony, od razu zwróć wynik, a jeśli nie, uprość problem i wywołaj funkcję ponownie na mniejszej części. Klasyczny przykład to silnia, czyli iloczyn liczb od 1 do n:

// Klasyczny przykład - silnia
function factorial(n) {
  // Przypadek bazowy
  if (n <= 1) return 1;
  // Przypadek rekurencyjny
  return n * factorial(n - 1);
}

factorial(5); // 5 * 4 * 3 * 2 * 1 = 120

Warunek n <= 1 zatrzymuje schodzenie, a każde wywołanie zmniejsza n o jeden, więc zawsze do niego dotrzemy. Rozpiszmy, co dzieje się na stosie wywołań (call stack) dla factorial(5):

// Wizualizacja wywołań:
// factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1)
//           return 1     <- przypadek bazowy
//         return 2
//       return 6
//     return 24
//   return 120

Żadne mnożenie nie wykonuje się, dopóki nie dotrzemy do przypadku bazowego, a wcześniejsze wywołania czekają na stosie, każde ze swoją wartością n. Bez przypadku bazowego funkcja wywoływałaby się w nieskończoność, aż silnik przerwie program błędem przepełnienia stosu: w Chrome i Node.js to RangeError: Maximum call stack size exceeded, w Firefoksie InternalError: too much recursion.

Rekurencja z drzewiastymi strukturami

Rekurencja jest naturalna przy przetwarzaniu drzewiastych struktur danych - jak hierarchia gatunków. Każdy węzeł ma nazwę i tablicę children, a liść to węzeł z pustą tablicą dzieci:

const dinoTaxonomy = {
  name: 'Dinosauria',
  children: [
    {
      name: 'Saurischia',
      children: [
        { name: 'Theropoda', children: [
          { name: 'T-Rex', children: [] },
          { name: 'Velociraptor', children: [] },
        ]},
        { name: 'Sauropoda', children: [
          { name: 'Brachiosaurus', children: [] },
        ]},
      ],
    },
    {
      name: 'Ornithischia',
      children: [
        { name: 'Triceratops', children: [] },
        { name: 'Stegosaurus', children: [] },
      ],
    },
  ],
};

Drzewo ma cztery poziomy, ale funkcje, które napiszemy, nie muszą tego wiedzieć. Szukanie gatunku działa tak: jeśli bieżący węzeł to cel, zwracamy go, a jeśli nie, pytamy po kolei każde dziecko:

// Rekurencyjne przeszukiwanie drzewa
function findSpecies(node, target) {
  if (node.name === target) return node;
  for (const child of node.children) {
    const found = findSpecies(child, target);
    if (found) return found;
  }
  return null;
}

findSpecies(dinoTaxonomy, 'Velociraptor');
// { name: 'Velociraptor', children: [] }

Przypadki bazowe są tu dwa: trafienie (node.name === target) oraz liść, dla którego pętla nie wykona się ani razu, więc funkcja zwróci null. Drzewo zostaje nietknięte, bo funkcja tylko czyta. Rekurencja świetnie łączy się też z reduce, na przykład przy liczeniu węzłów:

// Rekurencja + reduce: liczymy wszystkie węzły drzewa
function countNodes(node) {
  return 1 + node.children.reduce((sum, child) => sum + countNodes(child), 0);
}

countNodes(dinoTaxonomy); // 10

Przypadek bazowy jest tu ukryty: dla liścia reduce na pustej tablicy zwraca wartość początkową 0, więc liść liczy się jako 1 i rekurencja się kończy. Ten sam szkielet posłuży do zbierania nazw liści czy budowania ścieżki od korzenia do gatunku. Ścieżkę przekazuj jako nową tablicę ([...path, node.name]), a nie przez push, żeby gałęzie nie psuły sobie nawzajem wyników.

Rekurencja vs iteracja

W FP rekurencja zastępuje pętle. Każdą pętlę można zapisać rekurencyjnie. Porównaj dwie wersje sumowania wag dinozaurów:

// Iteracja - sumowanie tablicy
function sumIterative(arr) {
  let total = 0;
  for (const num of arr) {
    total += num;
  }
  return total;
}

// Rekurencja - sumowanie tablicy
function sumRecursive(arr) {
  if (arr.length === 0) return 0;
  const [head, ...tail] = arr;
  return head + sumRecursive(tail);
}

// Oba dają ten sam wynik
const weights = [8000, 150, 56000, 2500];
sumIterative(weights); // 66650
sumRecursive(weights); // 66650

Zapis const [head, ...tail] = arr to destrukturyzacja: head dostaje pierwszy element, a tail nową tablicę z resztą. Przypadkiem bazowym jest pusta tablica o sumie 0, a weights zostaje nietknięta. JavaScript nie jest jednak stworzony pod głęboką rekurencję: każde wywołanie zajmuje ramkę stosu, a tail to za każdym razem nowa kopia tablicy, więc przy kilku tysiącach elementów stos może się skończyć. Moja rada: płaskie listy sumuj przez reduce, a rekurencję zostaw dla struktur zagnieżdżonych, takich jak drzewa.

Optymalizacja ogonowa (Tail Call Optimization)

Rekurencja może prowadzić do przepełnienia stosu (stack overflow) przy głębokich wywołaniach. Rekurencja ogonowa to taka, w której wywołanie rekurencyjne jest ostatnią operacją funkcji. Po jego powrocie nie ma już nic do zrobienia, więc silnik mógłby zwolnić bieżącą ramkę stosu - na tym polega optymalizacja wywołań ogonowych (TCO). Porównaj obie formy silni:

// Zwykła rekurencja - każde wywołanie czeka na wynik następnego
function factorialNormal(n) {
  if (n <= 1) return 1;
  return n * factorialNormal(n - 1); // musi czekać na wynik
}

// Rekurencja ogonowa - akumulator przekazuje wynik
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // ostatnia operacja
}

W factorialNormal po powrocie z rekurencji trzeba jeszcze pomnożyć wynik przez n, więc wywołanie nie jest ostatnią operacją. factorialTail niesie cząstkowy wynik w akumulatorze, dzięki czemu wywołanie stoi na samym końcu. Uczciwie trzeba dodać: specyfikacja ES2015 przewiduje takie wywołania w trybie ścisłym, ale zaimplementował je tylko silnik Safari. W Chrome, Node.js i Firefoksie factorialTail(100000) nadal przepełni stos, więc w JavaScript rekurencja ogonowa to przede wszystkim czytelny wzorzec z akumulatorem, a nie ochrona przed błędem.

Wzorzec akumulatora przydaje się także poza liczbami. flattenDeep spłaszcza dowolnie zagnieżdżoną listę, przekazując w głąb tę samą tablicę wyników:

// Praktyczny przykład - spłaszczanie zagnieżdżonej struktury
function flattenDeep(arr, result = []) {
  for (const item of arr) {
    if (Array.isArray(item)) {
      flattenDeep(item, result);
    } else {
      result.push(item);
    }
  }
  return result;
}

const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
flattenDeep(nested);
// ['Rex', 'Blue', 'Charlie', 'Brachio', 'Stego']

Array.isArray rozpoznaje zagnieżdżoną tablicę i wtedy schodzimy poziom niżej. To nie jest rekurencja ogonowa, bo wywołanie siedzi w pętli, a push zmienia tablicę result. To jednak lokalny akumulator: domyślny parametr tworzy nową tablicę przy każdym wywołaniu z zewnątrz, więc nested zostaje nietknięta. W nowoczesnym JavaScript ten sam efekt da nested.flat(Infinity). W następnej lekcji zajmiemy się kopiowaniem zagnieżdżonych struktur bez mutacji.

Pamiętaj: rekurencja to wędrówka po drzewie genealogicznym - każdy krok przybliża Cię o jedno pokolenie do celu, a przypadek bazowy mówi, kiedy się zatrzymać.

Kod do tej lekcji: index.js
// Rekurencja w programowaniu funkcyjnym
console.log("=== Park Jurajski - Drzewo Genealogiczne Gatunkow ===\n");

// --- PRZYKLAD 1: Podstawowa rekurencja ---
console.log("--- Silnia (factorial) ---");

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log("5! =", factorial(5));
console.log("10! =", factorial(10));

// --- PRZYKLAD 2: Drzewo taksonomiczne ---
console.log("\n--- Drzewo taksonomiczne ---");

const taxonomy = {
  name: "Dinosauria",
  children: [
    {
      name: "Saurischia",
      children: [
        { name: "Theropoda", children: [
          { name: "T-Rex", children: [] },
          { name: "Velociraptor", children: [] },
          { name: "Spinosaurus", children: [] },
        ]},
        { name: "Sauropoda", children: [
          { name: "Brachiosaurus", children: [] },
          { name: "Diplodocus", children: [] },
        ]},
      ],
    },
    {
      name: "Ornithischia",
      children: [
        { name: "Triceratops", children: [] },
        { name: "Stegosaurus", children: [] },
        { name: "Ankylosaurus", children: [] },
      ],
    },
  ],
};

// Rekurencyjne wyswietlanie drzewa
function printTree(node, indent = 0) {
  console.log(" ".repeat(indent) + "- " + node.name);
  node.children.forEach((child) => printTree(child, indent + 2));
}

printTree(taxonomy);

// Rekurencyjne wyszukiwanie
function findSpecies(node, target) {
  if (node.name === target) return node;
  for (const child of node.children) {
    const found = findSpecies(child, target);
    if (found) return found;
  }
  return null;
}

console.log("\nZnaleziony:", findSpecies(taxonomy, "Velociraptor") ? "TAK" : "NIE");
console.log("Nieistniejacy:", findSpecies(taxonomy, "Dragon") ? "TAK" : "NIE");

// Rekurencyjne zliczanie lisci
function countLeaves(node) {
  if (node.children.length === 0) return 1;
  return node.children.reduce((sum, child) => sum + countLeaves(child), 0);
}
console.log("Liczba gatunkow:", countLeaves(taxonomy));

// --- PRZYKLAD 3: Rekurencyjna suma ---
console.log("\n--- Rekurencyjna suma vs iteracja ---");

function sumRecursive(arr) {
  if (arr.length === 0) return 0;
  const [head, ...tail] = arr;
  return head + sumRecursive(tail);
}

const weights = [8000, 150, 56000, 2500, 9000];
console.log("Suma rekurencyjna:", sumRecursive(weights));

// --- PRZYKLAD 4: Splaszczanie struktury ---
console.log("\n--- Splaszczanie struktury ---");

function flattenDeep(arr) {
  return arr.reduce((result, item) => {
    if (Array.isArray(item)) {
      return [...result, ...flattenDeep(item)];
    }
    return [...result, item];
  }, []);
}

const nested = [["Rex", ["Blue", "Charlie"]], "Brachio", [["Stego"]]];
console.log("Splaszczone:", flattenDeep(nested));

// --- PRZYKLAD 5: Rekurencja ogonowa ---
console.log("\n--- Rekurencja ogonowa ---");

function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);
}

console.log("Tail 10! =", factorialTail(10));
console.log("Tail 20! =", factorialTail(20));

Hasła z dokumentacji w tej lekcji

Widzisz błąd w tej lekcji?

Sprawdź się

Odpowiedz na pytania z tej lekcji. Wybierz odpowiedź, a od razu zobaczysz, czy jest poprawna.

  1. 1. Dlaczego przypadek bazowy (base case) jest konieczny w funkcji rekurencyjnej?

  2. 2. Czym jest rekurencja ogonowa (tail recursion)?

Zadania praktyczne w grze

  • Układanie w pionie

    Ułóż elementy poprawnej funkcji rekurencyjnej w kolejności wykonywania:

  • Edytor kodu

    Zaimplementuj countSpecies, totalCount, findPath i collectLeaves rekurencyjnie.

  • Klikanie w kolejności

    Ułóż elementy rekurencyjnej funkcji silni:

  1. PytaniePrzypadek bazowy rekurencji
  2. Ułóż w kolejnościElementy funkcji rekurencyjnej
  3. Zadanie z kodemRekurencja z drzewem gatunków
  4. PytanieRekurencja ogonowa
  5. Kliknij w kolejnościSkładnia rekurencyjnej silni

Przydatne artykuły