Rekurencja w informatyce - definicja, przykłady i algorytmy (Python, C++, Java)

Jedną z podstawowych definicji, z którą należy się zapoznać, ucząc się programowania, jest rekurencja. Przydaje się ona przy tworzeniu kodu, o czym przekonało się już wielu programistów. Jej znajomość jest też wymagana na maturze z informatyki. W tym artykule przeprowadzimy Cię krok po kroku przez wszystko, co musisz wiedzieć o rekurencji.

Co to jest rekurencja w informatyce?

Rekurencja (rekursja) to odwołanie się funkcji do samej siebie w trakcie działania programu. Wystarczy nawet pojedyncze wywołanie się procedury przez samą siebie, żeby uznać ją za rekurencyjną. Brzmi skomplikowanie? Spokojnie - za chwilę zobaczysz, że to prostsze niż myślisz.

Wyobraź sobie, że stoisz przed lustrem, a za Tobą jest drugie lustro. Widzisz nieskończone odbicia samego siebie - każde mniejsze od poprzedniego. Rekurencja działa podobnie: funkcja wywołuje samą siebie, ale za każdym razem z "mniejszym" problemem, aż dojdzie do przypadku podstawowego (bazowego), który można rozwiązać bezpośrednio.

Przykład rekurencji - obliczanie silni

Silnia liczby n (zapisywana jako n!) to iloczyn wszystkich liczb naturalnych od 1 do n. Na przykład: 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. Można to zapisać rekurencyjnie, zauważając że n! = n \cdot (n-1)!

funkcja Silnia(n)
    jeżeli n = 0 lub n = 1 wykonuj
        zwróć 1
    zwróć n * Silnia(n - 1)

Wykonanie powyższego kodu dla n = 3 wygląda następująco (każde wcięcie to kolejny poziom wywołania rekurencyjnego):

1. Silnia(3) – Warunek nie jest spełniony (bo n = 3), więc przechodzimy do mnożenia: 3 \cdot Silnia(2)
2. Silnia(2) – Warunek nie jest spełniony (bo n = 2), więc: 2 \cdot Silnia(1)
3. Silnia(1) – Warunek JEST spełniony (bo n = 1), więc zwracamy 1
4. Powrót do Silnia(2) – Mnożymy wynik z Silnia(1) (czyli 1) przez 2, wynik = 2
5. Powrót do Silnia(3) – Mnożymy wynik z Silnia(2) (czyli 2) przez 3, wynik = 6

Widzisz wzorzec? Funkcja "zanurzała się" coraz głębiej, aż dotarła do przypadku bazowego (n = 1), a potem "wynurzała się" z powrotem, zbierając wyniki po drodze.

Kluczowe elementy każdej funkcji rekurencyjnej

Każda poprawna funkcja rekurencyjna MUSI zawierać dwa elementy:

1. Przypadek bazowy (warunek brzegowy) – sytuacja, w której funkcja zwraca wynik BEZ wywoływania samej siebie. To "dno" rekurencji, które zatrzymuje nieskończone wywołania.
2. Przypadek rekurencyjny – sytuacja, w której funkcja wywołuje samą siebie, ale z MNIEJSZYM lub PROSTSZYM problemem. Krok po kroku zbliżamy się do przypadku bazowego.

UWAGA: Jeśli zapomnisz o przypadku bazowym lub źle go zdefiniujesz, funkcja będzie wywoływać samą siebie w nieskończoność, co doprowadzi do błędu Stack Overflow (przepełnienie stosu).

Rodzaje rekurencji

Rekurencja dzieli się na różne typy w zależności od sposobu wywołania oraz liczby wywołań. Znajomość tych podziałów pomoże Ci lepiej zrozumieć działanie rekurencji w kodzie.

Podział według sposobu wywołania

Rekurencja bezpośrednia jest spotykana znacznie częściej i łatwiejsza do analizy.

Podział według wzrostu liczby wywołań

