Algorytmy i struktury danych - Rekurencja oraz technika "Dziel i zwyciężaj"

1. Rekurencja to funkcja, która wywołuje samą siebie w sposób pośredni lub bezpośredni. Stosowana jest w momencie, w której dany "problem" można rozłożyć na "problem o mniejszym stopniu". skomplikowania".

np. obliczanie silni





2. Definicja Ciągu Fibonacciego: 

Przykład kodu:
Fibonacci( n )
   if n=0 then return 0
   if n=1 then return 1
   f' ← 0
   f ← 1
   for i ← 2 to n
     do
       m ← f + f'
       f' ← f
       f ← m
     end
   return f
3. W metodzie "Dziel i zwyciężaj" problem dzielony jest na kilka mniejszych podproblemów podobnych do początkowego problemu. Problemy te rozwiązywane są rekurencyjnie, a następnie rozwiązania wszystkich podproblemów są łączone w celu utworzenia rozwiązania całego
problemu.
W strategii dziel i zwyciężaj każdy poziom rekurencji składa się z następujących
trzech etapów:

Dziel: Dzielimy problem na podproblemy.
Zwyciężaj: Rozwiązujemy podproblemy rekurencyjnie, chyba że są one małego rozmiaru i
już nie wymagają zastosowania rekursji – używamy wtedy bezpośrednich metod.
Połącz: Łączymy rozwiązania podproblemów, aby otrzymać rozwiązanie całego problemu

4. Metody sortowania tablic techniką "Dziel i zwyciężaj":
  • wyszukiwanie binarne (dzielimy tablice na dwie równe mniejsze tablice; jeżeli x jest mniejsze od elementu środkowego wybieramy lewą podtablicę, jeżeli nie - prawą)
  • sortowanie przez scalanie (dzielimy tablicę na dwie podtablice (mniej więcej na pół), następnie sortujemy każdą podtablicę, a potem scalamy je i w jedną posortowaną już tablicę)
  • szybkie sortowanie (w każdym kroku algorytmu elementy sortowanego ciągu są rozdzielane względem elementem rozdzielającym, na podzbiór elementów większych lub mniejszych od danej liczby