Rekurencja w programowaniu funkcyjnym

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:

1// Klasyczny przykład - silnia
2function factorial(n) {
3  // Przypadek bazowy
4  if (n <= 1) return 1;
5  // Przypadek rekurencyjny
6  return n * factorial(n - 1);
7}
8
9factorial(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):

1// Wizualizacja wywołań:
2// factorial(5)
3//   5 * factorial(4)
4//     4 * factorial(3)
5//       3 * factorial(2)
6//         2 * factorial(1)
7//           return 1     <- przypadek bazowy
8//         return 2
9//       return 6
10//     return 24
11//   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:

1const dinoTaxonomy = {
2  name: 'Dinosauria',
3  children: [
4    {
5      name: 'Saurischia',
6      children: [
7        { name: 'Theropoda', children: [
8          { name: 'T-Rex', children: [] },
9          { name: 'Velociraptor', children: [] },
10        ]},
11        { name: 'Sauropoda', children: [
12          { name: 'Brachiosaurus', children: [] },
13        ]},
14      ],
15    },
16    {
17      name: 'Ornithischia',
18      children: [
19        { name: 'Triceratops', children: [] },
20        { name: 'Stegosaurus', children: [] },
21      ],
22    },
23  ],
24};

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:

1// Rekurencyjne przeszukiwanie drzewa
2function findSpecies(node, target) {
3  if (node.name === target) return node;
4  for (const child of node.children) {
5    const found = findSpecies(child, target);
6    if (found) return found;
7  }
8  return null;
9}
10
11findSpecies(dinoTaxonomy, 'Velociraptor');
12// { 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:

1// Rekurencja + reduce: liczymy wszystkie węzły drzewa
2function countNodes(node) {
3  return 1 + node.children.reduce((sum, child) => sum + countNodes(child), 0);
4}
5
6countNodes(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:

1// Iteracja - sumowanie tablicy
2function sumIterative(arr) {
3  let total = 0;
4  for (const num of arr) {
5    total += num;
6  }
7  return total;
8}
9
10// Rekurencja - sumowanie tablicy
11function sumRecursive(arr) {
12  if (arr.length === 0) return 0;
13  const [head, ...tail] = arr;
14  return head + sumRecursive(tail);
15}
16
17// Oba dają ten sam wynik
18const weights = [8000, 150, 56000, 2500];
19sumIterative(weights); // 66650
20sumRecursive(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:

1// Zwykła rekurencja - każde wywołanie czeka na wynik następnego
2function factorialNormal(n) {
3  if (n <= 1) return 1;
4  return n * factorialNormal(n - 1); // musi czekać na wynik
5}
6
7// Rekurencja ogonowa - akumulator przekazuje wynik
8function factorialTail(n, accumulator = 1) {
9  if (n <= 1) return accumulator;
10  return factorialTail(n - 1, n * accumulator); // ostatnia operacja
11}

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:

1// Praktyczny przykład - spłaszczanie zagnieżdżonej struktury
2function flattenDeep(arr, result = []) {
3  for (const item of arr) {
4    if (Array.isArray(item)) {
5      flattenDeep(item, result);
6    } else {
7      result.push(item);
8    }
9  }
10  return result;
11}
12
13const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
14flattenDeep(nested);
15// ['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ć.

1// Rekurencja w programowaniu funkcyjnym
2console.log("=== Park Jurajski - Drzewo Genealogiczne Gatunkow ===\n");
3
4// --- PRZYKLAD 1: Podstawowa rekurencja ---
5console.log("--- Silnia (factorial) ---");
6
7function factorial(n) {
8  if (n <= 1) return 1;
9  return n * factorial(n - 1);
10}
11
12console.log("5! =", factorial(5));
13console.log("10! =", factorial(10));
14
15// --- PRZYKLAD 2: Drzewo taksonomiczne ---
16console.log("\n--- Drzewo taksonomiczne ---");
17
18const taxonomy = {
19  name: "Dinosauria",
20  children: [
21    {
22      name: "Saurischia",
23      children: [
24        { name: "Theropoda", children: [
25          { name: "T-Rex", children: [] },
26          { name: "Velociraptor", children: [] },
27          { name: "Spinosaurus", children: [] },
28        ]},
29        { name: "Sauropoda", children: [
30          { name: "Brachiosaurus", children: [] },
31          { name: "Diplodocus", children: [] },
32        ]},
33      ],
34    },
35    {
36      name: "Ornithischia",
37      children: [
38        { name: "Triceratops", children: [] },
39        { name: "Stegosaurus", children: [] },
40        { name: "Ankylosaurus", children: [] },
41      ],
42    },
43  ],
44};
45
46// Rekurencyjne wyswietlanie drzewa
47function printTree(node, indent = 0) {
48  console.log(" ".repeat(indent) + "- " + node.name);
49  node.children.forEach((child) => printTree(child, indent + 2));
50}
51
52printTree(taxonomy);
53
54// Rekurencyjne wyszukiwanie
55function findSpecies(node, target) {
56  if (node.name === target) return node;
57  for (const child of node.children) {
58    const found = findSpecies(child, target);
59    if (found) return found;
60  }
61  return null;
62}
63
64console.log("\nZnaleziony:", findSpecies(taxonomy, "Velociraptor") ? "TAK" : "NIE");
65console.log("Nieistniejacy:", findSpecies(taxonomy, "Dragon") ? "TAK" : "NIE");
66
67// Rekurencyjne zliczanie lisci
68function countLeaves(node) {
69  if (node.children.length === 0) return 1;
70  return node.children.reduce((sum, child) => sum + countLeaves(child), 0);
71}
72console.log("Liczba gatunkow:", countLeaves(taxonomy));
73
74// --- PRZYKLAD 3: Rekurencyjna suma ---
75console.log("\n--- Rekurencyjna suma vs iteracja ---");
76
77function sumRecursive(arr) {
78  if (arr.length === 0) return 0;
79  const [head, ...tail] = arr;
80  return head + sumRecursive(tail);
81}
82
83const weights = [8000, 150, 56000, 2500, 9000];
84console.log("Suma rekurencyjna:", sumRecursive(weights));
85
86// --- PRZYKLAD 4: Splaszczanie struktury ---
87console.log("\n--- Splaszczanie struktury ---");
88
89function flattenDeep(arr) {
90  return arr.reduce((result, item) => {
91    if (Array.isArray(item)) {
92      return [...result, ...flattenDeep(item)];
93    }
94    return [...result, item];
95  }, []);
96}
97
98const nested = [["Rex", ["Blue", "Charlie"]], "Brachio", [["Stego"]]];
99console.log("Splaszczone:", flattenDeep(nested));
100
101// --- PRZYKLAD 5: Rekurencja ogonowa ---
102console.log("\n--- Rekurencja ogonowa ---");
103
104function factorialTail(n, acc = 1) {
105  if (n <= 1) return acc;
106  return factorialTail(n - 1, n * acc);
107}
108
109console.log("Tail 10! =", factorialTail(10));
110console.log("Tail 20! =", factorialTail(20));