Silnia rekurencyjnie w Pythonie i JavaScript - jak działa?

Przy obliczaniu silni łatwo zauważyć, że ten sam problem powtarza się dla coraz mniejszej liczby. To właśnie dobry moment, aby zastosować rekurencję i napisać funkcję, która wywołuje samą siebie. Pokażę, jak obliczyć silnię rekurencyjnie, prześledzić działanie programu oraz uniknąć błędów związanych z przypadkiem bazowym, ujemnymi liczbami i przepełnieniem.

Na czym polega silnia i rekurencja

Silnia liczby naturalnej n, oznaczana jako n!, jest iloczynem wszystkich dodatnich liczb całkowitych od 1 do n. Przykładowo 4! = 4 · 3 · 2 · 1 = 24. Szczególny przypadek stanowi 0! = 1, ponieważ ta wartość pozwala zachować spójność wielu wzorów matematycznych.

Definicję można zapisać krócej jako n! = n · (n - 1)!. Funkcja dla liczby 5 nie musi więc od razu mnożyć pięciu wartości. Wystarczy, że obliczy 5 · silnia(4), a funkcja wywołana dla 4 zrobi to samo dla liczby 3.

Każda funkcja rekurencyjna potrzebuje dwóch elementów. Pierwszym jest przypadek bazowy, który kończy działanie. Drugim jest przypadek rekurencyjny, czyli wywołanie tej samej funkcji z argumentem zbliżającym się do wartości bazowej.

Jak napisać funkcję krok po kroku

Najpierw trzeba zdecydować, dla jakich danych funkcja ma działać. Silnia w podstawowej wersji jest określona dla liczb całkowitych nieujemnych, dlatego liczby ujemne powinny zostać odrzucone zamiast prowadzić do nieskończonej rekurencji.

Przykład w Pythonie wygląda tak:

def silnia(n):
    if not isinstance(n, int):
        raise TypeError("Podaj liczbę całkowitą")

    if n < 0:
        raise ValueError("Silnia nie jest zdefiniowana dla liczb ujemnych")

    if n == 0:
        return 1

    return n * silnia(n - 1)

print(silnia(5))  # 120

Najważniejsza jest ostatnia linia funkcji. Dla argumentu 5 program oblicza 5 · silnia(4). Dla argumentu 1 powstaje wywołanie 1 · silnia(0), a silnia z zera zwraca 1. W tym momencie dalsze wywołania nie są już potrzebne.

Warunek n == 0 można zastąpić warunkiem n <= 1. Oba podejścia dają poprawny wynik dla wartości 0 i 1, ale jawne wskazanie zera często lepiej pokazuje matematyczną definicję problemu.

Wersja w JavaScript

W środowisku webowym podobną funkcję można napisać w JavaScript. Poniższy przykład korzysta z typu BigInt, dzięki czemu wynik nie jest ograniczony do zwykłego zakresu typu Number.

function silnia(n) {
  if (!Number.isSafeInteger(n)) {
    throw new TypeError("Podaj bezpieczną liczbę całkowitą");
  }

  if (n < 0) {
    throw new RangeError("Silnia nie jest zdefiniowana dla liczb ujemnych");
  }

  if (n === 0) {
    return 1n;
  }

  return BigInt(n) * silnia(n - 1);
}

console.log(silnia(5).toString()); // 120

Litera n po liczbie oznacza wartość typu BigInt. Trzeba pamiętać, że BigInt i Number nie powinny być mieszane w jednym działaniu bez jawnej konwersji. To częsty błąd w JavaScript, szczególnie gdy część danych pochodzi z formularza.

Co dzieje się podczas obliczeń dla liczby 5

Rekurencja może wydawać się abstrakcyjna, dopóki nie rozpiszemy kolejnych wywołań. Dla argumentu 5 funkcja schodzi w dół aż do przypadku bazowego, a dopiero później wykonuje mnożenie.

