Rekurencja - Żeby zrozumieć rekurencję, najpierw musisz zrozumieć rekurencję

Rekurencja

Rekurencja, zwana także rekursją – odwoływanie się np. funkcji lub definicji do samej siebie. 1

Każda definicja rekurencyjna potrzebuje przynajmniej jednego przypadku bazowego (nie rekurencyjnego). W przeciwnym wypadku nigdy się nie zakończy (warunek stopu). 1

Innymi słowy: W pewnym momencie wywoływanie funkcji przez samą siebie musi się kiedyś zakończyć, dlatego potrzebny jest stan, w którym dana funkcja nie jest wywoływana ponownie.

1(1,2)

https://pl.wikipedia.org/wiki/Rekurencja

Przykład - Suma kolejnych liczb całkowitych

W matematyce:

f(0) = 0
f(n) = n + f(n - 1)

Rozwinięcie:

f(5) = 5 + f(5 - 1)
         = 5 + f(4) = 5 + (4 + f(4 - 1))
         = 5 + (4 + f(3)) = 5 + (4 + (3 + f(3 - 1)))
         = 5 + (4 + (3 + f(2))) = 5 + (4 + (3 + (2 + f(2 - 1))))
         = 5 + (4 + (3 + (2 + f(1))) = 5 + (4 + (3 + (2 + (1 + f(1 - 1)))))
         = 5 + (4 + (3 + (2 + (1 + f(0)))) = 5 + (4 + (3 + (2 + (1 + 0))))
         = 15

To samo zapisane w języku Python:

def f(n):
        if n == 0:   # <-- warunek stopu
                return 0
        else:
                return n + f(n - 1)

x = f(5)

print(x)

Rozwinięcie dla języka Python:

x = f(5)
  = 5 + f(5 - 1)
  = 5 + f(4) = 5 + (4 + f(4 - 1))
  = 5 + (4 + f(3)) = 5 + (4 + (3 + f(3 - 1)))
  = 5 + (4 + (3 + f(2))) = 5 + (4 + (3 + (2 + f(2 - 1))))
  = 5 + (4 + (3 + (2 + f(1))) = 5 + (4 + (3 + (2 + (1 + f(1 - 1)))))
  = 5 + (4 + (3 + (2 + (1 + f(0)))) = 5 + (4 + (3 + (2 + (1 + 0))))
  = 5 + (4 + (3 + (2 + (1)))
  = 5 + (4 + (3 + (3)))
  = 5 + (4 + (6))
  = 5 + (10)
  = 15

Przykład - Ciąg Fibonacciego

W matematyce:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

To samo zapisane w języku Python:

def F(n):
        if n == 0:  # <-- warunek stopu
                return 0
        elif n == 1: # <-- warunek stopu
                return 1
        else:
                return F(n - 1) + F(n - 2)

Ważne

Obliczenia wykonywane rekurencyjnie nie zawsze są efektywne.

Obliczenia rekurencyjne często wymagają większej liczby wykonywanych obliczeń, a także wiążą się ze zwiększonym wykorzystaniem pamięci.