Czym jest rekurencja?

Rekurencja to proces, w którym funkcja wywołuje samą siebie. W programowaniu funkcja rekurencyjna to funkcja, która wywołuje siebie bezpośrednio lub pośrednio. Aby uniknąć nieskończonej pętli, funkcja rekurencyjna musi mieć przypadek bazowy, w którym przestaje się wywoływać.

Przykłady zastosowania:

• Przechodzenie przez struktury danych (np. drzewa).
• Rozwiązywanie problemów, które można podzielić na mniejsze podproblemy tego samego typu (np. obliczanie silni).

Przykład obliczania silni za pomocą rekurencji:

def factorial(n):
  # Przypadek bazowy: silnia z 0 to 1
  if n == 0:
    return 1
  # Przypadek rekurencyjny: silnia z n = n * silnia z (n-1)
  else:
    return n * factorial(n - 1)

# Przykład użycia
result = factorial(5)
# wynik będzie 120

Wady rekurencji:

• Może zużywać dużo pamięci z powodu stosu wywołań.
• Może być mniej wydajna w porównaniu do rozwiązań iteracyjnych dla niektórych problemów.
• Może prowadzić do przepełnienia stosu przy głębokich wywołaniach rekurencyjnych.