Recursiune și algoritmi recursivi. Recursiune și algoritmi recursivi Mai jos sunt scrise două proceduri recursive.
Recursiunea este atunci când o subrutină se autoapelează. Când întâlnesc o astfel de construcție algoritmică pentru prima dată, majoritatea oamenilor întâmpină anumite dificultăți, dar cu puțină practică, recursiunea va deveni un instrument de înțeles și foarte util în arsenalul tău de programare.
1. Esența recursiunii
O procedură sau o funcție poate conține apeluri către alte proceduri sau funcții. Inclusiv procedura se poate numi singur. Nu există niciun paradox aici - computerul execută numai secvenţial comenzile pe care le întâlneşte în program şi, dacă este întâlnit un apel de procedură, pur şi simplu începe să execute această procedură. Nu contează ce procedură a dat comanda să o facă.
Un exemplu de procedură recursivă:
Procedura Rec(a: întreg); începe dacă a>
Să luăm în considerare ce se întâmplă dacă punem un apel în programul principal, de exemplu, de forma Rec(3). Mai jos este o diagramă care arată secvența în care sunt executate instrucțiunile.
Orez. 1. Schema bloc a procedurii recursive.
Procedura Rec este apelată cu parametrul a = 3. Conține un apel la procedura Rec cu parametrul a = 2. Apelul anterior nu s-a finalizat încă, așa că vă puteți imagina că se creează o altă procedură și prima face să nu-și termine munca înainte de încheierea lucrării. Procesul de apel se încheie când parametrul a = 0. În acest moment sunt executate simultan 4 instanțe ale procedurii. Se apelează numărul de proceduri concurente adâncimea recursiunii.
A patra procedură numită (Rec(0)) va tipări numărul 0 și va ieși. După aceea, controlul revine la procedura care l-a numit (Rec(1)) și este tipărit numărul 1. Și așa mai departe până când toate procedurile sunt finalizate. Rezultatul apelului original va imprima patru numere: 0, 1, 2, 3.
O altă imagine vizuală a ceea ce se întâmplă este prezentată în Fig. 2.
Orez. 2. Executarea procedurii Rec cu parametrul 3 constă în executarea procedurii Rec cu parametrul 2 și tipărirea numărului 3. La rândul său, executarea procedurii Rec cu parametrul 2 constă în executarea procedurii Rec cu parametrul 1 și tipărirea numărului 2. Și curând.
Ca un exercițiu în sine, luați în considerare ce se întâmplă când apelați Rec(4). Luați în considerare și ce se întâmplă atunci când apelați procedura Rec2(4) descrisă mai jos, unde operatorii sunt inversați.
Procedura Rec2(a: întreg); începe scrieln(a); dacă a>0 atunci Rec2(a-1); Sfârșit;
Rețineți că, în exemplele de mai sus, apelul recursiv este în interiorul instrucțiunii condiționate. Aceasta este o condiție necesară pentru ca recursiunea să se termine vreodată. De asemenea, rețineți că procedura se autoapelează cu un parametru diferit de cel cu care a fost apelată. Dacă procedura nu folosește variabile globale, atunci acest lucru este și necesar pentru ca recursiunea să nu continue la infinit.
Este posibilă o schemă puțin mai complexă: funcția A apelează funcția B, care la rândul său îl cheamă pe A. Aceasta se numește recursivitate complexă. Se pare că procedura descrisă mai întâi trebuie să o numească pe cea nedescrisă încă. Pentru ca acest lucru să fie posibil, trebuie să utilizați .
Procedura A(n: întreg); (Descrierea directă (antetul) a primei proceduri) procedura B(n: întreg); (Descrierea directă a celei de-a doua proceduri) procedura A(n: întreg); (Descrierea completă a procedurii A) începe writeln(n); B(n-1); Sfârșit; procedura B(n: întreg); (Descrierea completă a procedurii B) start writeln(n); ifn
Declarația anticipată a procedurii B permite apelarea acesteia din procedura A. Declarația anticipată a procedurii A nu este necesară în acest exemplu și este adăugată din motive estetice.
Dacă recursiunea obișnuită poate fi asemănată cu un ouroboros (Fig. 3), atunci imaginea unei recursiuni complexe poate fi extrasă dintr-un binecunoscut poem pentru copii, în care „Lupii s-au mâncat unul pe altul de frică”. Imaginați-vă doi lupi care se mănâncă unul pe altul și înțelegeți recursiunea complexă.
Orez. 3. Ouroboros - un șarpe care își devorează propria coadă. Desen din tratatul alchimic „Synosius” de Theodore Pelecanos (1478).
Orez. 4. Recursie complexă.
3. Simulați activitatea ciclului folosind recursiunea
Dacă procedura se numește singură, atunci, de fapt, aceasta duce la execuția repetată a instrucțiunilor conținute în ea, care este similară cu funcționarea unei bucle. Unele limbaje de programare nu conțin deloc constructe în buclă, lăsând programatorii să organizeze repetiții folosind recursiunea (de exemplu, Prolog, unde recursiunea este tehnica principală de programare).
De exemplu, să simulăm activitatea buclei for. Pentru a face acest lucru, avem nevoie de o variabilă contor de pași, care poate fi implementată, de exemplu, ca parametru de procedură.
Exemplul 1
Procedură LoopImitation(i, n: întreg); (Primul parametru este numărul de pași, al doilea parametru este numărul total de pași) begin writeln("Hello N ", i); //Iată orice afirmații care se vor repeta dacă i Rezultatul unui apel precum LoopImitation(1, 10) va fi executarea de instrucțiuni de zece ori cu o schimbare a contorului de la 1 la 10. În acest caz, va fi imprimat: Salut N1 În general, nu este greu de observat că parametrii procedurii sunt limitele modificării valorilor contorului. Puteți schimba apelul recursiv și instrucțiunile care trebuie repetate, ca în exemplul următor. Exemplul 2
Procedura LoopImitation2(i, n: întreg); începe dacă i În acest caz, procedura va fi apelată recursiv înainte ca instrucțiunile să fie executate. O nouă instanță a procedurii va apela, în primul rând, o altă instanță și așa mai departe, până ajungem la valoarea maximă a contorului. Abia după aceea ultima dintre procedurile apelate își va executa instrucțiunile, apoi penultima își va executa instrucțiunile și așa mai departe. Rezultatul apelării LoopImitation2(1, 10) este de a tipări salutările în ordine inversă: Salutare N 10 Dacă ne imaginăm un lanț de proceduri numite recursiv, atunci în exemplul 1 îl parcurgem de la proceduri numite mai devreme la cele ulterioare. În exemplul 2, invers, de la mai târziu la mai devreme. În cele din urmă, un apel recursiv poate fi plasat între două blocuri de instrucțiuni. De exemplu: Procedura LoopImitation3(i, n: întreg); begin writeln("Bună ziua N", i); (Acesta ar putea fi primul bloc de declarații) dacă i Aici, mai întâi, instrucțiunile din primul bloc sunt executate secvențial, apoi instrucțiunile celui de-al doilea bloc sunt executate în ordine inversă. Când apelăm LoopImitation3(1, 10) obținem: Salut N1 Ar fi nevoie de două bucle deodată pentru a face același lucru fără recursivitate. Puteți profita de faptul că execuția părților aceleiași proceduri este distanțată în timp. De exemplu: Exemplul 3: Convertirea unui număr în binar.
Obținerea cifrelor unui număr binar, după cum știți, are loc prin împărțirea cu un rest la baza sistemului numeric 2. Dacă există un număr, atunci ultima lui cifră din reprezentarea sa binară este egală cu Luând partea întreagă a împărțirii la 2: obținem un număr care are aceeași reprezentare binară, dar fără ultima cifră. Astfel, este suficient să repetăm cele două operații de mai sus până când în câmpul următoarei diviziuni obținem partea întreagă egală cu 0. Fără recursivitate, va arăta astfel: În timp ce x>0 începe c:=x mod 2; x:=x div 2; scrie (c); Sfârșit; Problema aici este că cifrele reprezentării binare sunt calculate în ordine inversă (mai întâi mai târziu). Pentru a imprima un număr în forma sa normală, va trebui să vă amintiți toate numerele din elementele matricei și să le scoateți într-o buclă separată. Cu recursiunea, este ușor să obțineți rezultate în ordinea corectă fără o matrice și o a doua buclă. Și anume: Procedura BinaryRepresentation(x: întreg); var c, x: întreg; începe (Primul bloc. Execut în ordinea apelului procedurii) c:= x mod 2; x:=x div 2; (apel recursiv) dacă x>0 atunci BinaryRepresentation(x); (Al doilea bloc. Se rulează în ordine inversă) write(c); Sfârșit; În general, nu am primit niciun câștig. Cifrele reprezentării binare sunt stocate în variabile locale, care sunt diferite pentru fiecare instanță care rulează a procedurii recursive. Adică, memoria nu a putut fi salvată. Dimpotrivă, cheltuim memorie suplimentară stocând multe variabile locale x. Cu toate acestea, o astfel de soluție mi se pare frumoasă. Se spune că o secvență de vectori este dată de o relație de recurență dacă este dat vectorul inițial și dependența funcțională a următorului vector de cel anterior. Un exemplu simplu de mărime calculată folosind relații de recurență este factorialul Următorul factorial poate fi calculat din precedentul astfel: Introducând notația , obținem relația: Vectorii din formula (1) pot fi interpretați ca seturi de valori variabile. Apoi, calculul elementului necesar al secvenței va consta în actualizarea repetată a valorilor acestora. În special pentru factorial: X:= 1; pentru i:= 2 la n face x:= x * i; scrieln(x); Fiecare astfel de actualizare (x:= x * i) este apelată repetare, și procesul de repetare a iterațiilor repetare. Rețineți, totuși, că relația (1) este o definiție pur recursivă a unei secvențe, iar calculul celui de-al n-lea element este de fapt o luare repetată a funcției f de la sine: În special, pentru factorial se poate scrie: Funcție Factorial(n: întreg): întreg; începe dacă n > 1 atunci Factorial:= n * Factorial(n-1) else Factorial:= 1; Sfârșit; Ar trebui să se înțeleagă că apelurile de funcție implică o supraîncărcare suplimentară, astfel încât prima opțiune pentru calcularea factorialului va fi ceva mai rapidă. În general, soluțiile iterative funcționează mai rapid decât cele recursive. Înainte de a trece la situațiile în care recursiunea este utilă, să ne uităm la un alt exemplu în care nu ar trebui să fie folosită. Luați în considerare un caz special de relații de recurență, când următoarea valoare din secvență depinde nu de una, ci de mai multe valori anterioare simultan. Un exemplu este binecunoscuta succesiune Fibonacci, în care fiecare element următor este suma celor doi anteriori: Cu o abordare „frontală”, puteți scrie: Fib(n: întreg): întreg; începe dacă n > 1 atunci Fib:= Fib(n-1) + Fib(n-2) altfel Fib:= 1; Sfârșit; Fiecare apel către Fib creează două copii ale lui însuși simultan, fiecare dintre copii creează încă două și așa mai departe. Numărul de operațiuni crește odată cu numărul n exponențial, deși pentru o soluție iterativă, liniar în n numarul de operatii. De fapt, exemplul de mai sus ne învață că nu CÂND recursiunea nu trebuie folosită și CUM nu trebuie folosit. La urma urmei, dacă există o soluție iterativă rapidă (bazată pe buclă), atunci aceeași buclă poate fi implementată folosind o procedură sau o funcție recursivă. De exemplu: // x1, x2 – condiții inițiale (1, 1) // n – numărul funcției de număr Fibonacci cerută Fib(x1, x2, n: întreg): întreg; varx3: întreg; începe dacă n > 1 atunci începe x3:= x2 + x1; x1:=x2; x2:=x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; Sfârșit; Cu toate acestea, sunt preferate soluțiile iterative. Întrebarea este, atunci când ar trebui folosită recursiunea? Orice proceduri și funcții recursive care conțin un singur apel recursiv la sine sunt ușor înlocuite cu bucle iterative. Pentru a obține ceva care nu are o contraparte simplă nerecursivă, ar trebui să apelați la proceduri și funcții care se numesc de două sau mai multe ori. În acest caz, setul de proceduri numite nu mai formează un lanț, ca în Fig. 1, dar întregul copac. Există clase largi de probleme când procesul de calcul trebuie organizat în acest fel. Doar pentru ei, recursiunea va fi cea mai simplă și naturală modalitate de rezolvare. Baza teoretică pentru funcțiile recursive care se numesc de mai multe ori este ramura matematicii discrete care studiază arborii. Definiție:
vom numi mulţimea finită T, constând din unul sau mai multe noduri, astfel încât: Această definiție este recursivă. Pe scurt, un copac este un set format dintr-o rădăcină și subarbori atașați de acesta, care sunt și copaci. Arborele este definit prin el însuși. Cu toate acestea, această definiție are sens, deoarece recursiunea este finită. Fiecare subarbore conține mai puține noduri decât arborele care îl conține. În cele din urmă, ajungem la subarbori care conțin un singur nod, iar acest lucru este deja clar despre ce este vorba. Orez. 3. Arborele. Pe fig. 3 prezintă un arbore cu șapte noduri. Deși copacii obișnuiți cresc de jos în sus, se obișnuiește să-i desenezi invers. Când desenați o diagramă manual, această metodă este evident mai convenabilă. Din cauza acestei inconsecvențe, uneori apare confuzia atunci când se spune că unul dintre noduri este deasupra sau sub celălalt. Din acest motiv, este mai convenabil să folosiți terminologia folosită în descrierea arborilor genealogici, apelând nodurile mai apropiate de strămoșii rădăcinii și descendenții mai îndepărtați. Grafic, un copac poate fi reprezentat în alte moduri. Unele dintre ele sunt prezentate în Fig. 4. Conform definiției, un arbore este un sistem de mulțimi imbricate, în care aceste mulțimi fie nu se intersectează, fie sunt complet conținute unele în altele. Astfel de seturi pot fi descrise ca regiuni pe un plan (Fig. 4a). Pe fig. 4b, seturile imbricate nu sunt situate pe un plan, ci sunt alungite într-o singură linie. Orez. 4b poate fi văzută și ca o diagramă a unei formule algebrice care conține paranteze imbricate. Orez. 4c oferă un alt mod popular de a reprezenta o structură arborescentă ca o listă registru. Orez. 4. Alte moduri de reprezentare a structurilor arborescente: (a) seturi imbricate; (b) paranteze imbricate; (c) lista cedată. O listă cu LED-uri are o asemănare evidentă cu modul în care este format codul. Într-adevăr, un program scris în cadrul paradigmei de programare structurată poate fi reprezentat ca un arbore format din structuri imbricate. De asemenea, puteți face o analogie între lista registrului și aspectul cuprins în cărți, unde secțiunile conțin subsecțiuni, care la rândul lor conțin subsecțiuni etc. Modul tradițional de numerotare a unor astfel de secțiuni (secțiunea 1, subsecțiunile 1.1 și 1.2, subsecțiunea 1.1.2 etc.) se numește sistemul zecimal Dewey. După cum se aplică arborelui din Fig. 3 și 4 acest sistem va da: 1.A; 1.1B; 1,2C; 1.2.1D; 1.2.2E; 1.2.3F; 1.2.3.1G; În toți algoritmii asociați cu structurile arborescente, apare invariabil una și aceeași idee, și anume ideea trecere sau traversarea copacilor. Acesta este un mod de a vizita nodurile unui arbore în care fiecare nod este parcurs exact o dată. Rezultă o aranjare liniară a nodurilor arborelui. În special, există trei moduri: puteți traversa nodurile în ordine înainte, înapoi și în urmă. Algoritm de traversare înainte: Acest algoritm este recursiv, deoarece parcurgerea unui arbore conține subarbori traversați, iar aceștia, la rândul lor, sunt parcurși conform aceluiași algoritm. În special, pentru arborele din Fig. 3 și 4 parcurgerea directă oferă succesiunea de noduri: A, B, C, D, E, F, G. Secvența rezultată corespunde unei enumerari de la stânga la dreapta a nodurilor atunci când se reprezintă un arbore folosind paranteze imbricate și în zecimală Dewey, precum și merge de sus în jos atunci când este reprezentat ca o listă registru. Atunci când acest algoritm este implementat într-un limbaj de programare, atingerea rădăcinii corespunde efectuării unor acțiuni de către o procedură sau o funcție, iar trecerea prin subarbori corespunde apelurilor recursive către sine. În special, pentru un arbore binar (unde nu provin mai mult de doi subarbori de la fiecare nod), procedura corespunzătoare ar arăta astfel: // Preorder Traversal - Nume în limba engleză pentru procedura de comandă directă PreorderTraversal((Argumente)); începe //Trecerea rădăcinii DoSomething((Argumente)); // Trecerea subarborelului din stânga dacă (Există un subarboresc din stânga) apoi PreorderTransversal((Argumentele 2)); //Se trece subarborele din dreapta dacă (subarborele din dreapta există) atunci PreorderTransversal((Argumentele 3)); Sfârșit; Adică, mai întâi procedura efectuează toate acțiunile și abia apoi au loc toate apelurile recursive. Bypass algoritm în ordine inversă: Adică, toți subarborele sunt parcurși de la stânga la dreapta, iar întoarcerea la rădăcină este situată între aceste traversări. Pentru arborele din fig. 3 și 4, aceasta oferă o succesiune de noduri: B, A, D, C, E, G, F. În procedura recursivă corespunzătoare, acțiunile vor fi localizate în golurile dintre apelurile recursive. În special pentru un arbore binar: // Inorder Traversal este numele în limba engleză pentru procedura de ordine inversă InorderTraversal((Argumente)); începe // Parcurgerea subarborelului din stânga dacă (Există un subarboresc din stânga) apoi InorderTraversal((Argumentele 2)); // Traversând rădăcina DoSomething((Argumente)); // Traversarea subarborelui drept dacă (Există un subarboresc drept) atunci InorderTraversal((Argumentele 3)); Sfârșit; Algoritm de traversare în ordinea terminalului: Pentru arborele din fig. 3 și 4, aceasta va da o succesiune de noduri: B, D, E, G, F, C, A. În procedura recursivă corespunzătoare, acțiunile vor fi localizate după apelurile recursive. În special pentru un arbore binar: // Postorder Traversal este denumirea în limba engleză pentru procedura de ordine finală PostorderTraversal((Argumente)); începe // Parcurgerea subarborelului din stânga dacă (Există un subarboresc din stânga) apoi PostorderTraversal((Argumentele 2)); // Traversarea subarborelui drept dacă (Există un subarboresc drept) atunci PostorderTraversal((Argumentele 3)); // Traversând rădăcina DoSomething((Argumente)); Sfârșit; Dacă unele informații sunt localizate în nodurile arborelui, atunci o structură de date dinamică adecvată poate fi utilizată pentru a le stoca. În Pascal, acest lucru se face cu o variabilă de tip înregistrare care conține pointeri către subarbori de același tip. De exemplu, un arbore binar în care fiecare nod conține un număr întreg poate fi stocat folosind o variabilă de tip PTree, care este descrisă mai jos: Tip PTree = ^TTree; TTree = înregistrare Inf: întreg; LeftSubTree, RightSubTree: PTree; Sfârșit; Fiecare nod este de tip PTree. Acesta este un pointer, adică fiecare nod trebuie creat prin apelarea procedurii New pe el. Dacă nodul este un nod frunză, atunci câmpurile sale LeftSubTree și RightSubTree sunt setate la zero. În caz contrar, nodurile LeftSubTree și RightSubTree sunt create și prin procedura New. Schematic, o astfel de înregistrare este prezentată în Fig. 5. Orez. 5. Reprezentarea schematică a unei înregistrări TTree. Înregistrarea are trei câmpuri: Inf - un număr, LeftSubTree și RightSubTree - indicatoare către înregistrări de același tip TTree. Un exemplu de arbore compus din astfel de înregistrări este prezentat în Figura 6. Orez. 6. Un arbore alcătuit din înregistrări de tip TTree. Fiecare intrare stochează un număr și două indicatori, care pot conține fie zero, sau adrese ale altor înregistrări de același tip. Dacă nu ați lucrat anterior cu structuri formate din înregistrări care conțin link-uri către înregistrări de același tip, atunci vă recomandăm să vă familiarizați cu materialul de pe. Luați în considerare algoritmul pentru desenarea arborelui prezentat în Fig. 6. Dacă fiecare linie este considerată un nod, atunci această imagine satisface pe deplin definiția unui arbore dată în secțiunea anterioară. Orez. 6. Arborele. Rutina recursivă ar trage în mod evident o linie (trunchiul la prima bifurcație) și apoi s-ar autodenomina pentru a desena doi subarbori. Subarborele diferă de arborele care le conține prin coordonatele punctului de plecare, unghiul de rotație, lungimea trunchiului și numărul de ramuri pe care le conțin (cu una mai puțin). Toate aceste diferențe ar trebui făcute parametri ai procedurii recursive. Un exemplu de astfel de procedură, scris în Delphi, este prezentat mai jos: Arborele procedurii(Canvas: TCanvas; //Canvas pe care va fi desenat arborele x,y: extins; //Coordonatele rădăcinii Unghi: extins; //Unghiul la care crește arborele TrunkLength: extins; //Lungimea trunchiului n: întreg / /Numărul de furcături (câte apeluri recursive sunt încă de făcut)); var x2, y2: extins; //Sfârșitul trunchiului (punctul de ramificare) începe x2:= x + Lungimea trunchiului * cos(Unghi); y2:= y - TrunkLength * sin(Unghi); Canvas.MoveTo(round(x), rotund(y)); Canvas.LineTo(round(x2), round(y2)); dacă n > 1, atunci începe Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); Arborele (Pânză, x2, y2, Angle-Pi/4, 0,55*TrunkLength, n-1); Sfârșit; Sfârșit; Pentru a obține Fig. 6 această procedură a fost apelată cu următorii parametri: Arbore(Imagine1.Canvas, 175, 325, Pi/2, 120, 15); Rețineți că desenul se face înaintea apelurilor recursive, adică arborele este desenat în ordine directă. Potrivit legendei, in Marele Templu al orasului Benaras, sub catedrala care marcheaza mijlocul lumii, se afla un disc de bronz pe care sunt fixate 3 tije de diamant, inalte de un cot si groase ca o albina. Cu mult timp în urmă, chiar la începutul timpurilor, călugării acestei mănăstiri erau vinovați în fața zeului Brama. Înfuriat, Brahma a ridicat trei tije înalte și a așezat 64 de discuri de aur pur pe una dintre ele, și în așa fel încât fiecare disc mai mic să se întindă pe cel mai mare. De îndată ce toate cele 64 de discuri sunt transferate de la tija, pe care le-a pus Dumnezeu Brahma când a creat lumea, într-o altă tijă, turnul împreună cu templul se vor transforma în praf și lumea va pieri sub bubuituri de tunete. Indiferent de Brama, acest puzzle a fost propus la sfârșitul secolului al XIX-lea de către matematicianul francez Edouard Lucas. În versiunea vândută, se foloseau de obicei 7-8 discuri (Fig. 7). Orez. 7. Puzzle „Towers of Hanoi”. Să presupunem că există o soluție pentru n-1 disc. Apoi să traduc n discurile trebuie făcute după cum urmează: 1) Ne schimbăm n-1 disc. Din moment ce pentru cazul n= 1 algoritmul de deplasare este evident, apoi prin inducție, prin efectuarea acțiunilor (1) – (3), putem deplasa un număr arbitrar de discuri. Să creăm o procedură recursivă care imprimă întreaga secvență de schimburi pentru un anumit număr de discuri. O astfel de procedură ar trebui să imprime informații despre o tură (de la pasul 2 al algoritmului) la fiecare apel. Pentru trecerile de la punctele (1) și (3), procedura se va apela singură cu numărul de discuri redus cu unul. //n – numărul de discuri //a, b, c – numere de pin. Schimbarea se face de la pinul a, //la pinul b cu pinul auxiliar c. procedura Hanoi(n, a, b, c: întreg); începe dacă n > 1 atunci începe Hanoi(n-1, a, c, b); scrieln(a, " -> ", b); Hanoi(n-1, c, b, a); end else writeln(a, " -> ", b); Sfârșit; Rețineți că setul de proceduri numite recursiv în acest caz formează un arbore parcurs în ordine inversă. Sarcina analizei este de a utiliza șirul existent care conține o expresie aritmetică și valorile cunoscute ale variabilelor incluse în acesta pentru a calcula valoarea expresiei. Procesul de calcul al expresiilor aritmetice poate fi reprezentat ca un arbore binar. Într-adevăr, fiecare dintre operatorii aritmetici (+, -, *, /) necesită doi operanzi, care vor fi și expresii aritmetice și, în consecință, pot fi considerați subarbori. Orez. 8 prezintă un exemplu de arbore corespunzător expresiei: Orez. 8. Arborele de sintaxă corespunzător expresiei aritmetice (6). Într-un astfel de arbore, nodurile frunzelor vor fi întotdeauna variabile (aici X) sau constante numerice, iar toate nodurile interne vor conține operatori aritmetici. Pentru a executa un operator, trebuie mai întâi să-i evaluați operanzii. Astfel, arborele din figură trebuie străbătut în ordinea finală. Secvența corespunzătoare de noduri numit notație de poloneză inversă expresie aritmetică. Când construiți un arbore de sintaxă, ar trebui să acordați atenție următoarei caracteristici. Dacă există, de exemplu, o expresie și vom citi operațiile de adunare și scădere de la stânga la dreapta, apoi arborele de sintaxă corect va conține un minus în loc de un plus (Fig. 9a). De fapt, acest arbore corespunde expresiei.Este posibil să se faciliteze compilarea arborelui dacă analizăm expresia (8) invers, de la dreapta la stânga. În acest caz, arborele prezentat în Fig. 9b, care este echivalent cu arborele 8a, dar nu necesită înlocuirea semnului. În mod similar, de la dreapta la stânga, trebuie să analizați expresiile care conțin operatorii de înmulțire și împărțire. Orez. 9. Arbori de sintaxă pentru exprimare A – b + c la citirea de la stânga la dreapta (a) și de la dreapta la stânga (b). Această abordare nu elimină complet recursiunea. Cu toate acestea, vă permite să vă limitați la un singur apel la procedura recursivă, ceea ce poate fi suficient dacă motivul este preocuparea pentru performanță maximă. Ideea acestei abordări este de a înlocui apelurile recursive cu o buclă simplă care va fi executată de câte ori există noduri în arborele format din procedurile recursive. Ce se va face exact la fiecare pas ar trebui să fie determinat de numărul pasului. Compararea numărului pasului și a acțiunilor necesare nu este o sarcină banală și, în fiecare caz, va trebui rezolvată separat. De exemplu, să presupunem că vrei să faci k bucle imbricate pe n pași în fiecare: Pentru i1:= 0 la n-1 face pentru i2:= 0 la n-1 face pentru i3:= 0 la n-1 face... Dacă k nu este cunoscut în prealabil, atunci este imposibil să le scrieți în mod explicit, așa cum se arată mai sus. Folosind tehnica demonstrată în secțiunea 6.5, puteți obține numărul necesar de bucle imbricate folosind o procedură recursivă: Procedura NestedCycles(Indici: matrice de întregi; n, k, adâncime: întreg); var i: întreg; începe dacă adâncimea Pentru a scăpa de recursivitate și a reduce totul la un singur ciclu, rețineți că dacă numerotăm pașii din sistemul numeric cu bază n, atunci fiecare pas are un număr format din cifrele i1, i2, i3, ... sau din valorile corespunzătoare din tabloul Indexes. Adică, numerele corespund valorilor contoarelor de cicluri. Numărul pasului în sistemul numeric zecimal obișnuit: Pașii totali vor fi nk. După sortarea numerelor lor în sistemul numeric zecimal și traducerea fiecăruia dintre ele într-un sistem cu o bază n, obținem valorile indexului: M:= rotund(IntPower(n, k)); pentru i:= 0 la M-1 nu începe Număr:= i; pentru p:= 0 la k-1 nu începe Indecii := Număr mod n; Number:= Number div n; Sfârșit; Faceți ceva (Indici); Sfârșit; Încă o dată, observăm că metoda nu este universală și pentru fiecare sarcină va trebui să vii cu ceva al tău. 1. Determinați ce vor face următoarele proceduri și funcții recursive. (a) Ce se va imprima următoarea procedură când este apelată Rec(4)? Procedura Rec(a: întreg); începe scrieln(a); dacă a>0 atunci Rec(a-1); scrieln(a); Sfârșit; (b) Care va fi valoarea funcției Nod(78, 26)? Funcția Nod(a, b: întreg): întreg; începe dacă a > b atunci Nod:= Nod(a – b, b) else if b > a then Nod:= Nod(a, b – a) else Nod:= a; Sfârșit; (c) Ce se va imprima prin următoarele proceduri atunci când este apelat A(1)? Procedura A(n: întreg); procedura B(n: întreg); procedura A(n: întreg); începe scrieln(n); B(n-1); Sfârșit; procedura B(n: întreg); începe scrieln(n); ifn (d) Ce se va imprima următoarea procedură când se numește BT(0, 1, 3)? Procedura BT(x: real; D, MaxD: întreg); începe dacă D = MaxD atunci scrie ln(x) altfel începe BT(x - 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); Sfârșit; Sfârșit; 2. Ouroboros - un șarpe care își devorează propria coadă (Fig. 14) în formă extinsă are o lungime L, diametrul în jurul capului D, grosimea peretelui abdominal d. Stabilește câtă coadă poate încăpea în sine și în câte straturi va fi așezată coada după aceea? Orez. 14. Ouroboros desfășurat. 3. Pentru arborele din fig. 10a, indică secvențele de vizite la noduri în ordinea directă, inversă și finală a traversării. 4. Reprezentați grafic arborele dat prin paranteze imbricate: (A(B(C, D), E), F, G). 5. Desenați un arbore de sintaxă pentru următoarea expresie aritmetică: Scrieți această expresie în notație poloneză inversă. 6. Pentru graficul de mai jos (Figura 15), notați matricea de adiacență și matricea de incidență. 1. După calcularea factorialului de un număr suficient de mare de ori (un milion sau mai mult), comparați eficiența algoritmilor recursivi și iterativi. De câte ori va diferi timpul de execuție și cum va depinde acest raport de numărul al cărui factorial este calculat? 2. Scrieți o funcție recursivă care verifică plasarea corectă a parantezelor într-un șir. Cu aranjamentul corect, sunt îndeplinite următoarele condiții: (a) numărul de paranteze de deschidere și de închidere este egal. Exemple de plasare incorectă:)(, ())(, ())((), etc. 3. Linia poate conține paranteze, atât paranteze rotunde, cât și pătrate. Fiecare paranteză de deschidere corespunde unei console de închidere de același tip (rotund - rotund, pătrat - pătrat). Scrieți o funcție recursivă pentru a verifica dacă parantezele sunt corecte în acest caz. Un exemplu de plasare incorectă: ([) ]. 4. Numărul de structuri de paranteză valide cu lungimea 6 este 5: ()()(), (())(), ()(()), ((())), (()()). indicaţie: Structura corectă a parantezei de lungime minimă „()”. Structurile de lungime mai mare se obțin din structuri de lungime mai mică, în două moduri: (a) dacă structura mai mică este între paranteze, 5. Creați o procedură care imprimă toate permutările posibile pentru numerele întregi de la 1 la N. 6. Creați o procedură care imprimă toate subseturile setului (1, 2, ..., N). 7. Creați o procedură care imprimă toate reprezentările posibile ale unui număr natural N ca sumă a altor numere naturale. 8. Creați o funcție care calculează suma elementelor matricei conform următorului algoritm: matricea este împărțită în jumătate, sumele elementelor din fiecare jumătate sunt calculate și adăugate. Suma elementelor din jumătatea matricei se calculează după același algoritm, adică din nou prin împărțirea la jumătate. Diviziunile apar până când piesele de matrice rezultate conțin câte un element și calculul sumei, în consecință, devine banal. cometariu: Acest algoritm este o alternativă la . În cazul tablourilor cu valori reale, de obicei vă permite să obțineți erori de rotunjire mai mici. 10. Creați o procedură care desenează curba Koch (Fig. 12). 11. Reproduce fig. 16. În figură, la fiecare iterație următoare, cercul este de 2,5 ori mai mic (acest coeficient poate fi făcut un parametru). 1. D. Knut. Arta programarii computerelor. v. 1. (secțiunea 2.3. „Copaci”). Prezentarea pe tema „Algoritmi recursivi” a fost creată pentru a pregăti elevii pentru examenul de informatică și TIC. Lucrarea ia în considerare definiția recursiunii, oferă exemple de obiecte grafice definite recursiv. Prezentarea conține modalități de rezolvare a sarcinii nr. 11 din versiunea demo a proiectului Examenului de stat unificat - 2015 în informatică. Prima metodă presupune construirea unui arbore de apeluri, a doua metodă rezolvă problema folosind metoda substituției. Sunt luate în considerare 4 exemple de rezolvare a sarcinilor folosind ambele metode. În plus, prezentarea conține 25 de sarcini pentru antrenament cu răspunsuri de pe site-ul lui Konstantin Polyakov. Pentru a utiliza previzualizarea prezentărilor, creați un cont Google (cont) și conectați-vă: https://accounts.google.com Sarcina nr. 11 UTILIZARE (nivel de bază, timp - 5 minute) Algoritmi recursivi. Autor - Korotun O.V., profesor de informatică, MOU „Școala Gimnazială Nr. 71” Ce trebuie să știți: Recursie - în definiția, descrierea, imaginea unui obiect sau proces în cadrul acestui obiect sau proces în sine, adică situația în care obiectul face parte din el însuși. Stema Federației Ruse este un obiect grafic definit recursiv: în laba dreaptă a vulturului dublu capete descris pe ea, este prins un sceptru, care este încoronat cu o copie redusă a stemei. Întrucât pe această stemă există și un sceptru în laba dreaptă a vulturului, se obține o recursivitate infinită. Stema recursiva a Rusiei În programare, recursiunea este un apel de funcție de la sine, direct sau prin alte funcții, de exemplu, funcția A apelează funcția B, iar funcția B apelează funcția A. Numărul de apeluri de funcții imbricate sau proceduri se numește adâncimea recursiunii. exemplu recursiv: Dacă ai o pată de grăsime pe rochie, nu-ți face griji. Petele de ulei se îndepărtează cu benzină.Petele de benzină se îndepărtează cu o soluție de alcali.Se îndepărtează alcalii cu esență.Se frecau urma de esență cu ulei.Păi deja știi cum să îndepărtezi petele de ulei! Exemplu de sarcină: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); ifn Exemplu de sarcină: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); ifn Exemplu de sarcină: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 9 Exemplu de sarcină: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 10 Exemplu de sarcină: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 11 15 Exemplul #2: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); ifn Exemplul #2: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 13 Exemplul #3: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln("*"); dacă n > 0 atunci începe F(n-2); F(n div 2) end end ; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? 7 5 3 2 3 1 1 1 1 În acest exemplu, nu sunt afișate valorile parametrului n, ci caracterul * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 Exemplul #3: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-2); F(n div 2) end end ; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? * Numărând numărul de „asteriscuri”, obținem 21 În acest exemplu, nu sunt afișate valorile parametrului n, ci simbolul * * * * * * * * * * * * * * * * * * * * * * Exemplul #3: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-2); F(n div 2) end end ; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Să rezolvăm problema fără copac. Fie S(n) numărul de „asteriscuri” care vor fi afișate când F(n) este apelat. Atunci 1+S(n-2)+ S(n div 2), n>0 1 , n Trebuie să știm S(7). S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 Revers: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 S(n)= Exemplul #4: procedura F(n: întreg); începe dacă n Slide 18 Exemplul #4: procedura F(n: întreg); începe dacă n Slide 19 Exemplul #4: procedura F(n: întreg); începe dacă n Exemplul #4: procedura F(n: întreg); începe dacă n Sarcini pentru antrenament Sarcina 1: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-2); F(div 2); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(5)? Raspuns: 34 Sarcina 2: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-2); F(n-2); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(6)? Raspuns: 58 Sarcina 3: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Raspuns: 15 Sarcina 4: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(n-2); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Raspuns: 55 Problema 5: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(n-2); F(div 2); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(6)? Raspuns: 97 Problema 6: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe writeln("*"); F(n-2); F(div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Raspuns: 31 Problema 7: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe writeln("*"); F(n-2); F(div 2); F(div 2); sfârşitul sfârşitului; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Raspuns: 81 Problema 8: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe writeln("*"); F(n-2); F(n-2); F(div 2); sfârşitul sfârşitului; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(6)? Raspuns: 77 Problema 9: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe dacă n > 0 atunci începe F(n-2); F(n-1); F(n-1); Sfârșit; writeln("*"); Sfârșit ; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(5)? Raspuns: 148 Problema 10: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe dacă n > 0 atunci începe scrieln("*"); F(n-2); F(n-1); F(n-1); Sfârșit; writeln("*"); Sfârșit; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(5)? Răspuns: 197 Problema 11: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe dacă n > 1 atunci începe F(n-2); F(n-1); F(div 2); Sfârșit; writeln("*"); Sfârșit ; Câte asteriscuri vor fi tipărite pe ecran când este apelat F(7)? Raspuns: 88 Problema 12: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe dacă n > 2 atunci începe scrieln("*"); F(n-2); F(n-1); F(div 2); Sfârșit ; writeln("*"); Sfârșit; Câte asteriscuri vor fi tipărite pe ecran când se apelează F(6)? Raspuns: 33 Problema 13: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 14: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 15: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 16: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 17: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 18: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 19: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 20: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 21: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 22: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 23: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 24: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn Problema 25: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); ifn
Salut N2
…
Salutare N 10
…
Salut N1
…
Salutare N 10
Salutare N 10
…
Salut N14. Relații recurente. Recursiune și iterație
5. Copaci
5.1. Definiții de bază. Modalități de a descrie copacii
a) Există un nod special numit rădăcina acestui arbore.
b) Nodurile rămase (excluzând rădăcina) sunt conținute în submulțimi disjunse pe perechi, fiecare dintre acestea fiind, la rândul său, un arbore. Copacii se numesc subarbori a acestui copac.
5.2. trecând copaci
5.3. Reprezentarea arborelui în memoria computerului
6. Exemple de algoritmi recursivi
6.1. desen arborelui
6.2. turnurile din hanoi
În acest proces, este necesar ca discul mai mare să nu fie niciodată plasat deasupra celui mai mic. Călugării sunt în dificultate, în ce succesiune trebuie făcute schimburile? Este necesar să le furnizați un software pentru calcularea acestei secvențe.
2) Ne schimbăm n al-lea disc la pinul liber rămas.
3) Mutați teancul de n-1 disc obţinut la alin. (1) de mai sus n al-lea disc.6.3. Analizarea expresiilor aritmetice
7.3. Determinarea unui nod arborescent după numărul său
Întrebări de control
Sarcini
(b) în interiorul oricărei perechi de deschidere - paranteză de închidere corespunzătoare, parantezele sunt plasate corect.
Scrieți un program recursiv pentru a genera toate structurile paranteze valide de lungime 2 n.
(b) dacă două structuri mai mici sunt scrise secvenţial.
Literatură
2. N. Wirth. Algoritmi și structuri de date.Descarca:
Previzualizare:
Subtitrările diapozitivelor:
