Algoritm recursiv pentru analiza sarcinii de examen. Recursiune și algoritmi recursivi. Analizarea expresiilor aritmetice

Recursiunea este atunci când o subrutină se autoapelează. Când se confruntă pentru prima dată cu un astfel de design algoritmic, 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. Procedura se poate numi și singură. Nu există niciun paradox aici - computerul execută numai secvenţial comenzile pe care le întâlneşte în program şi, dacă întâlneşte un apel de procedură, pur şi simplu începe să execute această procedură. Nu contează ce procedură a dat comanda pentru a face acest lucru.

Exemplu de procedură recursivă:

Procedura Rec(a: întreg); începe dacă a>

Să luăm în considerare ce se întâmplă dacă se face un apel, de exemplu, de forma Rec(3) în programul principal. Mai jos este o diagramă care arată secvența de execuție a instrucțiunilor.

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ă este creată o altă procedură și prima nu își termină activitatea până când termina. Procesul de apelare se termină când parametrul a = 0. În acest moment, 4 instanțe ale procedurii sunt executate simultan. Se numește numărul de proceduri efectuate simultan adâncimea recursiunii.

A patra procedură numită (Rec(0)) va tipări numărul 0 și va termina munca. După aceasta, controlul revine la procedura care l-a numit (Rec(1)) și numărul 1 este tipărit și așa mai departe până când toate procedurile sunt finalizate. Apelul original va tipări 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. Etc .

Ca un exercițiu pe cont propriu, luați în considerare ce se întâmplă când apelați Rec(4). Luați în considerare și ce s-ar întâmpla dacă ați apela procedura Rec2(4) de mai jos, cu operatorii inversați.

Procedura Rec2(a: întreg); începe scrieln(a); dacă a>0 atunci Rec2(a-1); Sfârşit;

Vă rugăm să rețineți că în aceste exemple apelul recursiv este în interiorul unei instrucțiuni 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 utilizează variabile globale, atunci acest lucru este de asemenea 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ă apeleze o procedură care nu a fost încă descrisă. 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) start writeln(n); B(n-1); Sfârşit; procedura B(n: întreg); (Descrierea completă a procedurii B) start writeln(n); dacă n

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 recursiunii complexe poate fi extrasă din faimosul poem pentru copii, unde „Lupii s-au speriat și s-au mâncat unii pe alții”. Imaginează-ți doi lupi care se mănâncă unul pe altul și vei înțelege 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. Simularea unei bucle folosind recursiunea

Dacă o procedură se autoapelează, în esență provoacă executarea din nou a instrucțiunilor pe care le conține, similar unei bucle. Unele limbaje de programare nu conțin deloc constructe de buclă, lăsând programatorii să organizeze repetiții folosind recursiunea (de exemplu, Prolog, unde recursiunea este o tehnică de programare de bază).

De exemplu, să simulăm funcționarea unei bucle 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 contorul de pași, al doilea parametru este numărul total de pași) begin writeln("Bună ziua N ", i); //Iată instrucțiuni care vor fi repetate dacă i

Rezultatul unui apel de forma LoopImitation(1, 10) va fi executarea de zece ori a instrucțiunilor, schimbând contorul de la 1 la 10. În acest caz, se vor tipări următoarele:

Salutare N 1
Salut N 2
…
Salutare N 10

În general, nu este greu de observat că parametrii procedurii sunt limitele pentru modificarea 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, va avea loc un apel recursiv de procedură înainte ca instrucțiunile să înceapă să fie executate. Noua instanță a procedurii va apela și, în primul rând, o altă instanță, și așa mai departe, până ajungem la valoarea maximă a contorului. Abia după aceasta ultima dintre procedurile apelate își va executa instrucțiunile, apoi penultima își va executa instrucțiunile etc. Rezultatul apelării LoopImitation2(1, 10) va fi tipărirea saluturilor în ordine inversă:

Salutare N 10
…
Salutare N 1

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, dimpotrivă, 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); start writeln("Bună ziua N", i); (Primul bloc de instrucțiuni poate fi localizat aici) dacă i

