Rekurencja w Informatyce: Kompleksowy Przewodnik

W świecie informatyki i matematyki istnieje potężne narzędzie, które pozwala na eleganckie i zwięzłe rozwiązywanie złożonych problemów: rekurencja. Chociaż na pierwszy rzut oka może wydawać się nieco skomplikowana, jej zrozumienie otwiera drzwi do głębszego pojmowania algorytmów i struktury danych. Jest to koncepcja fundamentalna, często wymagana na egzaminach maturalnych z informatyki i niezwykle ceniona przez doświadczonych programistów.

Czym właściwie jest rekurencja i jak ją zastosować w praktyce? Mówiąc najprościej, rekurencja to proces, w którym funkcja lub procedura odwołuje się do samej siebie w trakcie swojego działania. Wyobraź sobie lustra ustawione naprzeciwko siebie – każde odbicie odwołuje się do poprzedniego, tworząc nieskończony ciąg. Podobnie działa funkcja rekurencyjna: aby rozwiązać dany problem, dzieli go na mniejsze, podobne podproblemy i wywołuje samą siebie, aby je rozwiązać, aż do osiągnięcia prostego przypadku bazowego, który można rozwiązać bezpośrednio.

Jak zbudować wzór rekurencyjny?

Tworzenie wzoru rekurencyjnego opiera się na dwóch kluczowych elementach. Po pierwsze, musimy zdefiniować przypadek bazowy (lub warunek brzegowy). Jest to najprostszy przypadek problemu, który może być rozwiązany bez dalszego wywoływania funkcji. Jest to punkt, w którym rekurencja się zatrzymuje, zapobiegając nieskończonemu wywoływaniu funkcji. Bez niego program nigdy by się nie zakończył, co doprowadziłoby do błędu. Po drugie, potrzebujemy kroku rekurencyjnego (lub przypadku ogólnego), który definiuje, jak większy problem jest redukowany do mniejszego, podobnego problemu, aż do osiągnięcia przypadku bazowego.

Przykładowo, rozważmy prosty ciąg zdefiniowany rekurencyjnie: a(1) = 1 oraz a(n) = a(n-1) + 4 dla n > 1. Tutaj a(1) = 1 jest naszym przypadkiem bazowym. Mówi nam, że pierwszy wyraz ciągu to 1. Krok rekurencyjny a(n) = a(n-1) + 4 informuje nas, że każdy kolejny wyraz ciągu (dla n > 1) jest równy poprzedniemu wyrazowi plus 4. Aby obliczyć a(5), musimy znać a(4), do obliczenia a(4) potrzebujemy a(3) i tak dalej, aż do a(1). Nie możemy po prostu "wpisać" numeru szukanego wyrazu; musimy "cofać się" do poprzednich wyrazów. To jest esencja rekurencji: problem jest rozwiązywany poprzez odwoływanie się do jego mniejszych instancji.

Rekurencja w informatyce: Co to jest i jak działa?

W informatyce rekurencja (zwana również rekursją) oznacza, że funkcja wywołuje samą siebie w trakcie swojego działania. Nawet pojedyncze wywołanie procedury przez samą siebie wystarczy, aby uznać ją za rekurencyjną. Jest to potężna technika programistyczna, która pozwala na pisanie eleganckiego i zwięzłego kodu, szczególnie w przypadku problemów, które mają naturalnie rekurencyjną strukturę.

Przykład: Obliczanie silni rekurencyjnie

Jednym z najczęściej podawanych przykładów funkcji rekurencyjnej jest obliczanie silni. Silnia liczby naturalnej n (oznaczana jako n!) to iloczyn wszystkich liczb całkowitych od 1 do n. Na przykład 4! = 1 * 2 * 3 * 4 = 24. Definicja iteracyjna jest prosta, ale rekurencyjna definicja silni jest równie intuicyjna:

• Przypadek bazowy: 1! = 1
• Krok rekurencyjny: n! = n * (n - 1)! dla n > 1

Spójrzmy, jak działa obliczanie 3! za pomocą rekurencji:

