# Rekurencja oraz Sortowania
## Rekurencja
### Wprowadzenie
Na zajęciach zaczeliśmy od prostego przedstawienia rekurencji jako funkcji która zamiast wzracać właściwy wynik pewnego problemu, zwracała wynik jej wywołania dla mniejszych argumentów.

TL;DR rozwiązujemy problem korzystając z pewnych bazowych faktów.

Przykład:
*Posiadamy funkcję $f$ dla której zachodzi $f(n)=f(n-1)+1$ i $f(0)=2$. Napisz algorytm obliczający $f(n)$ dla podanego $n$*.

Jako domyślny homo sapiens, najprościej by nam było rozpisywać kolejne wartości funkcji, aż dojdziemy do $f(n)$.
$f(0)=2$
$f(1)=f(0)+1=3$
$f(2)=f(1)+1=4$
...

Warto zauważyć, że rozwiązanie to może być odwrócone do góry nogami. Mianowicie może zacząć od $f(n)$ i używając podstawiania obliczyć wynik:
$f(n)=f(n-1)+1$
$f(n)=(f(n-2)+1)+1$
...

Schodzilibyśmy coraz niżej, aż funkcja po prawej miała argument $0$, dla którego znamy wartość funkcji.

No ale dobra, jak miałby wyglądać kod takiego rozwiązania? Wbrew pozorom implementacja rekurencji jest zazwyczaj łatwiejsza od formalnego zapisu matematycznego (przynajmniej wg. mnie, Cez'a).

#include<bits/stdc++.h>
using namespace std;

//Definiujemy funkcję, która przyjmuję jakiś argument x i zwraca 
//jakąś liczbę.
int f(int x){
    
    if(x==0) return 2; //Dla wywołania funkcji f(0), zwróć 2.

    return f(x-1)+1; //W przeciwnym wypadku zwróć wartość niższej funkcji
                     //z dodaną jedynką.
}


int main(){

    int n;
    cin>>n;
    
    cout<<f(n)<<endl;

}

Jest to oczywiście bardzo łatwy przykład (do którego po chwili zastanowienia nie trzeba nawet użyć rekurencji ale ciii). Zastanówmy się nad trochę bardziej skomplikowanym przykładem rekurencji.

### Liczby Fibbonacci'ego

Zapewne Ci którzy się interesują matematyką bądź oglądają matematykę na YT spotkali się z liczbami Fibbonacci'ego. Są one zdefiniowane następująco:

$F_0=0$
$F_1=1$
$F_n=F_{n-1}+F_{n-2}$

Oczywiście naszym zadaniem jest:
*Dla podanego $n$, oblicz $F_n$.*

Nic skomplikowanego. Dodajemy dwie poprzednie liczby i to jest nasza najnowsza wartość którą używamy w kolejnych obliczeniach.

Problem ten można rozwiązać na dwa sposoby: rekurencyjnie i iteracyjnie. Najpierw omówimy rozwiązanie rekurencyjne, następnie iteracyjne, a na koniec zobaczymy, że iteracyjne bije na głowę rozwiązanie rekurencyjne.

#### Rozwiązanie rekurencyjne

Zgodnie z ideą rekurencji, dla podstawowych argumentów 0 i 1 zwrócimy konkretną wartość, a dla argumentów większych zwrócimy wynik jakiejś operacji na funkjach o niższych argumentach.

#include<bits/stdc++.h>
using namespace std;


int F(int x){
    
    if(x==0) return 0; //Dla wywołania funkcji f(0), zwróć 0.
    if(x==1) return 1; //Dla wywołania funkcji f(0), zwróć 0.

    return F(x-1)+F(x-2); //W przeciwnym wypadku zwróć dodane do siebie poprzednie 
                          //dwie liczby Fibbonnaci'ego
}


int main(){

    int n;
    cin>>n;
    
    cout<<F(n)<<endl;

}

#### Rozwiązanie iteracyjne

Podobnie jak w przykładzie na począku wprowadzenia do rekurencji, zamiast używać jakiejś rekurencji, będziemy liczyć liczby Fibbonacci'ego po kolei, zaczynając od dwójki.

#include<bits/stdc++.h>
using namespace std;


int F(int x){

    int F1=0, F2=1;
    
    
    for(int i = 2; i<=n; i++){
    
        int Suma = F1 + F2;
        
        F1 = F2;
        F2 = Suma;
    
    }
    
    return F2;

}


int main(){

    int n;
    cin>>n;
    
    cout<<F(n)<<endl;

}

#### Porównanie rozwiązań

Jak widzimy oba rozwiązania są proste co do implementacji. Jednakże jedno z nich jest w swojej prostocie zabójcze czasowo (i pamięciowo). Chodzi tutaj o rekurencyjne rozwiązanie.

Najpierw zastanówmy się nad złożonością naszego iteracyjnego rozwiązania. Widzimy dwie zmienne i jedną pętlę for. Można zatem z pewnością powiedzieć, że jest to złożoność liniowa czasowo, i stała pamięciowo. Żadnych haczyków.

Rekurencja natomiast jest trochę bardziej skomplikowana. Wizualna reprezentacja wywołań funkcji F(n) jest o wiele łatwiejsza do zrozumienia:

Pozwoliłem sobie pożyczyć takie drzewko z google images. Widzimy, że dla każdego argumentu $x\geq2$, funkcja fib wywoła dwie kolejne funkcje. Czyli jedna funkcja wywoła dwie, te więc wywołają cztery etc.

Dostajemy więc $2+2^2+2^3...+2^n$ wywołań. Oczywiście ta liczba nie jest dokładna bo nie uwzględniłem w pełni specyfikacji problemu, ale jak można zauważyć na drzewku, różnica nie jest bardzo znacząca. Złożoność czasowa tego rozwiązania zatem jest na pewno wykładnicza, czyli o wiele wolniejsza niż liniowa.

Pamięciowo? Zauważmy, że gdy wywołamy A w funkcji B, to po zakończeniu się funkcji A, trzeba wrócić do funkcji B, czyli komputer pamięta wszytkie wyższe wywołania funkcji. Czyli nasza najdłuższa gałąź w naszym drzewku (czyli ta skrajna lewa) jest naszą złożonością pamięciową. Otrzymujemy więc liniową złożoność czasową.

Zatem iteracyjne rozwiązania totalnie niszczy rekurencyjne czasowo jak i pamięciowo. Nie oznacza to, że rekurencja jest ogólnie do bani. Na wykładzie chociażby pokazywałem algorytm na wypisanie wszystkich permutacji ciągu liczb od $1$ do $n$. Zachęcam zainteresowanych do poczytania o rekurencji więcej.

### NWD
Na zajęciach przypomnieliśmy sobie jak można w sposób rekurencyjny zapisać NWD dwóch liczb.

#include<bits/stdc++.h>
using namespace std;
int NWD(int a, int b)
{
    if(b == 0)                // warunek kończący rekurencje
    {
        return a;
    }
    return NWD(b, a % b);     // obliczanie rekurencyjnie NWD  
}
int main()
{
    int a,b; cin >> a >> b;
    cout << NWD(a,b);
}

### Szybkie potęgowanie
Na zajęciach zauważyliśmy prostą obserwację, że liczbę $a^n$ możemy zapisać jako $a^n = a^{n/2} * a^{n/2}$ dla $n$ parzystego, a dla $n$ nieparzystego $a^n =a^{n/2} * a^{n/2} * a$. Następnie skorzystaliśmy z tego faktu do napisania programu z użyciem rekurencji.

#include<bits/stdc++.h>
using namespace std;
int POT(int a, int n)
{
    if(n == 1)                // warunek kończący rekurencje
    {
        return a;
    }
    if(n % 2 == 0) 
        return POT(a,n/2)*POT(a,n/2);        // jeżeli n jest parzyste
    else 
        return POT(a,n/2)*POT(a,n/2) * a;    // jeżeli n jest nieparzyste

}
int main()
{
    int a,n;
    
    cout << POT(a,n);
}

## Sortowanie

### BubbleSort

Sortowanie bąbelkowe jest bardzo proste co do idei. Lecimy po tablicy elementów, i jak dwa elementy obok siebie nie są posortowane, to jest swap'ujemy.

Przykład:
0 5 3 2
^ ^
0 5 3 2
^ ^
0 3 5 2
^ ^
0 3 2 5

To było jedne przejście po tablicy. Jak widzimy elementy nie są jeszcze posortowane. To dlatego, że BubbleSort wymaga kilka takich przejść. W najgorszym przypadku (jaki jest taki przypadek?) będzie to $n$ przejść.

Zatem złożoność czasowa to $n^2$. Pamięciowa? Cały czas operujemy na tablicy więc jedynie $n$ aby pamiętać elementy oczywiście.

#include<bits/stdc++.h>
using namespace std;

void BubbleSort(int (&tab)[100], int n)
{
    
    bool Swapped = false;
    
    for(int i = 0; i<n; i++){
    
        Swapped = false;
    
        for(j = 1; j<n - i; j++){
        
            if(tab[j-1] > tab[j]){
                swap(tab[j-1], tab[j]);
                Swapped = true;
            }
        
        }
        
        if(Swapped) break;
    
    }


}
int main()
{
    int tab[100],n;
    
    cin>>n;
    for(int i = 0; i<n; i++) cin>>tab[i];
    
    cout << BubbleSort(tab, n);
}

W mojej implementacji są dwa usprawnienia (z czego jedno było sugerowane przez jednego z was ale byłem zbyt zmęczony aby zrozumieć o co chodzi, sory).
1. Jeśli nie swap'owałem elementów w danym przejściu, to znaczy, że tablica jest posortowana.
2. Przy i'tym przejściu, swap'ujemy jedynie do n-i elementu, bo przy każdym przejściu przenieśliśmy największy element na sam koniec.

### Sortowanie przez zliczanie
Jednym z algorytmów sortowania jest właśnie algorytm przez zliczanie. Jego zasada działania jest banalnie prosta. Wczytujemy nasz ciąg i zliczamy ile wystąpił dany wyraz $a_n$. Złożoność pamięciowa takiego algorytmu wynosi $O(max(a_1,a_2,...,a_n))$, gdzie $a_i$ oznaczają wyrazy ciągu podanego na wejściu, natomiast czasowa $O(n)$.

#include<bits/stdc++.h>
using namespace std;
int tab[101]    // jeśli wiemy że liczby są z przedziału od 0 do 100
int main()
{
    int n; cin >> n;
    for(int i = 0 ; i < n ; i ++)
    {
        int x; cin >> x;
        tab[x]++;                // zwiększamy ilość wystąpienia danego wyrazu
    }
    
    for(int i = 0 ; i <= 100; i++)
    {
        while(tab[i] > 0)        
        {
            cout << i << " ";
            tab[i]--;
        }
    }

}

### QuickSort
Algorytm ten działa w następujący sposób. Najpierw wybieramy sobie losowo "piwota", który pomoże nam podzielić dany przedział tak by na lewo było rzeczy mniejsze bądź równe piwotowi a na prawo większe bądź równe. Następnie wykonujemy takie podzielenie kolejny raz na dwa nowo powstałe przedziały.

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2*1e5 + 2;

int n;
int tab[MAX];

int Podziel(int *tablica, int l, int r)
{
    int pivot = tablica[l];        // wyznaczenie piwota (tutaj jako pierwszy element przedziału a nie losowo)
    int i = l, j = r;            
    while(i <= j)        
    {
        while(tablica[i] < pivot) i++;

        while(tablica[j] > pivot) j--;

        if(i < j)
        {
            swap(tablica[i], tablica[j]);
            i++;
            j--;
        } else
        {
            break;
        }
    }        
    return j;        // miejsce podziału przedziału (l,r)

}
void QuickSort(int *tablica, int l, int r)
{
    if(l < r)
    {
        int Przedzial = Podziel(tablica, l,r);    // wyznaczenie miejsca podziału

        QuickSort(tablica, l, Przedzial);        // puszczenie QS na przedział powstały po lewej stronie
        QuickSort(tablica, Przedzial + 1, r);    // puszczenie QS na przedział powstały po prawej stronie
    }
}

int main ()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 0 ;i < n; i++)
    {
        cin >> tab[i];
    }
    QuickSort(tab,0,n-1);
    for(int i = 0 ;i < n; i++)
    {
        cout << tab[i] << " ";
    }

}