Aici, instrucțiunile din primul bloc sunt mai întâi executate secvențial, apoi instrucțiunile din al doilea bloc sunt executate în ordine inversă. Când apelăm LoopImitation3(1, 10) obținem:

Salutare N 1
…
Salutare N 10
Salutare N 10
…
Salutare N 1

Ar fi nevoie de două bucle 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 se știe, 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 întreaga parte a împărțirii cu 2:

obținem un număr care are aceeași reprezentare binară, dar fără ultima cifră. Astfel, este suficient să repeți cele două operații de mai sus până când următorul câmp de împărțire primește o parte î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 formă normală, va trebui să vă amintiți toate numerele din elementele matricei și să le imprimați într-o buclă separată.

Folosind recursiunea, nu este dificil 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; start (Primul bloc. Execut în ordinea apelurilor de procedură) c:= x mod 2; x:= x div 2; (apel recursiv) dacă x>0 atunci BinaryRepresentation(x); (Al doilea bloc. Execut în ordine inversă) scrie(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ță de rulare a procedurii recursive. Adică nu a fost posibilă salvarea memoriei. Dimpotrivă, irosim memorie suplimentară stocând multe variabile locale x. Totuși, această soluție mi se pare frumoasă.

4. Relaţii de recurenţă. Recursiune și iterație

Se spune că o secvență de vectori este dată de o relație de recurență dacă vectorul inițial și dependența funcțională a vectorului următor de cel anterior sunt date.

Un exemplu simplu de mărime calculată folosind relații de recurență este factorialul

Următorul factorial poate fi calculat din cel anterior ca:

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, iar procesul de repetare a iterațiilor este repetare.

Să remarcăm, totuși, că relația (1) este o definiție pur recursivă a șirului, iar calculul celui de-al n-lea element este de fapt preluarea 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;

Trebuie să se înțeleagă că apelarea funcțiilor implică o suprasarcină suplimentară, astfel încât prima opțiune pentru calcularea factorialului va fi puțin 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 încă un exemplu în care nu ar trebui să fie folosită.

Să luăm în considerare un caz special de relații recurente, când următoarea valoare din secvență depinde nu de una, ci de mai multe valori anterioare simultan. Un exemplu este celebra succesiune Fibonacci, în care fiecare element următor este suma celor doi anteriori:

Cu o abordare „frontală”, puteți scrie:

Funcția Fib(n: întreg): întreg; începe dacă n > 1 atunci Fib:= Fib(n-1) + Fib(n-2) altfel Fib:= 1; Sfârşit;

Fiecare apel Fib creează două copii ale lui însuși, fiecare copie creează încă două și așa mai departe. Numărul de operații crește odată cu numărul n exponențial, deși cu 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ă, în caz contrar 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; var x3: î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, soluțiile iterative sunt de preferat. Întrebarea este când în acest caz ar trebui să utilizați recursiunea?

Orice proceduri și funcții recursive care conțin doar un apel recursiv la ele însele pot fi ușor înlocuite cu bucle iterative. Pentru a obține ceva care nu are o contraparte simplă nerecursivă, trebuie să recurgeț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, ci un copac întreg. Există clase largi de probleme când procesul de calcul trebuie organizat în acest fel. Pentru ei, recursiunea va fi soluția cea mai simplă și cea mai naturală.

5. Copaci

Baza teoretică pentru funcțiile recursive care se numesc de mai multe ori este ramura matematicii discrete care studiază arborii.

5.1. Definiții de bază. Modalități de a descrie copacii

Definiție: vom numi mulţimea finită T, constând din unul sau mai multe noduri astfel încât:
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 în perechi, fiecare dintre acestea fiind, la rândul său, un arbore. Se numesc copacii subarbori a acestui copac.

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. Un copac 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. Copac.

În fig. Figura 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ă un nod este deasupra sau sub altul. Din acest motiv, este mai convenabil să folosiți terminologia folosită atunci când descriem arbori genealogici, numiți noduri mai apropiate de strămoșii rădăcinii și descendenții celor mai îndepărtați.

Un copac poate fi reprezentat grafic î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). În 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. Figura 4c oferă un alt mod popular de a reprezenta o structură arborescentă ca o listă eșalonată.