Rekurencja nieliniowa może prowadzić do ogromnej liczby wywołań. Na przykład dla ciągu Fibonacciego obliczenie fib(50) naiwną metodą rekurencyjną wymagałoby miliardów wywołań!

Rekurencja ogonowa - szczególny przypadek

Rekurencja ogonowa (tail recursion) występuje wtedy, gdy ostatnią instrukcją funkcji jest wywołanie rekurencyjne. Dlaczego to ważne? Kompilatory wielu języków potrafią zoptymalizować taką rekurencję, zamieniając ją na pętlę, co eliminuje problem przepełnienia stosu.

# Zwykła rekurencja (NIE ogonowa)
def silnia(n):
    if n <= 1:
        return 1
    return n * silnia(n - 1)  # Po wywołaniu rekurencyjnym jest jeszcze mnożenie!

# Rekurencja ogonowa
def silnia_ogonowa(n, akumulator=1):
    if n <= 1:
        return akumulator
    return silnia_ogonowa(n - 1, n * akumulator)  # Ostatnia instrukcja = wywołanie

Rekurencja ogonowa pozwala na łatwą konwersję na iterację (pętlę), co może być przydatne przy optymalizacji.

Ciąg Fibonacciego - klasyczny przykład rekurencji

Ciąg Fibonacciego to jeden z najpopularniejszych przykładów rekurencji. Jest to ciąg liczb naturalnych, w którym każda liczba jest sumą dwóch poprzednich: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Definicja matematyczna: fib(1) = 1, fib(2) = 1, a dla n > 2: fib(n) = fib(n-1) + fib(n-2)

Implementacja rekurencyjna

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

# Przykład użycia
for i in range(1, 11):
    print(fib(i), end=" ")
# Wynik: 1 1 2 3 5 8 13 21 34 55

Powyższy kod jest elegancki i prosty, ale ma poważny problem z wydajnością. Spójrz na drzewo wywołań dla fib(6):

                    fib(6)
                   /      \
              fib(5)        fib(4)
             /    \         /    \
        fib(4)  fib(3)   fib(3) fib(2)
        /   \    /  \     /  \
    fib(3) fib(2) fib(2) fib(1) fib(2) fib(1)
    /   \
 fib(2) fib(1)

Widzisz problem? fib(3) jest obliczane 3 razy, fib(2) aż 5 razy! Im większe n, tym więcej powtórzeń. To prowadzi do wykładniczej złożoności O(2^n) - katastrofalnie wolnej.

Implementacja iteracyjna (znacznie wydajniejsza)

def fib_iteracyjnie(n):
    if n <= 2:
        return 1
    
    przedwczesniej = 0
    wczesniej = 1
    teraz = 1
    
    for i in range(2, n):
        przedwczesniej = wczesniej
        wczesniej = teraz
        teraz = przedwczesniej + wczesniej
    
    return teraz

# Teraz możemy bez problemu obliczyć nawet fib(1000)!
print(fib_iteracyjnie(50))  # Działa w ułamku sekundy

Wersja iteracyjna ma złożoność O(n) - liniową. To ogromna różnica! Dla n = 50 rekurencja wykonałaby biliony operacji, a iteracja tylko 50.

Rekurencja – zalety i wady

Większość początkujących programistów nie jest zaznajomiona z zaletami oraz wadami rekurencji. Warto je poznać, żeby świadomie decydować, kiedy warto jej użyć.

Zalety rekurencji

• Zwięzły i czytelny kod – dla problemów o rekurencyjnej naturze (drzewa, grafy, dziel i zwyciężaj) kod rekurencyjny bywa znacznie krótszy i łatwiejszy do zrozumienia
• Naturalność zapisu – niektóre algorytmy są definiowane rekurencyjnie z natury (silnia, Fibonacci, przeszukiwanie drzew), więc rekurencyjny kod odzwierciedla matematyczną definicję
• Możliwość udowodnienia poprawności – za pomocą indukcji matematycznej można formalnie dowieść, że algorytm rekurencyjny działa poprawnie dla wszystkich przypadków
• Memoizacja (caching) – można zoptymalizować algorytm rekurencyjny, zapisując wyniki powtarzających się wywołań, co drastycznie zmniejsza liczbę obliczeń

Wady rekurencji

• Jest pamięciochłonna – każde wywołanie funkcji wymaga miejsca na stosie (stack) do przechowywania zmiennych lokalnych i adresu powrotu. Głęboka rekurencja może przepełnić stos
• Może być wolna – narzut związany z wywołaniami funkcji (tworzenie ramki stosu, skok) spowalnia działanie w porównaniu z prostą pętlą
• Jest mniej intuicyjna dla początkujących – wymaga myślenia w kategoriach "zaufaj rekurencji" i zrozumienia, jak działa stos wywołań
• Ryzyko nieskończonej rekurencji – źle zdefiniowany warunek bazowy prowadzi do błędu Stack Overflow

Zapytani o rekurencję, doświadczeni programiści często odpowiadają: "unikamy, kiedy się da". Nie znaczy to, że rekurencja jest zła – po prostu wymaga świadomego stosowania. Dla wielu problemów (np. przeszukiwanie drzew, algorytmy dziel i zwyciężaj) jest naturalnym i eleganckim rozwiązaniem.

Kiedy używać rekurencji, a kiedy iteracji?

Oto praktyczny przewodnik, który pomoże Ci podjąć właściwą decyzję:

Używaj rekurencji, gdy:

• Problem ma rekurencyjną naturę – np. przeszukiwanie drzew, algorytmy dziel i zwyciężaj (Quicksort, Merge Sort), Wieże Hanoi
• Struktura danych jest rekurencyjna – drzewa binarne, grafy, listy powiązane – naturalnie nadają się do rekurencyjnego przetwarzania
• Problem można podzielić na identyczne podproblemy – jeśli rozwiązanie całości to kombinacja rozwiązań mniejszych, identycznych fragmentów
• Czytelność kodu jest priorytetem – rekurencyjny zapis bywa znacznie krótszy i bliższy matematycznej definicji

Używaj iteracji (pętli), gdy:

• Problem jest prosty i liniowy – sumowanie elementów tablicy, proste przeszukiwanie – pętla będzie prostsza
• Zależy Ci na wydajności – iteracja nie ma narzutu związanego z wywołaniami funkcji
• Musisz kontrolować zużycie pamięci – głęboka rekurencja może przepełnić stos
• Kod będą czytać początkujący programiści – dla wielu osób pętla jest bardziej intuicyjna

Przykłady algorytmów rekurencyjnych

Rekurencja jest szeroko stosowana w informatyce. Oto najważniejsze algorytmy, które warto znać:

• Silnia (Factorial) – klasyczny przykład rekurencji liniowej
• Ciąg Fibonacciego – przykład rekurencji nieliniowej (wymaga optymalizacji!)
• Wyszukiwanie binarne (Binary Search) – dzielenie przedziału na pół
• Sortowanie szybkie (Quicksort) – dziel i zwyciężaj, średnio O(n \log n)
• Sortowanie przez scalanie (Merge Sort) – stabilne sortowanie, zawsze O(n \log n)
• Wieże Hanoi – klasyczny problem rekurencyjny
• Przeszukiwanie grafów DFS – głębokie przeszukiwanie grafu
• Przechodzenie drzew – preorder, inorder, postorder
• Szybkie potęgowanie – obliczanie a^n w O(\log n)
• Algorytm Euklidesa (NWD) – największy wspólny dzielnik

Wieże Hanoi - pełna implementacja

Wieże Hanoi to klasyczny problem rekurencyjny, sformułowany przez Édouarda Lucasa w 1883 roku. Jest doskonałym przykładem problemu, który trudno rozwiązać iteracyjnie, a rekurencyjnie jest wręcz elegancki.

