Javascript – Przykład funkcji rekurencyjnej

Czym jest funkcja rekurencyjna

Funkcja rekurencyjna to funkcja, która wywołuje samą siebie. Robi to, dopóki nie osiągnie określonego warunku zatrzymania (tzw. warunku bazowego).

Dzięki temu można rozwiązywać problemy, które polegają na powtarzaniu tych samych działań na mniejszych fragmentach danych – sumowanie elementów w zagnieżdżonej tablicy – gdy tablica zawiera kolejne tablice w środku, przeszukiwanie drzewa – np. struktury kategorii, menu lub systemu plików czy nawigacja po zagnieżdżonych obiektach JSON.

Kluczowa zasada działania:

1. Funkcja wywołuje samą siebie z nowymi (mniejszymi) danymi.
2. Warunek bazowy zatrzymuje dalsze wywołania, żeby uniknąć nieskończonej pętli.

Przykład funkcji rekurencyjnej, który sumuje wszystkie elementy w tablicy:

function sumArray(array) {
    let sum = 0;

    for (const element of array) {
        if (Array.isArray(element)) {
          // If the element is an array, call the function again (recursion)
          sum += sumArray(element);
        } else {
          // If it's a number, add it to the total sum
          sum += element;
        }
    }

    return sum;
}

// Example usage:
const data = [1, [2, [3, 4], 5], 6];
console.log(sumArray(data)); // Output: 21

Funkcja sumArray przechodzi po wszystkich elementach tablicy. Jeśli element jest kolejną tablicą – wywołuje samą siebie (rekurencja). Jeśli element jest liczbą – dodaje go do sumy. Proces powtarza się, aż dotrze do wszystkich najgłębiej zagnieżdżonych liczb. Kod działa niezależnie od tego, jak głęboko zagnieżdżone są tablice – nie trzeba pisać wielu pętli.

Nieskończona pętla wywołań

Używając funkcji rekurencyjnej należy uważać na ryzyko powstania pętli nieskończonej (infinite loop). Może ona pojawić się, kiedy brakuje poprawnego warunku zatrzymania albo gdy ten warunek nigdy nie zostaje spełniony. Jeśli funkcja ciągle wywołuje samą siebie, nie osiągając momentu, w którym powinna się zatrzymać, będzie działała bez końca, aż przeglądarka lub interpreter (np. PHP) przerwie działanie z błędem typu stack overflow (przepełnienie stosu).