silnia(5)
= 5 * silnia(4)
= 5 * 4 * silnia(3)
= 5 * 4 * 3 * silnia(2)
= 5 * 4 * 3 * 2 * silnia(1)
= 5 * 4 * 3 * 2 * 1 * silnia(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120

W pierwszej fazie rośnie stos wywołań funkcji. Program zapamiętuje, że po zakończeniu silnia(4) trzeba jeszcze pomnożyć wynik przez 5. Gdy pojawi się wartość 1, wywołania wracają w odwrotnej kolejności i obliczenia są domykane.

To rozdzielenie na „zejście” i „powrót” jest jedną z najważniejszych rzeczy do zrozumienia. Samo wywołanie rekurencyjne nie zwraca od razu ostatecznego wyniku, ponieważ każde wcześniejsze wywołanie czeka na rezultat kolejnego.

Rekurencja czy pętla

Silnię można obliczyć także iteracyjnie, czyli za pomocą pętli. W praktycznych programach często jest to rozwiązanie rozsądniejsze, ponieważ nie zajmuje stosu wywołań i zwykle ma mniejszy narzut wykonania.

def silnia_iteracyjnie(n):
    if n < 0:
        raise ValueError("Silnia nie jest zdefiniowana dla liczb ujemnych")

    wynik = 1

    for liczba in range(2, n + 1):
        wynik *= liczba

    return wynik

Moim zdaniem rekurencja jest świetna do nauki sposobu myślenia algorytmicznego, ale nie ma sensu stosować jej automatycznie w produkcyjnym kodzie do tak prostego obliczenia. Jeśli liczy się odporność na duże argumenty i przewidywalne zużycie pamięci, pętla zwykle wygrywa.

Typowe błędy i ograniczenia

Brak przypadku bazowego

Funkcja, która zawsze wywołuje samą siebie, nie ma sposobu na zakończenie pracy. Przykład return n * silnia(n - 1) bez dodatkowego warunku prowadzi do coraz mniejszych wartości i w końcu do błędu przepełnienia stosu.

Nieprawidłowa obsługa zera

Jeżeli program zwraca 0 dla 0!, dalsze obliczenia będą błędne. Dla przykładu 1! powinno być równe 1 · 0!, więc przypadek bazowy musi zwracać 1, a nie 0.

Liczby ujemne

Dla argumentu -1 wywołanie silnia(-1) przechodziłoby do silnia(-2), potem do silnia(-3) i tak dalej. Sprawdzenie wartości przed rekurencją jest więc nie tylko walidacją danych, ale także ochroną przed nieskończonym ciągiem wywołań.

Przeczytaj również: Aplikacja natywna - Kiedy warto? Przewodnik dla początkujących

Przepełnienie typu liczbowego

Silnia rośnie bardzo szybko. Już 10! wynosi 3 628 800, a 20! to 2 432 902 008 176 640 000. W językach korzystających ze stałej szerokości liczb całkowity wynik może przestać być poprawny po przekroczeniu zakresu danego typu.

Python automatycznie obsługuje bardzo duże liczby całkowite, ale nadal obowiązuje ograniczenie głębokości rekurencji. W JavaScript warto rozważyć BigInt, a w C++ odpowiednią bibliotekę do dużych liczb, jeśli wynik ma wykraczać poza zakres standardowych typów.

Jak sprawdzić, czy rozwiązanie działa poprawnie

Dobre ćwiczenie nie kończy się na wpisaniu jednego przykładu. Ja zaczynam od przypadków granicznych, bo właśnie one najszybciej pokazują, czy funkcja ma poprawny przypadek bazowy i walidację danych.

• silnia(0) powinno zwrócić 1.
• silnia(1) powinno zwrócić 1.
• silnia(5) powinno zwrócić 120.
• silnia(10) powinno zwrócić 3 628 800.
• Argument ujemny powinien wywołać kontrolowany błąd.
• Tekst lub liczba zmiennoprzecinkowa powinny zostać odrzucone, jeśli funkcja wymaga liczby całkowitej.

Można też sprawdzić zgodność wersji rekurencyjnej i iteracyjnej dla kilku wartości. Taki prosty test porównawczy pomaga wykryć pomyłkę w warunku zakończenia albo w zakresie pętli, zanim funkcja trafi do większego programu.

Od prostego ćwiczenia do dobrego nawyku

Rekurencyjne obliczanie silni jest małym zadaniem, ale uczy kilku rzeczy przydatnych w większych projektach. Pokazuje, jak rozbić problem na mniejszy problem tego samego typu, jak zaplanować warunek zakończenia i jak analizować koszt pamięci, a nie tylko sam wynik.

Najprostsza reguła brzmi tak: funkcja musi przy każdym wywołaniu zbliżać się do przypadku bazowego, a dane wejściowe trzeba sprawdzić przed rozpoczęciem obliczeń. Gdy te dwa warunki są spełnione, rozwiązanie jest poprawne dydaktycznie, natomiast wybór między rekurencją i pętlą zależy już od ograniczeń konkretnego programu.