1. Wywołujemy Silnia(3). Warunek bazowy (n=1) nie jest spełniony. Przechodzimy do kroku rekurencyjnego: 3 * Silnia(2).
2. Aby obliczyć Silnia(2), wywołujemy ją. Warunek bazowy (n=1) nie jest spełniony. Przechodzimy do kroku rekurencyjnego: 2 * Silnia(1).
3. Aby obliczyć Silnia(1), wywołujemy ją. Warunek bazowy (n=1) jest spełniony. Funkcja zwraca 1.
4. Wracamy do obliczania Silnia(2). Mamy już wynik Silnia(1) (czyli 1). Obliczamy 2 * 1 = 2. Funkcja Silnia(2) zwraca 2.
5. Wracamy do obliczania Silnia(3). Mamy już wynik Silnia(2) (czyli 2). Obliczamy 3 * 2 = 6. Funkcja Silnia(3) zwraca 6.

Ten proces polega na "zawieszaniu" bieżących obliczeń i wywoływaniu kolejnych instancji funkcji, aż do osiągnięcia przypadku bazowego. Dopiero wtedy wyniki są "odwijane" w odwrotnej kolejności, aż do pierwotnego wywołania. To pokazuje, jak rekurencja znacznie upraszcza zapis kodu dla problemów o takiej naturze.

Rodzaje rekurencji

Rekurencję można klasyfikować na kilka sposobów, w zależności od sposobu wywoływania funkcji i wzrostu liczby wywołań.

Podział według sposobu wywołania:

• Rekurencja bezpośrednia: Funkcja wywołuje samą siebie bezpośrednio wewnątrz swojego ciała (np. funkcja F wywołuje F). Jest to najczęściej spotykane rozwiązanie.
• Rekurencja pośrednia: Funkcja jest wywoływana przez inną funkcję, która z kolei (bezpośrednio lub pośrednio) wywołuje tę pierwszą funkcję (np. funkcja A wywołuje B, a funkcja B wywołuje A).

Podział według wzrostu liczby wywołań:

• Rekurencja liniowa (single recursion): Charakteryzuje się liniowym wzrostem liczby wywołań rekurencyjnych w zależności od wielkości danych wejściowych. W czasie pojedynczego wykonania funkcji następuje tylko jedno wywołanie rekurencyjne (np. funkcja A wywołuje A, która ponownie wywołuje A). Przykładem jest wspomniana funkcja silnia.
• Rekurencja nieliniowa (multiple recursion): W czasie pojedynczego wywołania funkcji następuje większa liczba kolejnych wywołań rekurencyjnych (np. funkcja A wywołuje A w dwóch różnych miejscach). Ogólna liczba wywołań rośnie znacznie szybciej niż liniowo, często wykładniczo. Ze względu na większe skomplikowanie, może prowadzić do problemów z wydajnością i zużyciem pamięci. Klasycznym przykładem jest rekurencyjne obliczanie ciągu Fibonacciego.

Rekurencja ogonowa

Szczególnym typem jest rekurencja ogonowa (tail recursion), która następuje wtedy, gdy ostatnią instrukcją danej funkcji jest jej kolejne wywołanie. Jest to bardzo ważna cecha, ponieważ pozwala na optymalizację kodu. Kompilator może przekształcić takie wywołanie rekurencyjne w zwykłą pętlę (iterację), co eliminuje konieczność utrzymywania zapisanych danych w stosie dla każdego wywołania funkcji. Zamiast tego, przekazywane są tylko argumenty, bez zapisywania dodatkowych danych. To sprawia, że rekurencja ogonowa jest równie wydajna jak iteracja i pozwala uniknąć problemów z przepełnieniem stosu.

Przykład: Ciąg Fibonacciego

Ciąg Fibonacciego to sekwencja liczb naturalnych, w której każda liczba jest sumą dwóch poprzednich (z wyjątkiem pierwszych dwóch). Zazwyczaj zaczyna się od 0, 1, 1, 2, 3, 5, 8, .... Jest to doskonały przykład problemu, który można rozwiązać zarówno iteracyjnie, jak i rekurencyjnie.

Iteracyjne obliczanie Fibonacciego polega na użyciu pętli, która śledzi dwie poprzednie wartości, aby obliczyć następną. Jest to zazwyczaj bardziej wydajne pod względem pamięci i czasu dla dużych liczb.

Rekurencyjny zapis ciągu Fibonacciego wygląda następująco:

• Przypadki bazowe: fib(1) = 1, fib(2) = 1
• Krok rekurencyjny: fib(n) = fib(n-1) + fib(n-2) dla n > 2

W przypadku obliczania fib(5), funkcja wywoła fib(4) i fib(3). Następnie fib(4) wywoła fib(3) i fib(2), a fib(3) wywoła fib(2) i fib(1). Widać, że niektóre wartości (np. fib(3), fib(2)) są obliczane wielokrotnie. To jest cecha rekurencji nieliniowej i jest główną wadą prostego rekurencyjnego rozwiązania Fibonacciego.