Orez. 4. Alte moduri de reprezentare a structurilor arborescente: (a) seturi imbricate; (b) paranteze imbricate; (c) lista de concesiuni.

Lista eșalonată are asemănări evidente cu modul în care este formatat codul programului. Î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 în trepte ș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. Aplicat arborelui din Fig. 3 și 4 acest sistem va da:

1.A; 1.1B; 1,2 C; 1.2.1 D; 1.2.2 E; 1,2,3 F; 1.2.3.1 G;

5.2. Trecând copaci

În toți algoritmii legați de structurile arborescente, apare invariabil aceeași idee și anume ideea trecere sau traversarea copacilor. Acesta este un mod de a vizita nodurile arborescente în care fiecare nod este parcurs exact o dată. Rezultă o aranjare liniară a nodurilor arborelui. În special, există trei moduri: puteți trece prin nodurile în ordinea înainte, inversă și finală.

Algoritm de traversare înainte:

• Ajunge la rădăcină
• Parcurgeți toate subarborele de la stânga la dreapta în ordine directă.

Acest algoritm este recursiv, deoarece parcurgerea unui arbore conține traversarea subarborilor, iar aceștia, la rândul lor, sunt parcurși folosind același algoritm.

În special, pentru arborele din Fig. 3 și 4, traversarea directă oferă o succesiune 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 notație zecimală Dewey, precum și unui pasaj de sus în jos atunci când îl reprezintă ca o listă eșalonată.

La implementarea acestui algoritm într-un limbaj de programare, lovirea rădăcinii corespunde procedurii sau funcției care efectuează unele acțiuni, iar trecerea prin subarbori corespunde apelurilor recursive către sine. În special, pentru un arbore binar (unde fiecare nod are cel mult două subarbori), 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)); //Tranziția subarborelului din stânga dacă (Există un subarboresc din stânga) atunci PreorderTransversal((Argumentele 2)); //Transversal subarborelui drept dacă (Există un subarboresc drept) atunci PreorderTransversal((Argumentele 3)); Sfârşit;

Adică, mai întâi procedura efectuează toate acțiunile și abia apoi au loc toate apelurile recursive.

Algoritm de traversare inversă:

• Treceți prin subarborele din stânga,
• Ajunge la rădăcină
• Treceți prin următorul subarboresc din stânga.
• Ajunge la rădăcină
• etc., până când este străbătut subarborele din dreapta.

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ă succesiunea de noduri: B, A, D, C, E, G, F.

Într-o procedură recursivă corespunzătoare, acțiunile vor fi localizate în spațiile dintre apelurile recursive. În special pentru un arbore binar:

// Inorder Traversal – Nume englezesc pentru procedura de ordine inversă InorderTraversal((Argumente)); începe //Călătorește subarborele din stânga dacă (Există un subarbore din stânga) apoi InorderTraversal((Argumentele 2)); //Trecerea rădăcinii DoSomething((Argumente)); //Traversează subarborele drept dacă (Există un subarboresc drept) atunci InorderTraversal((Argumentele 3)); Sfârşit;

Algoritmul de traversare a ordinului final:

• Treceți prin toate subarborele de la stânga la dreapta,
• Ajunge la rădăcină.

Pentru arborele din fig. 3 și 4, aceasta va da secvența de noduri: B, D, E, G, F, C, A.

Într-o procedură recursivă corespunzătoare, acțiunile vor fi localizate după apelurile recursive. În special pentru un arbore binar:

// Postorder Traversal – Nume în limba engleză pentru procedura finală a comenzii PostorderTraversal((Argumente)); începe //Călătorește subarborele din stânga dacă (Există un subarbore din stânga) apoi PostorderTraversal((Argumentele 2)); //Transcenderea subarborelui drept dacă (Există un subarboresc drept) atunci PostorderTraversal((Argumentele 3)); //Trecerea rădăcinii DoSomething((Argumente)); Sfârşit;

5.3. Reprezentarea unui arbore în memoria computerului

Dacă unele informații sunt localizate în nodurile arborescente, atunci o structură de date dinamică adecvată poate fi utilizată pentru a le stoca. În Pascal, acest lucru se face folosind 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 are un tip PTree. Acesta este un pointer, ceea ce înseamnă că fiecare nod trebuie creat apelând procedura New pe el. Dacă nodul este un nod frunză, atunci câmpurilor sale LeftSubTree și RightSubTree li se atribuie valoarea zero. În caz contrar, nodurile LeftSubTree și RightSubTree sunt create și prin procedura New.

O astfel de înregistrare este prezentată schematic în Fig. 5.

Orez. 5. Reprezentarea schematică a unei înregistrări de tip TTree. Înregistrarea are trei câmpuri: Inf – un număr, LeftSubTree și RightSubTree – indicii către înregistrări de același tip TTree.

Un exemplu de arbore alcătuit 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 oricare 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, vă recomandăm să vă familiarizați cu materialul despre.

6. Exemple de algoritmi recursivi

6.1. Desenând un copac

Să luăm î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.

Procedura recursivă ar trage în mod evident o linie (trunchiul până la prima ramură), apoi s-ar apela la sine pentru a desena cei doi subarbori. Subarborele diferă de arborele care îi conține în coordonatele punctului lor de plecare, unghiului de rotație, lungimea trunchiului și numărul de ramuri pe care le conțin (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 ramuri (câte //apeluri recursive mai rămân)); 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 realizează înaintea apelurilor recursive, adică arborele este desenat în ordine directă.

6.2. Turnurile din Hanoi

Conform legendei din Marele Templu din Banaras, 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 timpului, călugării acestei mănăstiri au comis o ofensă în fața zeului Brahma. Înfuriat, Brahma a ridicat trei tije înalte și a așezat 64 de discuri de aur pur pe unul dintre ele, astfel încât fiecare disc mai mic să se sprijine pe unul mai mare. De îndată ce toate cele 64 de discuri sunt transferate de la tija pe care le-a așezat Dumnezeu Brahma când a creat lumea, la o altă tijă, turnul împreună cu templul se vor transforma în praf și lumea va pieri sub tunete.
Procesul necesită ca discul mai mare să nu ajungă niciodată deasupra celui mai mic. Călugării se află într-o dilemă: în ce ordine ar trebui să facă schimburile? Este necesar să le furnizați un software pentru a calcula această secvență.

Independent de Brahma, acest puzzle a fost propus la sfârșitul secolului al XIX-lea de către matematicianul francez Edouard Lucas. Versiunea vândută folosea de obicei 7-8 discuri (Fig. 7).

Orez. 7. Puzzle „Turnurile din Hanoi”.

Să presupunem că există o soluție pentru n-1 disc. Apoi pentru schimbare n discuri, procedați după cum urmează:

1) Schimbă n-1 disc.
2) Schimbă n al-lea disc pe pinul liber rămas.
3) Mutăm stiva de la n-1 disc primit la punctul (1) de sus n- al-lea disc.

Pentru că pentru caz n= 1 algoritmul de rearanjare este evident, apoi prin inducție, folosind acțiunile (1) – (3), putem rearanja un număr arbitrar de discuri.

Să creăm o procedură recursivă care imprimă întreaga secvență de rearanjamente pentru un anumit număr de discuri. De fiecare dată când este apelată o astfel de procedură, aceasta trebuie să imprime informații despre o tură (de la punctul 2 al algoritmului). Pentru rearanjamente 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ă.

6.3. Analizarea expresiilor aritmetice

Sarcina analizei este de a calcula valoarea expresiei folosind un șir existent care conține o expresie aritmetică și valorile cunoscute ale variabilelor incluse în acesta.

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. Figura 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 finale 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ă ar trebui parcurs în ordinea terminalului. Secvența corespunzătoare de noduri

numit notație poloneză inversă expresie aritmetică.

Când construiți un arbore de sintaxă, ar trebui să acordați atenție următoarei caracteristici. Dacă, de exemplu, există 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). În esență, acest arbore corespunde expresiei. Este posibil să faci crearea unui arbore mai ușor dacă analizezi expresia (8) în sens invers, de la dreapta la stânga. În acest caz, rezultatul este un arbore cu Fig. 9b, echivalent cu arborele 8a, dar care nu necesită înlocuirea semnelor.

