Rekurencja i iteracja

Rekurencja i iteracja to dwa kluczowe podejścia w programowaniu, pozwalające na rozwiązanie problemów poprzez wykonywanie powtarzalnych działań.

Na czym polega rekurencja?

Rekurencja to technika programistyczna, w której funkcja wywołuje samą siebie, aż do momentu osiągnięcia określonego warunku zakończenia, zwanego warunkiem bazowym. Rekurencja jest szczególnie przydatna w problemach, które można podzielić na mniejsze, podobne do siebie podproblemy (np. przeszukiwanie struktur drzewiastych, rozwiązywanie równań rekurencyjnych).

Struktura rekurencji:
  1. Warunek bazowy: Punkt, w którym rekurencja się zatrzymuje.
  2. Wywołanie rekurencyjne: Funkcja wywołuje samą siebie z mniejszym problemem.

Przykład (obliczanie silni w języku programowania pythoon):

Na czym polega iteracja?

Iteracja to powtarzanie zestawu operacji za pomocą pętli (np. for, while). Iteracje są prostsze do zrozumienia w wielu przypadkach i bardziej wydajne, ponieważ nie obciążają stosu wywołań.

Przykład (obliczanie silni w języku programowania pythoon):

Algorytm obliczania silni liczby naturalnej

Silnia liczby naturalnej nnn, oznaczana jako n!n!n!, to iloczyn wszystkich liczb naturalnych od 1 do nnn. Definicja matematyczna:

  • 0!=10! = 10!=1
  • n!=n×(n−1)!n! = n \times (n-1)!n!=n×(n−1)!, dla n>0n > 0n>0.

Implementacja rekurencyjna:

  1. Jeśli n=0n = 0n=0, zwróć 1 (warunek bazowy).
  2. W przeciwnym razie zwróć n×silnia(n−1)n \times silnia(n-1)n×silnia(n−1).

Przykład:

  • 5!=5×4!=5×4×3×2×1=1205! = 5 \times 4! = 5 \times 4 \times 3 \times 2 \times 1 = 1205!=5×4!=5×4×3×2×1=120.

Ciąg Fibonacciego

Ciąg Fibonacciego to sekwencja liczb, w której każda liczba (począwszy od trzeciej) jest sumą dwóch poprzednich:

  • F(0)=0F(0) = 0F(0)=0
  • F(1)=1F(1) = 1F(1)=1
  • F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2), dla n>1n > 1n>1.

Implementacja rekurencyjna:

Iteracyjna wersja algorytmu:

Przykład:

  • Ciąg Fibonacciego dla n=5n = 5n=5: 0,1,1,2,3,50, 1, 1, 2, 3, 50,1,1,2,3,5.

Algorytm Euklidesa – wyznaczanie NWD

Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba całkowita, która dzieli obie liczby bez reszty.

Opis algorytmu:

Algorytm Euklidesa opiera się na własności, że:

  • NWD(a,b)=NWD(b,amod  b)NWD(a, b) = NWD(b, a \mod b)NWD(a,b)=NWD(b,amodb), gdzie amod  ba \mod bamodb to reszta z dzielenia aaa przez bbb.
  • Jeśli b=0b = 0b=0, to NWD(a,b)=aNWD(a, b) = aNWD(a,b)=a.

Rekurencyjna implementacja:

Iteracyjna implementacja:

Przykład:

Znajdź NWD dla a=48a = 48a=48 i b=18b = 18b=18:

  1. 48mod  18=1248 \mod 18 = 1248mod18=12, więc NWD(48,18)=NWD(18,12)NWD(48, 18) = NWD(18, 12)NWD(48,18)=NWD(18,12).
  2. 18mod  12=618 \mod 12 = 618mod12=6, więc NWD(18,12)=NWD(12,6)NWD(18, 12) = NWD(12, 6)NWD(18,12)=NWD(12,6).
  3. 12mod  6=012 \mod 6 = 012mod6=0, więc NWD(12,6)=6NWD(12, 6) = 6NWD(12,6)=6.

Wynik: NWD(48,18)=6NWD(48, 18) = 6NWD(48,18)=6.

Podsumowanie

Rekurencja i iteracja to dwa różne podejścia do rozwiązywania problemów:

  • Rekurencja jest naturalna dla problemów o strukturze hierarchicznej (np. ciąg Fibonacciego, NWD).
  • Iteracja jest bardziej efektywna pod względem pamięci, ale może być mniej intuicyjna.

W algorytmach takich jak wyznaczanie NWD, zarówno rekurencja, jak i iteracja są równie skuteczne, ale w przypadku skomplikowanych problemów rekurencja oferuje prostszy zapis i lepszą czytelność.