Przez jakiś czas nie miałem kontaktu z algorytmami i obecnie zacząłem przeglądać moje koncepcje. Ku mojemu zdziwieniu ostatni raz, jaki pamiętam z mojej umiejętności rekursji był taki, że byłem w tym dobry, ale już nie. Mam dla was podstawowe pytanie, które mnie dezorientuje. Najpierw zobacz poniższy kod ..

private void mergesort(int low, int high) {
    if (low < high) {
        int middle = (low + high)/2 ;
        System.out .println ("Before the 1st Call");
        mergesort(low, middle);
        System.out .println ("After the 1st Call");
        mergesort(middle+1, high);
        System.out .println ("After the 2nd Call");
        merge(low, middle, high);
    }
}

Wywołanie funkcji

mergesort(0,7);

A wyjście jest

Przed pierwszym wezwaniem

Przed pierwszym wezwaniem

Przed pierwszym wezwaniem

Po pierwszym wezwaniu

Po drugim wezwaniu

Po pierwszym wezwaniu

Przed pierwszym wezwaniem

Po pierwszym wezwaniu

Po drugim wezwaniu

Po drugim wezwaniu

Po pierwszym wezwaniu

Przed pierwszym wezwaniem

Przed pierwszym wezwaniem

Po pierwszym wezwaniu

Po drugim wezwaniu

Po pierwszym wezwaniu

Przed pierwszym wezwaniem

Po pierwszym wezwaniu

Po drugim wezwaniu

Po drugim wezwaniu

Po drugim wezwaniu

Rzeczą wprowadzającą w błąd w powyższym kodzie i wyniku jest drugie wywołanie rekurencyjne. Rozumiem przepływ aż do czwartej linii wyjściowej (tj. Po 1. wywołaniu). Ale nie mogę zrozumieć, dlaczego wychodzi (po drugim wywołaniu) po (po pierwszym wywołaniu). Zgodnie z whati rozumiem z kodu Po wyjściu (po pierwszym wywołaniu) należy wywołać funkcję mergesort z parametrem (środkowy + 1, wysoki) i powinna ona wywołać (przed pierwszym wywołaniem) i przejść do wywołania rekurencyjnego z mergesort (niski, środkowy). Jestem kompatybilny z jedną rekurencyjną funkcją wywołania i rozumiem ją oraz synchronizuję z przykładem foreg fibonacci.