Dwa rekurencyjne wywołania funkcji

0

Witam!

Rekurencja nie stwarza mi problemów w pojęciu zasady jej działania w momencie, gdy następuje pojedyncze wywołanie przez funkcję samej siebie. Ale co w momencie, gdy następują dwa lub nawet więcej takich wywołań jedno pod drugim w tej samej funkcji? Jak to wtedy działa?

Pozdrawiam!

0

Tak samo, jak dla jednego wywołania? Tylko jest tego więcej?

0

Nadal rekurencja działa w sposób rekurencyjny - co tu dużo mówić;

Pierwsze wywołanie rekurencyjne opóźnia kolejne w danej instancji funkcji, ale po wykonaniu całego drzewa rekurencji wraca do tej samej instancji i wywołuje kolejne - nic nadzwyczajnego.

0

Wywołania są realizowane jednocześnie w tym samym momencie? Może ktoś mógłby omówić jakiś krótki przykład.

0

Jak mogą byc wywoływane w tym samym momencie?

0

zobacz sobie np. ciąg fibonacciego w rekurencji. w sieci jest pewnie implementacja w każdym możliwym języku. po kolei rozrysuj sobie na kartce jak masz problem - powinno pomóc w ogarnięciu

0
int rek(int a = 5)
{
  funkcja();
  if(a)
    return rek(--a);
  funkcja2();
  return 0;
}
rek(5):
a = 5
funkcja()
5!=0 => rek(4):
funkcja()
4!=0 => rek(3):
funkcja()
3!=0 => rek(2):
funkcja()
2!=0 => rek(1):
funkcja()
1!=0 => rek(0):
0==0
funkcja2()
--> 0
rek(1):
funkcja2()
--> 0
rek(2):
funkcja2()
--> 0
rek(3):
funkcja2()
--> 0
rek(4):
funkcja2()
--> 0
rek(5):
funkcja2()
--> 0

Mam nadzieje, ze nic nie pokręcilem i jest to dość zrozumiałe.

Generelnie działa to tak, ze najpierw są wykonywane instrukcje znajdujące się przed warukiem zakonczenia rekurencji. Jeśli ten warunek zostanie spełniony, to wykonywane są instrukcje, ktore są po tym warunku i rekurencja "wraca do góry". Na stosie jest pamiętane co, to zwróciło każde wywołanie rekurencji + miejsce powrotu, bo przeciez trzeba wiedziec, w ktore miejsce funkcji wrocic jak "wracamy do góry".

0

Ok, mój błąd, chyba źle sformułowałem pytanie. Chodzi mi o takie coś:

public static void mergesort(int pocz, int kon)
    {
      int sr;
      if (pocz<kon) {
        sr=(pocz+kon)/2;
        mergesort(pocz, sr);    // Dzielenie lewej części
        mergesort(sr+1, kon);   // Dzielenie prawej części
        merge(pocz, sr, kon);   // Łączenie części lewej i prawej
      }
    }

Sortowanie przez scalanie, fragment kodu.

Wywołuje się mergesort w tym samym warunku co kolejny mergesort z innymi parametrami. Tego nie mogę sobie wyobrazić ;)

1

No bo jak wywoła się mergesort(pocz, sr); i ta funkcja sie skonczy (warunek if(pocz<kon) nie zostanie spełniony <=> ta czesc tablicy zostanie posortowana) to wróci do mergesort(sr+1, kon);. Tak jak pisałem, rekurencja najpierw idzie "w dół" a poźniej "wraca do góry"

0

Dziękuję za odpowiedź @pingwindyktator, o to mi chodziło, już wszystko jasne :)

0

Niby wszystko jasne, ale dzieją się dziwne rzeczy, przynajmniej niezrozumiałe znowu dla mnie.

Napisałem taki kod, żeby przeanalizować działanie rekurencji takiej, o jakiej mówiłem w tym wątku:


public class Rekurencja {
    
    public static void Req(char znak, int index)
    {            
        
        if(index>0)
        {
            
            System.out.print(znak + "(" + index + ") ");
            
            Req(znak, --index);

            Req('p', --index);
            
        }

    }
    
    public static void main(String args[])
    {
        
        Rekurencja.Req('k',4);
        
    }
    
}

Otrzymuję taki wynik działania tego programu: k(4) k(3) k(2) k(1) p(1) p(2) p(1)

Nie mam pojęcia dlaczego. Rozpisałem wszystko powoli na kartce według tego, jak zrozumiałem wytłumaczony wcześniej przez Was problem. Ale chyba jednak dalej czegoś nie rozumiem. Mógłbym jeszcze się uprzeć że p(1) powinno się pojawić, ale jakim cudem potem jest p(2) w następnym wywołaniu?