Reguły gry

1. Mamy trzy słupki (A, B, C) i n krążków o różnych rozmiarach
2. Na początku wszystkie krążki są na słupku A, ułożone od największego (na dole) do najmniejszego (na górze)
3. Cel: przenieść wszystkie krążki na słupek B
4. Zasady: można przenosić tylko jeden krążek na raz, nigdy nie kładziemy większego na mniejszy

Algorytm rekurencyjny

Sprytna obserwacja: żeby przenieść n krążków z A na B, musimy:

1. Przenieść n-1 górnych krążków z A na C (używając B jako pomocniczego)
2. Przenieść największy krążek z A na B
3. Przenieść n-1 krążków z C na B (używając A jako pomocniczego)

To właśnie jest definicja rekurencyjna! Aby przenieść n krążków, musimy dwa razy przenieść n-1 krążków.

Pseudokod

funkcja hanoi(n, źródło, cel, pomocniczy)
    jeżeli n = 1 wykonuj
        wypisz("Przenieś krążek z " + źródło + " na " + cel)
    w przeciwnym razie
        hanoi(n-1, źródło, pomocniczy, cel)
        wypisz("Przenieś krążek z " + źródło + " na " + cel)
        hanoi(n-1, pomocniczy, cel, źródło)

Przykład wykonania dla n = 3

Prześledźmy wywołania krok po kroku. Wcięcia pokazują poziom rekurencji:

hanoi(3, A, B, C)                      # Cel: 3 krążki z A na B
    hanoi(2, A, C, B)                  # Podcel: 2 krążki z A na C
        hanoi(1, A, B, C)              # 1 krążek z A na B
            → Przenieś z A na B
        → Przenieś z A na C            # Środkowy krążek na C
        hanoi(1, B, C, A)              # 1 krążek z B na C
            → Przenieś z B na C
    → Przenieś z A na B                # NAJWIĘKSZY krążek na B!
    hanoi(2, C, B, A)                  # Podcel: 2 krążki z C na B
        hanoi(1, C, A, B)              # 1 krążek z C na A
            → Przenieś z C na A
        → Przenieś z C na B            # Środkowy krążek na B
        hanoi(1, A, B, C)              # 1 krążek z A na B
            → Przenieś z A na B

Wynikowa sekwencja ruchów: A→B, A→C, B→C, A→B, C→A, C→B, A→B. Razem 7 ruchów - to minimalna liczba dla 3 krążków.

Ciekawostka: minimalna liczba ruchów dla n krążków to 2^n - 1. Dla 3 krążków: 2^3 - 1 = 7. Dla 64 krążków (jak w legendzie): 2^{64} - 1 \approx 18 trylionów ruchów!

Python - Wieże Hanoi

def hanoi(n, zrodlo, cel, pomocniczy):
    if n == 1:
        print(f"Przenieś krążek z {zrodlo} na {cel}")
    else:
        hanoi(n - 1, zrodlo, pomocniczy, cel)
        print(f"Przenieś krążek z {zrodlo} na {cel}")
        hanoi(n - 1, pomocniczy, cel, zrodlo)

# Wywołanie dla 3 krążków
print("Rozwiązanie Wież Hanoi dla 3 krążków:")
hanoi(3, 'A', 'B', 'C')

C++ - Wieże Hanoi

#include <iostream>
using namespace std;

void hanoi(int n, char zrodlo, char cel, char pomocniczy) {
    if (n == 1) {
        cout << "Przenies krazek z " << zrodlo << " na " << cel << endl;
    } else {
        hanoi(n - 1, zrodlo, pomocniczy, cel);
        cout << "Przenies krazek z " << zrodlo << " na " << cel << endl;
        hanoi(n - 1, pomocniczy, cel, zrodlo);
    }
}

int main() {
    cout << "Rozwiazanie Wiez Hanoi dla 3 krazkow:" << endl;
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

Java - Wieże Hanoi

public class WiezeHanoi {
    public static void hanoi(int n, char zrodlo, char cel, char pomocniczy) {
        if (n == 1) {
            System.out.println("Przenies krazek z " + zrodlo + " na " + cel);
        } else {
            hanoi(n - 1, zrodlo, pomocniczy, cel);
            System.out.println("Przenies krazek z " + zrodlo + " na " + cel);
            hanoi(n - 1, pomocniczy, cel, zrodlo);
        }
    }

    public static void main(String[] args) {
        System.out.println("Rozwiazanie Wiez Hanoi dla 3 krazkow:");
        hanoi(3, 'A', 'B', 'C');
    }
}

Optymalizacja rekurencji - memoizacja

Jak widzieliśmy na przykładzie Fibonacciego, naiwna rekurencja może wielokrotnie obliczać te same wartości. Memoizacja (caching) to technika zapisywania wyników obliczeń, aby uniknąć powtórzeń.

Fibonacci z memoizacją

# Prosta memoizacja ręczna
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# Lub elegancko z dekoratorem:
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 2:
        return 1
    return fib_lru(n - 1) + fib_lru(n - 2)

# Teraz fib(100) działa błyskawicznie!
print(fib_lru(100))  # 354224848179261915075

Dzięki memoizacji złożoność spada z O(2^n) do O(n) - każda wartość jest obliczana tylko raz!

Najczęściej zadawane pytania o rekurencję

Kiedy rekurencja sprawia problemy?

• Przepełnienie stosu (Stack Overflow) – gdy problem jest zbyt złożony lub brak warunku brzegowego, stos wywołań może się zapełnić. W Pythonie domyślny limit to ok. 1000 wywołań.
• Problemy z wydajnością – bez memoizacji rekurencja nieliniowa może być katastrofalnie wolna
• Błędny warunek bazowy – jeśli przypadek bazowy jest źle zdefiniowany, rekurencja może nigdy się nie zakończyć

Jak zoptymalizować algorytmy rekurencyjne?

• Memoizacja – zapisuj wyniki wcześniejszych wywołań
• Rekurencja ogonowa – pozwala kompilatorowi zoptymalizować do pętli
• Konwersja na iterację – jeśli to możliwe, zamień rekurencję na pętlę
• Programowanie dynamiczne – bardziej systematyczne podejście do problemów z powtarzającymi się podproblemami

Czym różni się rekurencja od iteracji?

Jak rozpoznać algorytm rekurencyjny?

W gotowym kodzie łatwo rozpoznasz rekurencję, znajdując wywołanie funkcji przez samą siebie. Wystarczy wyszukać (Ctrl+F) nazwę funkcji wewnątrz jej ciała. Jeśli funkcja `foo` zawiera w sobie wywołanie `foo(...)`, to jest rekurencyjna.

Podsumowanie

Rekurencja jest potężnym narzędziem, które pozwala elegancko rozwiązywać problemy o rekurencyjnej naturze. Jednak wymaga świadomego stosowania – pamiętaj o warunku bazowym, uważaj na wydajność przy rekurencji nieliniowej i rozważ memoizację lub konwersję na iterację, gdy to konieczne.

• Zawsze definiuj przypadek bazowy – to zatrzymuje rekurencję
• Każde wywołanie musi zbliżać się do przypadku bazowego – inaczej rekurencja nie zakończy się
• Rozważ złożoność – rekurencja nieliniowa może być wykładniczo wolna
• Używaj memoizacji – gdy te same wartości są obliczane wielokrotnie
• Dla prostych problemów wybierz iterację – jest szybsza i zużywa mniej pamięci

Jeśli dobrze opanujesz rekurencję, stanie się ona naturalnym sposobem myślenia o problemach algorytmicznych. A na maturze z informatyki możesz być pewien, że się przyda!