Rekurencja w programowaniu funkcyjnym

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

1// Klasyczny przyklad - 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
10
11// Wizualizacja wywolan:
12// factorial(5)
13//   5 * factorial(4)
14//     4 * factorial(3)
15//       3 * factorial(2)
16//         2 * factorial(1)
17//           return 1     <- przypadek bazowy
18//         return 2
19//       return 6
20//     return 24
21//   return 120

Rekurencja z drzewiastymi strukturami

Rekurencja jest naturalna przy przetwarzaniu drzewiastych struktur danych - jak hierarchia gatunków:

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};
25
26// Rekurencyjne przeszukiwanie drzewa
27function findSpecies(node, target) {
28  if (node.name === target) return node;
29  for (const child of node.children) {
30    const found = findSpecies(child, target);
31    if (found) return found;
32  }
33  return null;
34}
35
36findSpecies(dinoTaxonomy, 'Velociraptor');
37// { name: 'Velociraptor', children: [] }

Rekurencja vs iteracja

W FP rekurencja zastępuje pętle. Każdą pętlę można zapisać rekurencyjnie:

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 daja ten sam wynik
18const weights = [8000, 150, 56000, 2500];
19sumIterative(weights); // 66650
20sumRecursive(weights); // 66650

Optymalizacja ogonowa (Tail Call Optimization)

Rekurencja może prowadzić do przepełnienia stosu (stack overflow) przy głębokich wywołaniach. Rekurencja ogonowa rozwiązuje ten problem:

1// Zwykla rekurencja - kazde wywolanie czeka na wynik nastepnego
2function factorialNormal(n) {
3  if (n <= 1) return 1;
4  return n * factorial(n - 1); // musi czekac 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}
12
13// Praktyczny przyklad - splaszczanie zagniezdzonej struktury
14function flattenDeep(arr, result = []) {
15  for (const item of arr) {
16    if (Array.isArray(item)) {
17      flattenDeep(item, result);
18    } else {
19      result.push(item);
20    }
21  }
22  return result;
23}
24
25const nested = [['Rex', ['Blue', 'Charlie']], 'Brachio', [['Stego']]];
26flattenDeep(nested);
27// ['Rex', 'Blue', 'Charlie', 'Brachio', 'Stego']