Wywołałem funkcję z argumentem ** index=2**, wtedy działanie kończy się na k(1), więc pasowało mi, ale dla większych wartości wykonują się operacje, których nie rozumiem i prosiłbym o wytłumaczenie ;)

1

Nie rozumiem czego nie rozumiesz ;] Przecież zagłębiasz się po prostu przy każdym napotkaniu wywołania funkcji.
W związku z tym kolejność wykonywania operacji w tym twoim kodzie jest taka (poziomy zagłębienia to kolejne stopnie rekurencji, ale chronologia wywołań jest od góry do dolu):

  • wykonując req('k',4) wchodzisz do ifa i wywołujesz
    • req('k',3) w której to znów wchodzisz do ifa i wywołujesz
      • req('k',2) w której to znów wchodzisz do ifa i wywołujesz
        • req('k',1) w której to znów wchodzisz do ifa i wywołujesz
          • req('k',0) w której nie wchodzisz do ifa
        • po wykonaniu req('k',1) w poprzednim kroku przechodzimy do wykonania kolejnej instrukcji czyli req('p',0) (zero, bo drugi raz dekrementujesz index!)
          • req('p',0) w której nie wchodzisz do ifa
        • następnie po wykonaniu req('p',0) wychodzisz z ifa i wracasz z tej funkcji
      • po wykonaniu req('k',2) w poprzednim kroku przechodzimy do wykonania kolejnej instrukcji czyli req('p',1) (jeden bo znów dwa razy dekrementujesz index!)
        • req('p',1) w której wchodzisz do ifa i wywołujesz req('p',0) które oczywiście nic nie robi oraz req('p',-1) które też nic nie robi
      • następnie wychodzimy z ifa i wracamy z funkcji
    • po wykonaniu req('k',3) w poprzednim kroku wywołujemy req('p',2) (dwa, bo znów dwukrotnie dekrementowałeś...)
      • req('p',2) w którym wchodzimy do ifa i wywołujemy sobie req('p',1) oraz req(p,0)

W efekcie mamy na ekranie:
k4, k3, k2, k1, p1, p2, p1

2

Ja bym proponował postawić breakpoint na funkcji i przechodzić sobie po niej krokowo. Przed każdym krokiem tłumacz sobie co zaraz się stanie i sprawdzaj czy program zachował się tak jak sobie założyłeś. Dobrym pomysłem jest też wywleczenie okna stosu podczas debugowania, ale niestety nie w każdym środowisku stos jest pokazany w przyjazny sposób.

0
Shalom napisał(a):

Nie rozumiem czego nie rozumiesz ;] Przecież zagłębiasz się po prostu przy każdym napotkaniu wywołania funkcji.
W związku z tym kolejność wykonywania operacji w tym twoim kodzie jest taka (poziomy zagłębienia to kolejne stopnie rekurencji, ale chronologia wywołań jest od góry do dolu):

  • wykonując req('k',4) wchodzisz do ifa i wywołujesz
    • req('k',3) w której to znów wchodzisz do ifa i wywołujesz
      • req('k',2) w której to znów wchodzisz do ifa i wywołujesz
        • req('k',1) w której to znów wchodzisz do ifa i wywołujesz
          • req('k',0) w której nie wchodzisz do ifa
        • po wykonaniu req('k',1) w poprzednim kroku przechodzimy do wykonania kolejnej instrukcji czyli req('p',0) (zero, bo drugi raz dekrementujesz index!)
          • req('p',0) w której nie wchodzisz do ifa
        • następnie po wykonaniu req('p',0) wychodzisz z ifa i wracasz z tej funkcji
      • po wykonaniu req('k',2) w poprzednim kroku przechodzimy do wykonania kolejnej instrukcji czyli req('p',1) (jeden bo znów dwa razy dekrementujesz index!)
        • req('p',1) w której wchodzisz do ifa i wywołujesz req('p',0) które oczywiście nic nie robi oraz req('p',-1) które też nic nie robi
      • następnie wychodzimy z ifa i wracamy z funkcji
    • po wykonaniu req('k',3) w poprzednim kroku wywołujemy req('p',2) (dwa, bo znów dwukrotnie dekrementowałeś...)
      • req('p',2) w którym wchodzimy do ifa i wywołujemy sobie req('p',1) oraz req(p,0)

W efekcie mamy na ekranie:
k4, k3, k2, k1, p1, p2, p1

Dzięki za odpowiedzi, a ten fragment dopiszę sobie do dekalogu ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1