În mod similar, de la dreapta la stânga, trebuie să analizați expresiile care conțin operatori 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 o procedură recursivă, ceea ce poate fi suficient dacă motivul este maximizarea performanței.

7.3. Determinarea unui nod arborescent după numărul său

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 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 este necunoscut în prealabil, 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ă numerotați pașii în sistemul de numere radix n, atunci fiecare pas are un număr format din numerele i1, i2, i3, ... sau din valorile corespunzătoare din tabloul Indexes. Adică, numerele corespund valorilor contoarelor de cicluri. Numărul pasului în notație zecimală obișnuită:

Vor fi un total de pași n k. Trecând prin numerele lor în sistemul numeric zecimal și transformând fiecare dintre ele în sistemul radix 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;

Să remarcăm încă o dată că metoda nu este universală și va trebui să veniți cu ceva diferit pentru fiecare sarcină.

Întrebări de control

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 procedurile de mai jos 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); dacă n

(d) Ce va imprima procedura de mai jos la apelarea 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) când este desfășurat are o lungime L, diametrul în jurul capului D, grosimea peretelui abdominal d. Stabiliți cât de multă coadă poate strânge în sine și în câte straturi va fi așezată coada după aceea?

Orez. 14. Ouroboros extins.

3. Pentru arborele din Fig. 10a indică secvența nodurilor de vizitare în ordinea traversării înainte, înapoi și finală.

4. Descrieți grafic arborele definit folosind paranteze imbricate: (A(B(C, D), E), F, G).

5. Reprezentați grafic arborele de sintaxă pentru următoarea expresie aritmetică:

Scrieți această expresie în notație poloneză inversă.

6. Pentru graficul de mai jos (Fig. 15), notați matricea de adiacență și matricea de incidență.

Sarcini

1. După ce a calculat factorialul 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. Dacă aranjamentul este corect, sunt îndeplinite următoarele condiții:

(a) numărul de paranteze de deschidere și de închidere este egal.
(b) în cadrul oricărei perechi există un suport de deschidere - închidere corespunzător, consolele sunt plasate corect.

Exemple de plasare incorectă:)(, ())(, ())((), etc.

3. Linia poate conține atât paranteze rotunde, cât și pătrate. Fiecare suport de deschidere are un suport de închidere corespunzător de același tip (rotund - rotund, pătrat - pătrat). Scrieți o funcție recursivă care verifică dacă parantezele sunt plasate corect în acest caz.

Exemplu de plasare incorectă: ([) ].

4. Numărul de structuri regulate de paranteză cu lungimea 6 este 5: ()()(), (())(), ()(()), ((())), (()()).
Scrieți un program recursiv pentru a genera toate structurile regulate de paranteze de lungime 2 n.

Notă: Structura corectă a parantezei de lungime minimă „()”. Structurile de lungime mai mare sunt obținute din structuri de lungime mai mică în două moduri:

(a) dacă structura mai mică este luată între paranteze,
(b) dacă două structuri mai mici sunt scrise secvenţial.

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 numărului natural N ca sumă a altor numere naturale.

8. Creați o funcție care calculează suma elementelor matricei folosind următorul 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 este calculată folosind același algoritm, adică din nou prin împărțirea la jumătate. Diviziunile apar până când piesele rezultate ale matricei conțin câte un element fiecare și calcularea sumei, în consecință, devine trivială.

cometariu: Acest algoritm este o alternativă. În cazul tablourilor cu valori reale, de obicei permite erori de rotunjire mai mici.

10. Creați o procedură care desenează curba Koch (Figura 12).

11. Reproduce figura. 16. În figură, la fiecare iterație următoare cercul este de 2,5 ori mai mic (acest coeficient poate fi transformat în parametru).

Literatură

1. D. Knuth. Arta programarii computerelor. v. 1. (secțiunea 2.3. „Copaci”).
2. N. Wirth. Algoritmi și structuri de date.

O prezentare pe tema „Algoritmi recursivi” a fost creată pentru a pregăti studenții pentru Examenul de stat unificat în informatică și TIC. Lucrarea examinează definiția recursiunii și oferă exemple de obiecte grafice definite recursiv. Prezentarea conține metode de rezolvare a sarcinii nr. 11 din versiunea demo a proiectului Unified State Exam - 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. Următoarea prezentare conține 25 de exerciții pentru antrenament cu răspunsuri de pe site-ul lui Konstantin Polyakov.

Descarca:

Previzualizare:

Pentru a utiliza previzualizările prezentării, creați un cont Google și conectați-vă la el: https://accounts.google.com

Subtitrări din diapozitive:

Sarcina nr. 11 Examen de stat unificat (nivel de bază, timp - 5 minute) Algoritmi recursivi. Autor – Korotun O.V., profesor de informatică, Instituția Municipală de Învățământ „Școala Gimnazială Nr. 71”

Ce trebuie să știți: recursiunea este în definirea, descrierea, reprezentarea unui obiect sau proces în cadrul acestui obiect sau proces însuși, adică o situație în care un obiect este o 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 mai mică 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 apelarea unei funcții de la ea însăși, 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 imbricate la o funcție sau procedură se numește profunzimea recursiunii. exemplu de recursivitate: Dacă aveți o pată de grăsime pe rochie, nu vă faceți griji. Petele de ulei se îndepărtează cu benzină. Se îndepărtează petele de ulei.

Exemplu de sarcină: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n

Exemplu de atribuire: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln (n); dacă n

Exemplu de sarcină: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 9

Exemplu de sarcină: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 10

Exemplu de atribuire: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 11

15 Exemplul nr. 2: Se dă un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n

Exemplul nr. 2: dat un algoritm recursiv: procedura F(n: întreg); începe scrieln(n); dacă n Slide 13

Exemplul nr. 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 la apelarea F(7)? 7 5 3 2 3 1 1 1 1 În acest exemplu, simbolul * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 este afișat pe ecran, mai degrabă decât valorile parametru n .

Exemplul nr. 3: dat 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 la apelarea F(7)? * Numărând numărul de „stele”, obținem 21 În acest exemplu, nu valorile parametrului n sunt afișate pe ecran, ci simbolul * * * * * * * * * * * * * * * * * * * * * *

Exemplul nr. 3: dat 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 la apelarea F(7)? Să rezolvăm problema fără copac. Fie S(n) numărul de „stele” care vor fi imprimate la apelarea F(n). 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 nr. 4: procedura F(n: întreg); începe dacă n Slide 18

Exemplul nr. 4: procedura F(n: întreg); începe dacă n Slide 19

Exemplul nr. 4: procedura F(n: întreg); începe dacă n

Exemplul nr. 4: procedura F(n: întreg); începe dacă n

Sarcini de instruire

Problema 1: 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); F(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(5)? Raspuns: 34

Problema 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(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(6)? Raspuns: 58

Problema 3: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(7)? Raspuns: 15

Problema 4: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(n-2); F(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(7)? Raspuns: 55

Problema 5: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe F(n-3); F(n-2); F(n div 2); F(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(6)? Raspuns: 97

Problema 6: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe writeln("*"); F(n-2); F(n div 2); sfârşit sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(7)? Raspuns: 31

Problema 7: Având în vedere un algoritm recursiv: procedura F(n: întreg); începe scrieln ("*"); dacă n > 0 atunci începe writeln("*"); F(n-2); F(n div 2); F(n div 2); sfârşitul sfârşitului; Câte asteriscuri vor fi tipărite pe ecran la apelarea 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(n div 2); sfârşitul sfârşitului; Câte asteriscuri vor fi tipărite pe ecran la apelarea 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; scrieln("*"); Sfârşit ; Câte asteriscuri vor fi tipărite pe ecran la apelarea 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; scrieln("*"); Sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea 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(n div 2); Sfârşit; writeln("*"); Sfârşit ; Câte asteriscuri vor fi tipărite pe ecran la apelarea 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(n div 2); Sfârşit ; writeln("*"); Sfârşit; Câte asteriscuri vor fi tipărite pe ecran la apelarea F(6)? Raspuns: 33

Problema 13: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 14: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 15: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 16: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 17: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 18: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 19: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 20: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 21: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 22: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 23: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 24: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n

Problema 25: Având în vedere un algoritm recursiv: procedura F (n: întreg); începe scrieln(n); dacă n