### Mergesort

Sortowanie przez scalanie jest troszkę prostsze od QuickSorta i troszkę bardziej stabilne (przy odpowiednio niesprzyjających warunkach, QuickSort może osiągnąć $n^2$).

Mianowicie będziemy dzielić naszą tablicę na dwa aż dostaniemy jedno-elementowe przedziały. Następnie zaczniemy je scalać.

Scalanie polega na przejściu po dwóch posortowanych tablicza i branie kolejnego mniejszego elementu z pierwszej bądź drugiej tablicy.

Przykład:

2 4 6
^
3 5 7
^

Scalona tablica: 2

2 4 6
^
3 5 7
^

Scalona tablica: 2 3

2 4 6
^
3 5 7
^

Scalona tablica: 2 3 4

... i tak dalej.

Następujące drzewko wizualizuje ten algorytm:


Algorytm jest najbardziej zrozumiałem w kodzie

#include <bits/stdc++.h>

using namespace std;

vector<int> pomocniczy;

void MergeSort(vector<int> &list, int l, int p){

    if(p==l) return;

    //sortujemy dwa równe podzbiory

    int s = (l+p)/2;
    
    MergeSort(list, l, s);
    MergeSort(list, s+1, p);

    //mergeujemy te dwa podzbiory
    
    pomocniczy.clear();
    int i = l, j = s+1;

    while(i <= s || j <= p){

        if(i>s){    //osiągnęliśmy koniec pierwszego podzbioru
            pomocniczy.push_back(list[j]);
            j++;
            continue;
        }
        if(j>p){    //a tutaj drugiego
            pomocniczy.push_back(list[i]);
            i++;
            continue;
        }
        
        if(list[i] < list[j]){
            pomocniczy.push_back(list[i]);
            i++;
        }
        else{
            pomocniczy.push_back(list[j]);
            j++;
        }
    }

    for(int i = l; i<=p; i++){
        list[i]=pomocniczy[i-l];
    }
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin>>n;

    vector<int> nums;

    for(int i = 0; i<n; i++){
        int x;
        cin>>x;
        nums.push_back(x);
    }

    MergeSort(nums, 0, n-1);

Do scalania można zdefiniować osobną funkcję. Zachęcam chętnych do napisania oddzielnej funkcji scalania która zostałaby użyta w funkcji MergeSort.

*Ja (Cez) i Dawid Skowronek (Skowi) zastrzegamy sobie prawo do nie brania odpowiedzialności za błędy w powyższym artykule które prawdopodobnie zostały wywołane zmęczeniem i brakiem zdolności humanistycznych.*