Funcții recursive în C. Recursiune și algoritmi recursivi
Recursiunea este atunci când o subrutină se autoapelează. Când se confruntă pentru prima dată cu o astfel de construcție algoritmică, majoritatea oamenilor întâmpină anumite dificultăți, dar cu puțină practică, recursiunea va deveni clară și foarte unealtă folositoareî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ă se creează 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 este tipărit numărul 1. Și așa mai departe până când toate procedurile sunt finalizate. Rezultatul 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 .
La fel de exercițiu independent gândește-te la ce se întâmplă când apelezi 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 exemplele de mai sus apelul recursiv este în interior operator condițional. Acest conditie necesara 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.
Puțin mai posibil circuit complex: Funcția A apelează funcția B, care la rândul său îl cheamă pe A. Aceasta este numită 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); ( Descriere completa procedurile A) începe scrierea(n); B(n-1); Sfârşit; procedura B(n: întreg); (Descrierea completă a procedurii B) start writeln(n); dacă n
O declarație anticipată a procedurii B îi permite să fie apelată dintr-o procedură A. O declarație anticipată a procedurii A în în acest exemplu nu este necesar și 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”. Imaginați-vă doi lupi care se mănâncă unul pe altul și veți î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ă, ea determină în esență ca instrucțiunile pe care le conține să fie executate din nou, 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 munca pentru buclă. 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 instrucțiunilor de zece ori cu contorul schimbându-se de la 1 la 10. În în acest caz, vor fi tipărite: Salutare N 1 Î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 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); begin 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 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 la 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ă. 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 factoriale: 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 un alt exemplu în care nu ar trebui să fie folosită. Sa luam in considerare caz special relații recurente, când următoarea valoare dintr-o secvență depinde nu de una, ci de mai multe valori anterioare simultan. Un exemplu este celebra succesiune Fibonacci, în care fiecare elementul următor este suma celor două anterioare: 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 ar trebui utilizată recursiunea în acest caz? Orice proceduri recursive iar funcțiile care conțin doar un apel recursiv la ele însele sunt ușor înlocuite cu bucle iterative. Pentru a obține ceva care nu are o contraparte simplă nerecursivă, trebuie 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, 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ă. 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. Un copac este definit prin el însuși. in orice caz 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 confuzie 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 a descrie structurile arborilor: (a) seturi imbricate; (b) paranteze imbricate; (c) lista de concesiuni. Lista eșalonată are asemănări evidente cu metoda de formatare codul programului. Într-adevăr, un program scris în cadrul paradigmei programare structurată, poate fi reprezentat ca un arbore format din structuri imbricate unele în altele. De asemenea, puteți face o analogie între o listă de margine și aspect cuprins în cărțile în care 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; Î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: 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 secvențiale de la stânga la dreapta a nodurilor atunci când se reprezintă un arbore folosind paranteze imbricate și în sistem zecimal Dewey, precum și pasajul de sus în jos atunci când este prezentat sub forma unei liste în trepte. 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 subarborelui din stânga dacă (Există un subarboresc din stânga) atunci PreorderTransversal((Argumentele 2)); //Tranziția 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ă: 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: 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 – Denumire în limba engleză pentru procedura de comandă finală 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; Dacă unele informații se află în nodurile arborelui, atunci puteți utiliza cele corespunzătoare structura dinamica date. În Pascal acest lucru se face folosind tip variabil o î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 – indicatoare 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. Să luăm în considerare algoritmul pentru desenarea arborelui prezentat în Fig. 6. Dacă fiecare linie este considerată un nod, atunci imaginea asta 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); Arbore(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ă. Conform legendei din Marele Templu din Banaras, sub catedrala, marcand 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. Furios, 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. 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. 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); writeln(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ă. Sarcină analizare este de a calcula valoarea expresiei folosind o linie existentă care conține o expresie aritmetică și valorile cunoscute ale variabilelor incluse în aceasta. 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, de asemenea, 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 verso Notație poloneză
expresie aritmetică. Când construiți un arbore de sintaxă, ar trebui să acordați atenție următoarea caracteristică. 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 mai ușoară crearea unui arbore 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. Idee această abordare 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. Prin trecerea prin numerele lor în sistemul numeric zecimal și conversia fiecăruia 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; Faceți ceva (Indici); 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ă. 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 de traversare înainte, inversă și finală. 4. Reprezentaț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ță. 1. După ce am calculat suficient factorialul un numar mare de de ori (un milion sau mai mult), comparați eficiența algoritmilor recursivi și iterativi. Cât de mult 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ă dacă parantezele sunt plasate corect î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. Exemple de plasare incorectă:)(, ())(, ())((), etc. 3. Linia poate conține atât paranteze rotunde, cât și pătrate. Fiecare paranteză de deschidere are o paranteză de închidere corespunzătoare 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: ()()(), (())(), ()(()), ((())), (()()). 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, 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 vizualizările posibile numar natural N ca sumă a altor numere naturale. 8. Creați o funcție care calculează suma elementelor matricei prin la următorul algoritm: Matricea este împărțită în jumătate, se calculează și se adună sumele elementelor din fiecare jumătate. 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 și calcularea sumei, în consecință, devine banală. 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 (din acest coeficient se poate face un parametru). 1. D. Knuth. Arta programarii computerelor. v. 1. (secțiunea 2.3. „Copaci”). Salut Habrahabr! În acest articol vom vorbi despre problemele recursive și despre cum să le rezolvăm. În programare, recursiunea este strâns legată de funcții; mai precis, datorită funcțiilor din programare există un asemenea lucru precum recursiunea sau o funcție recursivă. Cu cuvinte simple, recursiunea este definirea unei părți a unei funcții (metode) prin ea însăși, adică este o funcție care se numește, direct (în corpul ei) sau indirect (prin altă funcție). S-au spus multe despre recursivitate. Iată câteva resurse bune: din retea Orice algoritm implementat în formă recursivă poate fi rescris în formă iterativă și invers. Rămâne întrebarea dacă acest lucru este necesar și cât de eficient va fi. Următoarele argumente pot fi date pentru a justifica acest lucru. Pentru început, putem aminti definițiile recursiunii și iterației. Recursiunea este o modalitate de organizare a procesării datelor în care un program se autoinvocă direct sau cu ajutorul altor programe. Iterația este o modalitate de organizare a prelucrării datelor în care anumite actiuni sunt repetate de multe ori fără a duce la apeluri recursive de program. După care putem concluziona că sunt interschimbabile între ele, dar nu întotdeauna cu aceleași costuri în ceea ce privește resursele și viteza. Pentru a justifica acest lucru, putem da următorul exemplu: există o funcție în care, pentru a organiza un anumit algoritm, există o buclă care execută o secvență de acțiuni în funcție de valoarea curentă a contorului (poate să nu depindă de aceasta). Deoarece există un ciclu, înseamnă că corpul repetă o secvență de acțiuni - iterații ale ciclului. Puteți muta operațiunile într-o subrutină separată și îi puteți transmite valoarea contorului, dacă există. La finalizarea execuției subrutinei, verificăm condițiile de execuție a buclei, iar dacă este adevărată, trecem la un nou apel la subprogram; dacă este fals, încheiem execuția. Deoarece Am plasat tot conținutul buclei într-o subrutină, ceea ce înseamnă că condiția de executare a buclei este plasată și în subrutină și se poate obține prin valoarea de returnare a funcției, parametrii trecuți prin referință sau pointer la subrutină. , precum și variabile globale. Mai mult, este ușor să arătăm că un apel către o anumită subrutină dintr-o buclă poate fi ușor convertit într-un apel sau non-apel (returnarea unei valori sau pur și simplu finalizarea lucrării) a unei subrutine de la sine, ghidat de anumite condiții (cele care au fost anterior în starea buclei). Acum, dacă te uiți la noastre program abstract, arată aproximativ ca transferul de valori la o subrutină și utilizarea lor, pe care subrutina le va schimba la finalizare, de exemplu. am înlocuit bucla iterativă cu un apel recursiv la o subrutină pentru a rezolva un anumit algoritm. Sarcina de a aduce recursiunea la o abordare iterativă este simetrică. Pentru a rezuma, putem exprima următoarele gânduri: pentru fiecare abordare există propria sa clasă de sarcini, care este determinată de cerințele specifice pentru o anumită sarcină. Puteți afla mai multe despre asta Deci funcția recursivă constă din Clasa publică Soluție ( public static int recursion(int n) ( // condiție de ieșire // Caz de bază // când să opriți repetarea recursiunii? if (n == 1) ( return 1; ) // Pas de recursivitate / condiție recursivă return recursive( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // apelează funcția recursivă ) ) Aici condiția de bază este condiția când n=1. Din moment ce știm că 1!=1 și să calculăm 1! nu avem nevoie de nimic. Pentru a calcula 2! putem folosi 1!, i.e. 2!=1!*2. Pentru a calcula 3! avem nevoie de 2!*3... Pentru a calcula n! avem nevoie de (n-1)!*n. Acesta este pasul recursiv. Cu alte cuvinte, pentru a obține valoarea factorială a unui număr n, este suficient să înmulțim valoarea factorială a numărului anterior cu n. Etichete: Adăugați etichete Recursiunea este un fenomen destul de comun care apare nu numai în domeniile științei, ci și în viața de zi cu zi. De exemplu, efectul Droste, triunghiul Sierpinski etc. Cel mai simplu mod de a vedea recursiunea este să îndreptați camera Web către ecranul monitorului computerului, desigur, după ce ați pornit-o mai întâi. Astfel, camera va înregistra imaginea ecranului computerului și o va afișa pe acest ecran, va fi ceva ca o buclă închisă. Ca urmare, vom observa ceva asemănător cu un tunel. În programare, recursiunea este strâns legată de funcții; mai precis, datorită funcțiilor din programare există un asemenea lucru precum recursiunea sau o funcție recursivă. În cuvinte simple, recursiunea este definirea unei părți a unei funcții (metode) prin ea însăși, adică este o funcție care se autoinvocă, direct (în corpul său) sau indirect (prin altă funcție). Problemele recursive tipice sunt: găsirea n!, numerele Fibonacci. Am rezolvat deja astfel de probleme, dar folosind bucle, adică iterativ. În general, tot ceea ce este rezolvat iterativ poate fi rezolvat recursiv, adică folosind o funcție recursivă. Întreaga soluție se rezumă la rezolvarea cazului principal sau, așa cum se mai numește, cazul de bază. Există așa ceva ca un pas recursiv sau un apel recursiv. În cazul în care o funcție recursivă este apelată pentru a rezolva o problemă complexă (nu cazul de bază), se efectuează un număr de apeluri sau pași recursivi pentru a reduce problema la una mai simplă. Și așa mai departe până vom obține o soluție de bază. Să dezvoltăm un program care declară o funcție recursivă care calculează n! „stdafx.h” #include // cod Cod::Blocuri // Cod Dev-C++ // factorial.cpp: Definește punctul de intrare pentru aplicația consolă. #include ÎN rândurile 7, 9, 21 Tipul de date este declarat unsigned long int , deoarece valoarea factorialului crește foarte repede, de exemplu, deja 10! = 3 628 800. Dacă dimensiunea tipului de date nu este suficientă, atunci rezultatul va fi o valoare complet incorectă. Codul declară mai mulți operatori decât sunt necesari pentru a găsi n!. Acest lucru se face astfel încât, după rulare, programul să arate ce se întâmplă la fiecare pas al apelurilor recursive. Vă rugăm să rețineți liniile de cod evidențiate, rândurile 23, 24, 28 este o soluție recursivă pentru n!. Rândurile 23, 24 sunt soluția de bază a unei funcții recursive, adică de îndată ce valoarea din variabilă f va fi egal cu 1 sau 0 (din moment ce știm că 1! = 1 și 0! = 1), apelurile recursive se vor opri, iar valorile vor începe să fie returnate pentru fiecare apel recursiv. Când se întoarce valoarea pentru primul apel recursiv, programul va returna valoarea factorialului calculat. ÎN linia 28 funcția factorial() se autoapelează, dar argumentul său este cu unul mai puțin. Argumentul se reduce de fiecare dată pentru a ajunge la o anumită soluție. Rezultatul programului (vezi Figura 1). Introdu n!: 5 Rezultatul pasului 1= 0 Rezultatul pasului 2= 0 Rezultatul pasului 3= 0 Rezultatul pasului 4= 0 5!=120 Figura 1 - Recursiune în C++ Pe baza rezultatului programului, fiecare pas este clar vizibil și rezultatul la fiecare pas este zero, cu excepția ultimului apel recursiv. A fost necesar să se calculeze cinci factoriali. Programul a efectuat patru apeluri recursive, iar la al cincilea apel a fost găsit cazul de bază. Și odată ce programul a avut o soluție pentru cazul de bază, a rezolvat pașii anteriori și a scos rezultatul general. În Figura 1, sunt vizibile doar patru pași, deoarece în pasul al cincilea a fost găsită o soluție parțială, care în cele din urmă a returnat soluția finală, adică 120. Figura 2 prezintă schema de calcul recursiv 5!. Diagrama arată clar că primul rezultat este returnat atunci când se ajunge la o anumită soluție, dar nu imediat, după fiecare apel recursiv. Figura 2 - Recursiune în C++ Deci să găsesc 5! trebuie sa stii 4! și înmulțiți-l cu 5; 4! = 4*3! și așa mai departe. Conform schemei prezentate în Figura 2, calculul se va reduce la găsirea unui caz special, adică 1!, după care valorile vor fi returnate la fiecare apel recursiv pe rând. Ultimul apel recursiv va returna valoarea 5!. Să reluăm programul pentru găsirea factorialului astfel încât să obținem un tabel de factoriali. Pentru a face acest lucru, vom declara o buclă for în care vom apela funcția recursivă. // cod Cod::Blocuri // Cod Dev-C++ // fibonacci.cpp: definește punctul de intrare pentru aplicația de consolă. #include // cod Cod::Blocuri // Cod Dev-C++ // hanoi_tower.cpp: Definește punctul de intrare pentru aplicația de consolă. // Un program care rezolvă recursiv problema Turnului din Hanoi #include Figura 5 prezintă un exemplu de program recursiv Turnul din Hanoi. Mai întâi, am introdus numărul de discuri egal cu trei, apoi am intrat în tija de bază (întâi) și am desemnat tija finală (a treia). În mod automat, a doua tijă a devenit auxiliară. Programul a produs un rezultat care coincide complet cu soluția animată a acestei probleme. Introduceți numărul de discuri: 3 Introduceți numărul tijei de bază: 1 Introduceți numărul tijei finale: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3 Figura 5 - Recursiune în C++ Se poate observa din figură că mai întâi discul se mișcă de la tija unu la tija trei, apoi de la tija unu la tija doi, de la tija trei la tijadoi, etc. Adică, programul afișează doar secvența mișcărilor discului și numărul minim de pași în care vor fi mutate toate discurile. Toate aceste probleme ar putea fi rezolvate iterativ. Apare întrebarea: „Ce este mai bine de rezolvat, iterativ sau recursiv?” Răspund: „Dezavantajul recursiunii este că consumă mult mai multe resurse computerizate decât iterația. Acest lucru are ca rezultat o sarcină mare atât pe RAM, cât și pe procesor. Dacă este evident că o anumită problemă poate fi rezolvată într-un mod iterativ, atunci ar trebui folosită diferit, folosind recursiunea!” În funcție de problema rezolvată, complexitatea scrierii programelor se modifică atunci când se folosește una sau alta metodă de rezolvare. Dar mai des, o problemă rezolvată folosind o metodă recursivă din punct de vedere al lizibilității codului este mult mai clară și mai scurtă. Pentru a nu scrie un articol uriaș, unde vor exista numeroase exemple de recursivitate în C++, voi mai scrie aici un exemplu de recursivitate. În general, cei care înțeleg elementele de bază și utilizarea recursiunii directe în funcțiile lor pot sări peste acest material. Iată un exemplu de utilizare a recursiunii, ca în articolul Funcții în C++ pentru începători. Recursiune Problema 1 – Folosind recursiunea, afișați factorialul unui număr de la 1 la N #include #include #include int main() getch(); A fost creat un program gol, cred că nu este nevoie să comentezi #include #include #include //Funcția noastră recursivă //0! = 1, 1!=1, 2!=2, 3!=6... Pentru că primele 2 numere sunt una și nu sunt în ordine strictă, forțăm acest punct din cod dacă n<2
return 1
;
int main() Piesa principală într-un program recursiv C++ Funcția noastră recalculează pentru a obține valoarea anterioară. Valoarea reală este parametrul căruia i-a fost transmis n din punctul apelului de funcție. Scopul apelării funcției noastre este să o apelăm din blocul principal al programului. În cazul nostru, îl numim dintr-o funcție int main() Fie ca programatorii să mă ierte pentru o astfel de judecată răvășită. Cam așa percep începătorii recursiunea. Sper că acest blog C++ pentru începători a fost util cuiva și a ajutat pe cineva să înțeleagă conceptul de bază al unei funcții recursive în C++ Notă. În acest articol, ca și în cel precedent, am făcut calculul nu de la 1 la N, ci la valoarea introdusă în program. Ideea este că nu am vrut să scriu o linie suplimentară de cod și am presupus că utilizatorul era deja bine versat în introducerea datelor și afișarea lor pe ecran.
Varg spune: Bună ziua, chiar nu pot înțelege cum efectuează calculele această funcție.
{ După înțelesul meu, în n există 5, condiția nu se potrivește, atunci acest cod se execută sum(n-1)+n, adică ceva obținut între paranteze prin scădere se adaugă la 5, dar ceea ce este (5 - 1) + 5 și dacă da, ce oprește această operație aritmetică:?: :?: :?: Care este valoarea anterioară, de unde vine, cu ce este egală cu:?: :?: :?: Da, aproape totul este așa cum am înțeles (în ultimul paragraf ați arătat recursivitate))), dar rămâne întrebarea: cum se obține suma, care este apoi afișată pe ecran? : (5) //Am dat 5 funcției, am verificat-o pentru egalitate cu unu. nu este egal, a numit din nou funcția, pasând 5-1 în ea 2-1 == 1, s-a terminat de apelat funcția. Da, da, da, nu am avut timp să scriu că am înțeles, totul este corect, ceva nu a trecut imediat. Multumesc site bun)) Și încă nu este complet logic în a 8-a linie dacă modificați numărul returnat de la returnarea 1 la 2, suma se schimbă la 16. Cum este această condiție legată de a 9-a linie? :
Salutare N 2
…
Salutare N 10
…
Salutare N 1
…
Salutare N 10
Salutare N 10
…
Salutare N 14. Relații de recurență. 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 în perechi, fiecare dintre acestea fiind, la rândul său, un arbore. Se numesc copacii subarbori a acestui copac.
5.2. Trecând copaci
5.3. Reprezentarea unui arbore în memoria computerului
6. Exemple de algoritmi recursivi
6.1. Desenând un copac
6.2. Turnurile din Hanoi
Procesul cere asta disc mai mare niciodată nu m-am găsit mai presus de nimic mai puțin. Călugării se află într-o dilemă: în ce ordine ar trebui să facă schimburile? Este necesar să le furnizați software pentru a calcula această secvență.
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.6.3. Analizarea expresiilor aritmetice
7.3. Determinarea unui nod arborescent după numărul său
Întrebări de control
Sarcini
(b) în cadrul oricărei perechi există un suport de deschidere - închidere corespunzător, consolele sunt plasate corect.
Scrieți un program recursiv pentru a genera toate structurile regulate de paranteze de lungime 2 n.
(b) dacă două structuri mai mici sunt scrise secvenţial.
Literatură
2. N. Wirth. Algoritmi și structuri de date.Pe scurt despre recursivitate
Recursiunea este un fenomen destul de comun care apare nu numai în domeniile științei, ci și în Viata de zi cu zi. De exemplu, efectul Droste, triunghiul Sierpinski etc. O modalitate de a vedea recursiunea este să îndreptați camera Web spre ecranul monitorului computerului, desigur, după ce a pornit-o mai întâi. Astfel, camera va înregistra imaginea ecranului computerului și o va afișa pe acest ecran, va fi ceva ca o buclă închisă. Ca urmare, vom observa ceva asemănător cu un tunel.
Se presupune că cititorul este teoretic familiarizat cu recursiunea și știe ce este. În acest articol vom acorda mai multă atenție problemelor recursive. Sarcini
Când învățați recursiunea, cel mai eficient mod de a înțelege recursiunea este rezolvarea problemelor. Cum se rezolvă problemele recursive?
În primul rând, trebuie să înțelegeți că recursiunea este un fel de exagerare. În general, tot ceea ce este rezolvat iterativ poate fi rezolvat recursiv, adică folosind o funcție recursivă.
La fel ca o enumerare (ciclu), recursiunea trebuie să aibă o condiție de oprire - Caz de bază (altfel, la fel ca un ciclu, recursiunea va funcționa pentru totdeauna - infinit). Această condiție este cazul în care merge recursiunea (etapa de recursivitate). La fiecare pas, o funcție recursivă este apelată până când următorul apel declanșează condiția de bază și recursiunea se oprește (sau mai bine zis, revine la ultimul apel funcții). Întreaga soluție se rezumă la rezolvarea cazului de bază. În cazul în care o funcție recursivă este chemată să rezolve sarcină dificilă(nu cazul de bază) sunt efectuate un număr de apeluri sau pași recursivi pentru a reduce problema la una mai simplă. Și așa mai departe până ajungem solutie de baza.
Să ne uităm la asta folosind exemplul de găsire a factorialului:
Cod de scriere
=============================
ETAPA Nr. 1 scrie un program gol
=============================
{
system("cls");
returnează 0;
}
ETAPA Nr. 2 scriem scriem funcția recursivă în sine
=========================================
int fapt (int N)
{
altfel returnează n * fapt (n–1)
//aici funcția se numește singură
}
{
system("cls");
cout<
getch();
returnează 0;
}
ddd
============
returnează n * fapt (n–1)
De ce o scriu nu pe următoarea, ci pe cea anterioară? Când numerele sunt înmulțite, atunci mai întâi 0 * 1 aici este valoarea noastră curentă 1, iar zero este valoarea de calcul anterioară. Aceasta este întreaga esență a recursiunii, calculăm valoarea actuală folosind cea anterioară, în timp ce valoarea anterioară este obținută prin același calcul. Compilatorul însuși calculează valoarea anterioară și stochează această valoare în memorie. Tot ce trebuie să facem este să dăm instrucțiuni.
. Datorită acestei caracteristici a compilatoarelor, o funcție întâlnește o instrucțiune pentru a se autodenomina (în cazul nostru fapt (n–1)
)nu suprascrie parametrul transmis n pentru a calcula funcția. Parametrul transmis la n rămâne în memorie. În acest caz, este definită suplimentar o altă zonă de memorie în care funcția noastră recursivă efectuează calcule recursive pentru a obține rezultatul anterior.
dacă (n==1) returnează 1; //dacă noua valoare este 1, atunci o vom adăuga cu 1, și nu cu cea anterioară. deoarece precedentul este zero. iar adunarea 1+0 va fi infinită.
altfel returnează suma(n-1)+n; //dar dacă n>1, atunci se adună cu valoarea anterioară egală cu suma tuturor elementelor până la n
}
Lucrez cu Dev C++, acest exemplu afișează suma ==15, dacă o numărați așa cum este scris în exemplu, atunci suma se dovedește a fi diferită.
Am scris mai sus, să luăm (5-1)+5=4+5=9
1+2+3+4+5 = 15. Exemplul iese corect.
(5-1+(5)) //...
(4-1+(5-1+(5)))
(3-1+(4-1+(5-1+(5))))
(2-1+(3-1+(4-1+(5-1+(5)))))
(2-1+(3-1+(4-1+(5-1+(5))))) == 15
acesta este rezultatul.
Aici rezultatul funcției este diferența dintre primele două numere, iar n este restul părții drepte
__________________________________
Trebuie doar să înțelegeți corect funcția și să o acceptați ca valoare calculată și să nu o înțelegeți ca variabilă. Este similar cu o variabilă, dar mai aproape de o constantă calculată, deși nu este o constantă, pur și simplu este mai convenabil să o percepem în acest fel.
Și cu aceasta, totul este clar, doar returnarea 2 adaugă privarea sa la sumă, ca să spunem așa.
nu steaua în plus, ci aceasta două, iar dacă scrieți -3, atunci când adăugați o dată va scădea cele trei etc.
Întreaga logică este că orice funcție recursivă are nevoie de un punct de întoarcere.
Legătura cu a noua linie este că un număr este trecut la funcția de sumă atunci când este apelat din interiorul principal; în timpul apelurilor recursive, acest număr este redus cu unul (n-1) de fiecare dată, acest rezultat n-1 este verificat pentru egalitate cu unul și dacă egalitatea este adevărată, atunci întreaga sumă primită va fi însumată cu numărul din acea declarație. în caz contrar, întregul total va fi însumat cu acest nou n-1
