Rekurencja

Rekurencja w programowaniu odnosi się do sytuacji, w której funkcja wywołuje samą siebie w celu rozwiązania problemu. Jest to technika, w której problem jest dzielony na mniejsze podproblemy, aż dojdziesz do problemów na tyle małych, że można je rozwiązać bezpośrednio. Rekurencja jest szczególnie przydatna w sytuacjach, gdzie problem ma naturalną strukturę zagnieżdżonych podproblemów.

W języku Python rekurencję można zaimplementować w funkcjach poprzez wywoływanie funkcji samej siebie z innymi argumentami. Kluczowym aspektem jest zadanie warunku bazowego, który określa moment, w którym rekurencja się zatrzymuje i nie wywołuje się dalej.

Przykład 1 – obliczanie silni:

def silnia(n):
	if n == 0:
		return 1
	else:
		return n * silnia(n - 1)

print(silnia(5))  # 5! = 5 * 4 * 3 * 2 * 1 = 120

W tym przykładzie funkcja silnia wywołuje samą siebie, obliczając silnię liczby n poprzez pomnożenie jej przez silnię liczby n - 1. Rekurencja działa, dopóki nie osiągnie warunku bazowego n == 0, wtedy zwraca 1. Dzięki temu, rekurencyjnie obliczane jest iloczyn kolejnych liczb, co daje wynik silni.

Przykład 2 – zamiana dec na bin:

def dec2bin(n):
    if(n==0): 
        return
    dec2bin(n//2)
    print(n%2, end="")

Przykład 3 – ciąg Fibonacciego:

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

# pierwszych 10 elementów ciągu:
for i in range(10):
    print(fib(i), end=" ")	

Ważne kwestie związane z rekurencją:

1. Warunek bazowy: To jest kluczowy element rekurencji. Musisz określić warunek, przy którym rekurencja się zatrzymuje i zwraca wartość bez dalszych wywołań rekurencyjnych. Bez właściwie zdefiniowanego warunku bazowego rekurencja może prowadzić do nieskończonej pętli.
2. Podproblemy: W każdym kroku rekurencji problem jest dzielony na mniejsze podproblemy. To właśnie te podproblemy prowadzą do osiągnięcia warunku bazowego.
3. Efektywność: Rekurencja może prowadzić do dużego zużycia pamięci i nieefektywności, zwłaszcza jeśli nie jest prawidłowo zaimplementowana. W niektórych przypadkach, gdzie problem może być łatwo rozwiązany iteracyjnie, lepiej jest unikać rekurencji.
4. Debugowanie: Debugowanie rekurencyjnych funkcji może być trudne, ponieważ każde wywołanie rekurencyjne tworzy nowy stos wywołań. Używanie drzewa wywołań (np. poprzez wypisywanie informacji przy każdym wywołaniu) może pomóc zrozumieć, jak funkcja działa.

Rekurencja jest potężnym narzędziem, które może być używane do rozwiązywania wielu problemów. Jednakże, warto używać jej z umiarem, starając się wybrać odpowiedni moment do zastosowania, a także dbając o prawidłową implementację warunku bazowego i efektywności rozwiązania.