BitCell

Buna ziua , am un algoritm simplu de gasire a numarului maxim dintr-un sir bazandu-ne pe divide_et_impera .



Intrebarea mea este urmatoarea : avem doua apeluri recursive a functiei divide_et_impera , nu inteleg exact cum se vor apela , banuiesc ca atunci cand se va compila linia aceasta " max=divide_et_impera(p,mij) " se va autoapela functia revenind la inceputul programului mai precis conditia " if (p==q) ". Deci daca de fiecare data cand se ajunge la primul apel al subprogramului se revine la ineputul lui , cum se va ajunge si la al doilea apel care calculeaza maximul din cealalata jumatete a sirului ? . Va multumesc .

Divide et impera imparte problema initiala in probleme din ce in ce mai mici, pana se ajunge la o problema care poate fi rezolvata usor.

Sa presupunem ca noi cautam elementul A (un intreg care are o valoare oarecare). Comparam elementul din mijlocul array-ul cu A: daca A este mai mic, continuam cautarea in prima jumatate a array-ul ... altfel cautam in a doua jumate.

"Continuarea" cautarii se face prin apelul recursiv de care intrebi. Mergi in debugger pas cu pas pentru a vedea ce se intampla - teoriile sunt bune doar pana la un punct . Cautarea se termina atunci cand se gaseste elementul sau cand sirul are doar un singur element, moment in care se revine din apel(uri).

However, codul tau pare ciudat ... am impresia ca tu cauti dupa pozitia elementului, nu dupa valoarea lui.

Anyway, cautarea unui element intr-un vector prin metoda divide et impera se numeste "cautare binara" - poate te ajuta cu ceva .

Bafta

L.E. o reprezentare "vizuala" a unui program care foloseste recursivitate gasesti in tutorialul de Pascal despre functii si proceduri (chiar pe la sfarsit). Spor !

^^ Trebuie să înțelegi ce se întâmplă în culise atunci când se apelează o funcție. Să considerăm că funcția noastră este una simplă :
Apelând funcția prin : se vor întâmpla 3 lucruri :

1. Se va aloca spațiu pe stivă pentru a găzdui atât parametrii funcției cât și variabilele locale declarate în ea + adresa de revenire după terminarea apelului.
2. Se vor inițializa parametrii a cu 1 și b cu 2
3. Se va trece la execuția codului ce-l conține funcția

Grafic, situația s-ar prezenta în felul următor :

Distingem 4 momente (prefixate cu "t = ") importante pe parcursul acestei execuții :

• Momentul 0 : apelul inițial de funcție
• Momentul 1 : alocarea de spațiu pe stivă (cel discutat mai sus)
• Momentul 2 : terminarea funcției
• Momentul 3 : golirea stivei de valori utilizate în cadrul funcției și returnarea la punctul din care s-a declanșat apelul

Dacă acest aspect este clar, vom continua cu cazul tău concret, sharky92. În acest cadru, vom elimina bucăți de cod nefolositoare explicației și vom prezenta, în același spirit, situația stivei pentru un apel recursiv. Generalizarea rămâne la latitudinea imaginației tale, dar nu este un lucru foarte dificil.
Pornim, așadar, cu codul ciopârțit :

Se poate ușor observa că avem relativ aceleași elemente ca și în prima explicație și anume : avem o funcție (?!?), avem parametri (chiar același număr și același tip) și avem și variabile locale. Pe lângă acestea, mai avem și un apel la sine. Să vedem cum se comportă stiva în această situație :
[Dacă nu se vede complet, deschide imaginea într-o filă nouă]
După cum se poate intui, se observă un comportament asemănător.
Analizăm din nou timpii cheie :

• 0 : se realizează apelul inițial
• 1 : stiva inițială este alocată comform principiului de mai sus
• 2 : la un moment dat, in cadrul funcției, avem un apel la ea însăși. În acest moment, se împing pe stivă un alt spațiu necesar funcției susținând acum un total de 2 adrese de returnare, 2 x p, 2 x q, 2 x [orice].
• 3 : apelul recursiv poate continua alocând tot mai multe spații pe stivă
• 4, 5 : la un moment dat, datorită instrucțiunii de control (if-ul acela), ciorchinele colapsează și se revine, din return în return până la suprafața stivei (momentul în care s-a găsit stiva înainte de primul apel al funcției)
• 6 : terminându-se și acest nivel, stiva este complet curățată, iar calculele sunt îndeplinite, execuția programului reluându-se de la instrucțiunea imediat următoare apelului inițial

Și cam asta este tot. Te rog observă că dacă nu există o instrucțiune de control, se poate ajunge la un moment dat la un număr atât de mare de alocări de funcție pe stivă încât programul rămâne fără memorie. Acest lucru se poate materializa printr-un "Don't send" clasic urmat, uneori, de un bine plasat upercut de "End Task".

Spor

Va multumesc pentru raspunsuri si lui eni4ever pentru reprezentarea grafica care ajuta foarte mult . Am inteles cum functioneaza subprogramele recursive, era destul de simplu, dar trebuia un pic de ajutor .