Kurs JavaScript i TypeScript · Moduł 12: Programowanie funkcyjne
Rekurencja w programowaniu funkcyjnym
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:
- Przypadek bazowy (base case) - warunek kończący rekurencję
- 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 = 120Warunek 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); // 10Przypadek 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); // 66650Zapis 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. Dlaczego przypadek bazowy (base case) jest konieczny w funkcji rekurencyjnej?
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: