quicksort rekurencja

Question

Witam, muszę zadać to pytanie bo pogubiłem się w zrozumieniu wywołań rekurencyjnych. 

Wszystko do tej pory rozumiem, ale nie potrafie zrozumieć dlaczego skąd bierze się ostatnie wywołanie rekurencyjne dla algorytmu quick sort. Kod zamieszczam poniżej, służy on do nauki krok po kroku co się dzieje w kodzie, mam nadzieje że, kod jest w miare czytelny. 

(A dokładniej skąd w ostanim wywołaniu rekurencyjnym bierze się wartość dla  prawy = 3,  i  = 2  ) ???

 

#include <iostream>                 //KOD DO NAUKI
#include <cstdio>

using namespace std;

void quicksort(int *tablica, int lewy, int prawy)
{
    int pivot = tablica[(lewy + prawy)/2];
    int i,j;
    i=lewy;
    j=prawy;

    cout << "---------------------------------------------------" << endl;
    cout << "lewy;                                   = " << lewy  << endl;
    cout << "prawy;                                  = " << prawy << endl;
    cout << "int pivot = tablica[(lewy + prawy)/2];  = " << pivot << endl;
    cout << "int i=lewy;                             = " << i     << endl;
    cout << "int j=prawy;                            = " << j     << endl;
    cout << "---------------------------------------------------" << endl <<endl;

    int counter = 1;
    do
    {
        cout << "Dzialanie petli do...while(i<=j);" << endl;
        cout << "---------------------------------------------------" << endl;

        while(tablica[i] < pivot) i++;
        cout<<"while(tablica[i]<pivot) i++;      i = "<< i <<endl;
        while(tablica[j] > pivot) j--;
        cout<<"while(tablica[j]>pivot) j--;      j = "<< j <<endl << endl;

        cout<<"warunek if(i<=j) wewnatrz petli do...while   "<<endl;
        if(i <= j)
        {
            swap(tablica[i],tablica[j]);
            cout<<"swap(tablica[i],tablica[j]);         = ("<<tablica[i]<<","<<tablica[j]<<")"<<endl;

            i++;
            j--;
            cout<<"i++;                               i = "<< i <<endl;
            cout<<"j--;                               j = "<< j <<endl;

        }

        cout<<'\n'<<"***Po posortowaniu nr."<<counter <<endl;
        for(int i=0; i<6; i++)
        {
            cout<<tablica[i]<<" ";
        }
        cout << "\n---------------------------------------------------" << endl;
        counter++;
        getchar();

    }
    while(i <= j);
   
    cout << endl << "[ i = " << i << "]" << "[prawy = " << prawy <<"]"<< endl;
    if(j>lewy)
    {
        cout <<endl<< "REKURENCJA" << endl;
        cout <<endl<< "lewy = "<< lewy << endl;
        cout << "j = "         << j << endl << endl;
        cout << "if(j>lewy)  quicksort(tablica,lewy, j);" << endl;
        quicksort(tablica,lewy, j);
    }
    cout << endl << "[ i = " << i << "]" << "[prawy = " << prawy <<"]"<< endl;
    if(i<prawy)
    {
        cout <<endl<< "REKURENCJA" << endl;
        cout <<endl<< "prawy = "<< prawy << endl;
        cout << "i = "          << i << endl<<endl;
        cout << "if(i<prawy) quicksort(tablica, i, prawy);" << endl;
        quicksort(tablica, i, prawy);
    }
}

int main()
{
    int tablica[] = {6, 3, 11, 3, 3, 9};

        cout<<"Przed posortowaniem: "<<endl;
        for(int i=0; i<6; i++) {

            cout<<tablica[i]<<" ";
        }

    cout<<endl<<"Sortuje teraz algorytmem quicksort. Prosze czekac!"<<endl << endl;
    cout << "quicksort (tablica, 0, 5);\nvoid quicksort(int *tablica, int lewy, int prawy)" << endl << endl;

    quicksort(tablica, 0, 5);

        cout<<"Po posortowaniu: "<<endl;
        for(int i=0; i<6; i++){

            cout<<tablica[i]<<" ";
        }

    return 0;
}

 

Comments

Polecam IDE z debuggerem :P. Wtedy nie potrzebujesz zawsze wszystkiego wypisywać bo śledzisz sobie krok po kroku kod i możesz podglądnąć wartość każdej zmiennej na danym etapie.

---

Pisze z palca, jest trudniej ale utrwala się wiedza lepiej, jak się samemu stara rozgryść zasade działania.  Taka metoda nauki, może nie idealna ale programowanie nie należy do najłatwiejszych dziedzin.

Dopisałem pare linijek kodu. Odnośnie ostaniego wywołania rekurencyjnego, i tam jest problem, tylko nie wiem czemu się tak dzieje ,że miedzy wywołaniem jednej rekurencji a drugiej zmienne zmieniają swoje wartości. Bez konkretnego polecenia lub instrukcji w kodzie nie rozumiem tego.

---

Siedzę nad tym kodem i dochodzę do wniosku że już chyba wiem gdzie jest problem,

prawdopodobnie lepiej będę musiał zrozumieć jak działa rekurencja i jej kopie wstecz po napotkaniu przypadku podstawowego, jaki proces dokładnie w nich zachodzi kopia po kopi i ich niszczenie. Rekurencja, pewnie nie jedna bolączka w programowaniu. 

(debugger nie ma nic do rzeczy, sortowanie działa w porządku, )

Rekurencja ==  

---

Nie analizowałem bardzo kodu, ale musisz pamiętać, że zmienne mogą się zmieniać w dziwny sposób, bo gdy program dojdzie do wywołania rekurencyjnego po którym jest jeszcze jakiś kod to gdy już przejdzie wszystkie wywołania, które prowadzą do tej pierwszej rekurencji to zacznie odwikływać to co zostało w postaci tej reszty kodu poniżej wywołania rekurencyjnego. Wartości zmiennych w tych funkcjach nie zmieniają się, sa zapamietywane, nie ma tu żadnej magii. Po prostu to prześledzenie jak te końcówki funkcji rekurencyjnych będą wywoływane jest kłopotliwe :P

---

Własnie o to chodzi, o czym teraz napisałeś, własnie zdałem sobie z tego sprawę, że nawet kopia funkcji może rozpocząć nowy proces rekurencyjny jeśli wykona swoje instrukcje po napotkaniu przypadku podstawowego.

---

void magiaRekurencji(int n) {
	if (n > 0) {
		cout << n << endl;
		magiaRekurencji(n - 1);
		cout << n << endl;
	}
}

int main() {
	magiaRekurencji(5);

}

Może taki prosty kod coś pomoże :P