Drzewo wywołań rekurencyjnych

Aby lepiej zrozumieć, jak działają wywołania rekurencyjne, często stosuje się drzewo wywołań rekurencyjnych. Jest to struktura graficzna, która wizualizuje kolejne wywołania rekurencyjne danej funkcji. Każdy węzeł w drzewie reprezentuje jedno wywołanie funkcji, a gałęzie wychodzące z węzłów wskazują na kolejne wywołania z wnętrza tej funkcji. Korzeń drzewa to początkowe wywołanie, a liście to przypadki bazowe, gdzie rekurencja się kończy. Analiza takiego drzewa pozwala na identyfikację powtarzających się obliczeń i zrozumienie złożoności algorytmu, co jest kluczowe dla optymalizacji.

Zalety i wady rekurencji

Chociaż rekurencja jest potężnym narzędziem, ma swoje mocne i słabe strony, które należy wziąć pod uwagę przy wyborze metody rozwiązywania problemu.

Zalety rekurencji:

• Zwięzły i czytelny kod: Dla pewnych algorytmów (jak silnia, czy operacje na drzewach i grafach) rekurencyjne rozwiązania są znacznie bardziej intuicyjne i krótsze niż ich iteracyjne odpowiedniki, co poprawia czytelność kodu.
• Możliwość dowodzenia poprawności (indukcja matematyczna): Algorytmy rekurencyjne często mają bezpośrednie przełożenie na dowody matematyczne za pomocą indukcji, co ułatwia weryfikację ich poprawności dla wszystkich przypadków problemu.
• Caching (memoizacja): Algorytmy rekurencyjne, zwłaszcza te z wielokrotnymi wywołaniami tych samych podproblemów (jak Fibonacci), mogą być zoptymalizowane za pomocą memoizacji. Polega to na zapamiętywaniu wyników już obliczonych podproblemów, aby uniknąć ponownego ich obliczania. To znacznie poprawia wydajność, ale wymaga dodatkowej pamięci na przechowywanie wyników.
• Brak modyfikacji globalnej pamięci: Rekurencyjne funkcje często operują wyłącznie na swoich "własnych" zmiennych lokalnych, co może zmniejszać ryzyko błędów związanych z manipulacją stanem globalnym programu.

Wady rekurencji:

• Pamięciochłonność: W wielu przypadkach użycie rekurencji może prowadzić do nadmiernego wykorzystywania stosu wywołań (pamięci). Każde wywołanie funkcji rekurencyjnej dodaje nową ramkę na stosie, co przy dużej liczbie zagnieżdżonych wywołań może doprowadzić do przepełnienia stosu (stack overflow), zwłaszcza przy dużych danych wejściowych.
• Mniejsza intuicyjność dla początkujących: Zrozumienie przepływu sterowania w funkcji rekurencyjnej wymaga pewnej wprawy i innego sposobu myślenia niż w przypadku pętli. Debugowanie rekurencyjnego kodu bywa trudniejsze.
• Niska wydajność: Częste wywoływanie funkcji i zarządzanie stosem wywołań wiąże się z pewnym narzutem czasowym. Dla wielu prostych problemów iteracyjne rozwiązania są po prostu szybsze i bardziej efektywne. Profesjonalni programiści często "unikają rekurencji, kiedy się da", szczególnie w systemach o wysokich wymaganiach wydajnościowych, chyba że problem ma naturalnie rekurencyjną strukturę i rekurencja ogonowa może być zastosowana lub problem jest optymalizowany przez memoizację.
• Ryzyko nieskończonej rekurencji: Niewłaściwie zdefiniowany przypadek bazowy lub brak gwarancji jego osiągnięcia może spowodować, że funkcja będzie wywoływać się w nieskończoność, co doprowadzi do awarii programu.

Kiedy używać rekurencji, a kiedy iteracji?

Wybór między rekurencją a iteracją (pętlami) zależy od natury problemu, wymagań wydajnościowych i czytelności kodu. Nie ma jednej uniwersalnej zasady, ale istnieją pewne wytyczne:

Zastosowanie rekurencji:

• Problem ma rekurencyjną naturę: Niektóre zagadnienia, takie jak algorytmy działające na strukturach drzewiastych (np. przeszukiwanie drzewa, operacje na grafach), naturalnie pasują do rekurencji, ponieważ problem można łatwo podzielić na mniejsze, identyczne podproblemy.
• Struktura danych jest rekurencyjna: Przetwarzanie danych o rekurencyjnej strukturze, np. drzewa binarne, listy zagnieżdżone czy grafy, jest często znacznie prostsze i bardziej eleganckie przy użyciu rekurencji.
• Możliwy jest podział na podobne podproblemy: Jeśli dany problem można łatwo rozbić na mniejsze podproblemy, które są praktycznie takie same jak problem oryginalny, rekurencja jest często idealnym rozwiązaniem, pozwalającym na eleganckie i zwięzłe wyrażenie algorytmu.

Zastosowanie iteracji:

• Problem jest prosty i liniowy: Dla prostych, sekwencyjnych zadań, takich jak sumowanie elementów listy czy iterowanie po tablicy, pętle są zazwyczaj bardziej efektywne i łatwiejsze do napisania.
• Potrzebna jest dokładna kontrola nad pamięcią: Iteracja daje programiście większą kontrolę nad zużyciem pamięci, ponieważ nie ma narzutu związanego ze stosem wywołań funkcji.
• Prostota i wydajność kodu jest kluczowa: Jeśli kod ma być czytany i utrzymywany przez wiele osób, a rekurencja nie jest absolutnie wymagana, iteracja często jest preferowana ze względu na jej niższy narzut i prostszą strukturę dla początkujących. W wielu przypadkach iteracja jest po prostu szybsza.

Przykłady algorytmów rekurencyjnych

Rekurencja znajduje szerokie zastosowanie w wielu algorytmach informatycznych. Oto lista popularnych przykładów:

• Silnia (Factorial)
• Ciąg Fibonacciego (Fibonacci Sequence)
• Suma elementów listy (Sum of List Elements)
• Wyszukiwanie binarne (Binary Search)
• Dzielenie całkowite z odejmowaniem (Integer Division with Subtraction)
• Szybkie potęgowanie (Fast Exponentiation)
• Sortowanie przez scalanie (Merge Sort)
• Sortowanie szybkie (QuickSort)
• Drzewo Binomialne (Binomial Tree)
• Wieże Hanoi (Tower of Hanoi)
• Algorytmy grafowe DFS/BFS (Graph Algorithms – DFS/BFS)
• Algorytm podziału zbioru (Subset Sum)
• Algorytm najdłuższego wspólnego podciągu (Longest Common Subsequence)
• Algorytm programowania dynamicznego (Dynamic Programming)
• Algorytmy drzewiaste AVL/Red-Black (AVL Tree/Red-Black Tree Algorithms)
• Algorytm rozwiązywania labiryntów (Maze Solving)

Zastosowanie rekurencji – przykład implementacji algorytmu Wieże Hanoi

Wieże Hanoi to klasyczny problem rekurencyjny, który doskonale ilustruje działanie rekurencji. Zadanie polega na przeniesieniu stosu n krążków z kolumny początkowej na kolumnę docelową, używając kolumny pomocniczej, z zachowaniem kilku zasad:

1. Krążki są ułożone w stosie w malejącej kolejności średnicy (największy na dole, najmniejszy na górze).
2. Tylko jeden krążek może zostać przeniesiony w danym czasie.
3. Krążek większy nigdy nie może leżeć na krążku mniejszym.
4. Celem jest przeniesienie wszystkich krążków z minimalną liczbą ruchów.

Algorytm rekurencyjny dla Wież Hanoi jest niezwykle elegancki:

1. Przenieś n-1 górnych krążków z kolumny początkowej na kolumnę pomocniczą, używając kolumny docelowej jako tymczasowej.
2. Przenieś największy (ostatni) krążek z kolumny początkowej na kolumnę docelową.
3. Przenieś n-1 krążków z kolumny pomocniczej na kolumnę docelową, używając kolumny początkowej jako tymczasowej.

A oto pseudokod funkcji hanoi(n, pkolumna, dkolumna, gkolumna):

• n: liczba krążków do przeniesienia
• pkolumna: nazwa kolumny początkowej
• dkolumna: nazwa kolumny docelowej
• gkolumna: nazwa kolumny pomocniczej

funkcja hanoi (n, pkolumna, dkolumna, gkolumna) jeżeli n = 1 wykonuj wypisz ("Przerzuc krazek z kolumny " + pkolumna + " na " + dkolumna) w przeciwnym razie hanoi (n-1, pkolumna, gkolumna, dkolumna) // Krok 1 wypisz ("Przerzuc krazek z kolumny " + pkolumna + " na " + dkolumna) // Krok 2 hanoi (n-1, gkolumna, dkolumna, pkolumna) // Krok 3 

Opis działania pseudokodu:

• Linia 5: Wywołaj funkcję hanoi rekurencyjnie dla n-1 krążków. Przenieś je z pkolumny na gkolumnę, używając dkolumny jako pomocniczej. To powoduje, że n-1 mniejszych krążków jest przenoszonych na kolumnę pomocniczą, zwalniając największy krążek na kolumnie początkowej.
• Linia 6: Po zakończeniu poprzedniego rekurencyjnego wywołania, największy krążek (ten o numerze n) jest przenoszony z pkolumny na dkolumnę. Ten ruch jest wypisywany.
• Linia 7: Wywołaj funkcję hanoi rekurencyjnie ponownie dla n-1 krążków. Przenieś je z gkolumny (gdzie teraz się znajdują) na dkolumnę, używając pkolumny jako pomocniczej. To przenosi pozostałe krążki na docelową kolumnę, umieszczając je na największym krążku.

Przykład wykonania dla 3 krążków (A, B, C)

Śledzenie wywołań dla hanoi(3, 'A', 'B', 'C'):

Hanoi(3, A, B, C) // Główne wywołanie Hanoi(2, A, C, B) // Krok 1: Przenieś 2 krążki z A na C (pomocniczo B) Hanoi(1, A, B, C) // Krok 1.1: Przenieś 1 krążek z A na B (pomocniczo C) Przerzuc krazek z kolumny A na B (warunek bazowy) Przerzuc krazek z kolumny A na C (Krok 2: Przenieś największy krążek z A na C) Hanoi(1, B, C, A) // Krok 1.3: Przenieś 1 krążek z B na C (pomocniczo A) Przerzuc krazek z kolumny B na C (warunek bazowy) Przerzuc krazek z kolumny A na B (Krok 2: Przenieś największy krążek z A na B) Hanoi(2, C, B, A) // Krok 3: Przenieś 2 krążki z C na B (pomocniczo A) Hanoi(1, C, A, B) // Krok 3.1: Przenieś 1 krążek z C na A (pomocniczo B) Przerzuc krazek z kolumny C na A (warunek bazowy) Przerzuc krazek z kolumny C na B (Krok 3.2: Przenieś największy krążek z C na B) Hanoi(1, A, B, C) // Krok 3.3: Przenieś 1 krążek z A na B (pomocniczo C) Przerzuc krazek z kolumny A na B (warunek bazowy)

Wcięcia pokazują zagnieżdżenie wywołań. Ten przykład doskonale obrazuje, jak rekurencja rozbija duży problem na mniejsze, identyczne podproblemy, aż do osiągnięcia przypadku bazowego, a następnie składa rozwiązania z powrotem.

Podsumowanie

Rekurencja to jedna z fundamentalnych i zarazem najbardziej eleganckich technik w programowaniu. Pozwala na zwięzłe i czytelne wyrażenie algorytmów dla problemów o naturalnie rekurencyjnej strukturze, takich jak operacje na drzewach, grafach czy klasyczne zagadki, jak Wieże Hanoi. Zrozumienie jej działania, w tym pojęć takich jak przypadek bazowy i krok rekurencyjny, jest kluczowe dla każdego aspirującego programisty i często pojawia się na egzaminach maturalnych z informatyki.

Mimo swoich zalet, rekurencja ma również wady, takie jak potencjalnie wysokie zużycie pamięci (przepełnienie stosu) i niższa wydajność w porównaniu do iteracji dla niektórych problemów. Dlatego ważne jest, aby wiedzieć, kiedy ją stosować. Dla problemów, które można łatwo zaimplementować iteracyjnie, pętle są często lepszym wyborem. Jednak w sytuacjach, gdy struktura problemu jest rekurencyjna, lub gdy zwięzłość i elegancja kodu są priorytetem, rekurencja staje się niezastąpionym narzędziem. Opanowanie tej techniki, wraz z jej optymalizacjami, takimi jak memoizacja czy rekurencja ogonowa, otwiera drogę do rozwiązywania bardziej złożonych problemów algorytmicznych i jest cenną umiejętnością w arsenale każdego programisty.

Najczęściej zadawane pytania o rekurencję w informatyce

Kiedy rekurencja sprawia problemy?

Rekurencja może sprawiać problemy głównie w dwóch sytuacjach: po pierwsze, gdy problem jest złożony i wymaga zbyt wielu zagnieżdżonych wywołań, co może doprowadzić do przepełnienia stosu (stack overflow). Stos wywołań ma ograniczoną pojemność, a każde wywołanie rekurencyjne zajmuje na nim miejsce. Po drugie, rekurencja może być mniej wydajna niż iteracja ze względu na narzut związany z zarządzaniem stosem i wywoływaniem funkcji. W niektórych przypadkach te same podproblemy są obliczane wielokrotnie, co prowadzi do niepotrzebnej pracy, chyba że zastosuje się optymalizacje takie jak memoizacja. Niewłaściwie zdefiniowany warunek brzegowy może również spowodować nieskończoną rekurencję, prowadzącą do awarii programu.

Jak zoptymalizować algorytmy rekurencyjne?

Najpopularniejszą techniką optymalizacji algorytmów rekurencyjnych, zwłaszcza tych z powtarzającymi się podproblemami (jak Fibonacci), jest memoizacja (caching). Polega ona na zapamiętywaniu wyników wcześniejszych wywołań danej funkcji rekurencyjnej (np. w tablicy lub mapie). Gdy funkcja jest wywoływana z argumentami, dla których wynik został już obliczony, zamiast ponownego obliczania, zwracana jest zapamiętana wartość. Inną formą optymalizacji jest przekształcenie rekurencji na rekurencję ogonową, co pozwala kompilatorom na optymalizację wywołań rekurencyjnych do zwykłych pętli, eliminując narzut stosu.

Co to jest metoda rekurencyjna?

Metoda rekurencyjna to po prostu inna nazwa dla funkcji rekurencyjnej lub procedury rekurencyjnej. Jest to blok kodu (funkcja, metoda, procedura), który w trakcie swojego działania wywołuje sam siebie, aby rozwiązać mniejsze instancje problemu, aż do osiągnięcia przypadku bazowego.

Czym różni się rekurencja od iteracji?

Główna różnica polega na sposobie rozwiązywania problemu:
Rekurencja: Funkcja rozwiązuje problem, dzieląc go na mniejsze, podobne podproblemy i wywołując samą siebie do ich rozwiązania. Wyniki z podproblemów są następnie łączone, aby uzyskać ostateczny wynik. Rekurencja opiera się na stosie wywołań funkcji.
Iteracja: Problem jest rozwiązywany za pomocą pętli (np. for, while), która powtarza zestaw instrukcji, modyfikując stan programu w każdej iteracji, aż do osiągnięcia końcowego wyniku. Iteracja nie używa stosu wywołań do śledzenia postępu, co często czyni ją bardziej efektywną pod względem pamięci i czasu.

Który algorytm jest rekurencyjny?

Algorytm jest rekurencyjny, jeśli zawiera w sobie wywołanie samego siebie. W kodzie rozpoznasz to po tym, że funkcja (lub procedura) o danej nazwie, np. mojaFunkcja(), wywołuje w swoim ciele mojaFunkcja(...). Przykłady algorytmów rekurencyjnych to wspomniana silnia, ciąg Fibonacciego, algorytmy sortowania takie jak Sortowanie przez Scalanie (Merge Sort) i Sortowanie Szybkie (QuickSort), przeszukiwanie drzew i grafów (DFS/BFS) czy algorytm Wieże Hanoi.

Jak obliczyć silnię za pomocą rekurencji?

Aby obliczyć silnię liczby n za pomocą rekurencji, potrzebujesz dwóch elementów:
1. Przypadek bazowy: Silnia liczby 1 (lub 0, w zależności od definicji, ale najczęściej 1) wynosi 1. To jest warunek zatrzymania: jeżeli n = 1, zwróć 1.
2. Krok rekurencyjny: Silnia liczby n jest równa n pomnożonej przez silnię liczby n-1. To jest definicja rekurencyjna: zwróć n * Silnia(n-1).
Na przykład, aby obliczyć 4!, funkcja rekurencyjna wywoła 4 * Silnia(3), która z kolei wywoła 3 * Silnia(2), potem 2 * Silnia(1). Silnia(1) zwróci 1 (przypadek bazowy), co pozwoli na obliczenie 2 * 1 = 2, następnie 3 * 2 = 6, i w końcu 4 * 6 = 24.

Zainteresował Cię artykuł Rekurencja w Informatyce: Kompleksowy Przewodnik? Zajrzyj też do kategorii Edukacja, znajdziesz tam więcej podobnych treści!