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. Cel mai simplu mod de a vedea recursiunea este să îndreptați camera Web către ecranul monitorului computerului, desigur, după ce o porniț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ă. 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). 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 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 tot așa până ajungem solutie de baza. Să dezvoltăm un program care declară o funcție recursivă care calculează n!

„stdafx.h” #include << "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// cod Cod::Blocuri

// Cod Dev-C++

// factorial.cpp: Definește punctul de intrare pentru aplicația consolă. #include folosind namespace std; unsigned long int factorial(unsigned long int // prototip al unei funcții recursive int i = 1); // inițializarea unei variabile globale pentru a număra numărul de apeluri recursive unsigned long int rezultat; // variabilă globală pentru stocarea rezultatului returnat al funcției recursive int main(int argc, char* argv) ( int n; // variabilă locală pentru trecerea numărului introdus de la tastatură cout<< "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

Î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ă pentru o funcție recursivă, 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 vizibili 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 diagramei 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ă reelaboră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ă.

folosind namespace std; unsigned long int factorial(unsigned long int // prototip al unei funcții recursive int i = 1); // inițializarea unei variabile globale pentru a număra numărul de apeluri recursive unsigned long int rezultat; // variabilă globală pentru stocarea rezultatului returnat al funcției recursive int main(int argc, char* argv) ( int n; // variabilă locală pentru trecerea numărului introdus de la tastatură cout<< "Enter n!: "; cin >>n; pentru (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n; pentru (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <> <= entered_number; counter++) cout << setw(2) <

// cod Cod::Blocuri

// Cod Dev-C++

// fibonacci.cpp: definește punctul de intrare pentru aplicația de consolă. #include // bibliotecă pentru formatarea informațiilor afișate pe ecran #include folosind namespace std; unsigned long fibonacci(unsigned long // prototip al unei funcții recursive pentru căutarea numerelor din seria Fibonacci int main(int argc, char* argv) ( unsigned long entered_number; cout);<< "Enter number from the Fibonacci series: "; cin >> număr_introdus; for (int counter = 1; counter<= entered_number; counter++) cout << setw(2) <#include folosind namespace std; void tower(int, int, int, int); // declararea unui prototip al unei funcții recursive int count = 1; // variabilă globală pentru numărarea numărului de pași int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>număr; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> tijă_de bază; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // bloc pentru determinarea numărului tijei auxiliare, analizând numerele tijei inițiale și finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lansează o funcție recursivă pentru rezolvarea numărului problemei Towers of Hanoi, // o variabilă care stochează numărul de discuri care trebuie mutate basic_rod, // o variabilă care stochează numărul tijei pe care vor fi inițial discurile localizat help_rod , // o variabilă care stochează numărul tijei, care este folosită ca auxiliar final_rod); // variabila care stocheaza numarul tijei la care trebuie mutate discurile system("pause"); întoarce 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condiție pentru terminarea apelurilor recursive ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// 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 #include folosind namespace std; void tower(int, int, int, int); // declararea unui prototip al unei funcții recursive int count = 1; // variabilă globală pentru numărarea numărului de pași int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>număr; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> tijă_de bază; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // bloc pentru determinarea numărului tijei auxiliare, analizând numerele tijei inițiale și finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lansează o funcție recursivă pentru rezolvarea numărului problemei Towers of Hanoi, // o variabilă care stochează numărul de discuri care trebuie mutate basic_rod, // o variabilă care stochează numărul tijei pe care vor fi inițial discurile localizat help_rod , // o variabilă care stochează numărul tijei, care este folosită ca auxiliar final_rod); // variabila care memoreaza numarul tijei la care trebuie mutate discurile returneaza 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condiție pentru terminarea apelurilor recursive ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

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ă.

Functii: dat recursiv o funcție în definiția sa se conține în special, o funcție definită printr-o formulă recurentă este recursivă. Astfel, într-o expresie puteți da un set infinit de moduri de a calcula o funcție, defini multe obiecte prin tine folosind definiții private specificate anterior.

Date

Struct element_of_list ( element_of_list * next; /* referință la următorul element de același tip */ int date; /* unele date */ ) ;

Structura recursivă a datelor dictează adesea utilizarea recursiunii pentru a procesa aceste date.

În fizică

Un exemplu clasic de recursivitate infinită sunt două oglinzi plasate una față de cealaltă: ele formează două coridoare de reflexii descrescătoare ale oglinzilor.

Un alt exemplu de recursivitate infinită este efectul de autoexcitare (feedback pozitiv) în circuitele electronice de amplificare, când semnalul de la ieșire merge la intrare, este amplificat, se întoarce la intrarea circuitului și este amplificat din nou. Amplificatoarele pentru care acest mod de operare este standard se numesc auto-oscilatoare.

În lingvistică

Capacitatea unei limbi de a genera propoziții și construcții imbricate. Oferta de baza" pisica a mâncat șoarecele» poate fi extins prin recursivitate ca Vanya a ghicit că pisica a mâncat șoarecele, apoi ca Katya știe că Vanya a ghicit că pisica a mâncat șoareceleși așa mai departe. Recursiunea este considerată unul dintre universalele lingvistice, adică este caracteristică oricărei limbi naturale. Cu toate acestea, recent s-a discutat activ despre posibila absență a recursiunii într-una dintre limbile Amazonului - Pirahã, care este remarcată de lingvistul Daniel Everett ( Engleză) .

În cultură

Cele mai multe glume despre recursivitate se referă la recursiunea infinită, în care nu există nicio condiție de ieșire, de exemplu, celebra zicală: „pentru a înțelege recursiunea, trebuie mai întâi să înțelegi recursiunea”.

O glumă foarte populară despre recursivitate, care amintește de o intrare din dicționar:

Mai multe povestiri ale lui Stanislaw Lem sunt dedicate incidentelor (posibile) cu recursivitate infinită:

• povestea despre Ion liniștitul „A paisprezecea călătorie” din „Jurnalele stelelor lui Iyon liniștitul”, în care eroul trece secvenţial de la un articol despre sepulki la un articol despre sepulcare, de acolo la un articol despre sepulcarie, care din nou conține o referire la articolul „sepulki”:

Am gasit urmatoarele informatii scurte:
„SEPULKI sunt un element important al civilizației Ardrite (q.v.) de pe planeta Enteropia (q.v.). Vezi SEPULCARIA."
Am urmat acest sfat si am citit:
„SEPULCARIA - dispozitive pentru sepulție (vezi).”
Am căutat „Sepulenia”; se citi:
„SEPULAREA este ocupația Ardriților (q.v.) de pe planeta Enteropia (q.v.). Vezi SEPULS.”

Lem S. „Jurnalele stelelor lui Iyon the Quiet. Călătoria paisprezece.”

• O poveste din „Cyberiad” despre o mașină inteligentă care avea suficientă inteligență și lene pentru a construi una similară pentru a rezolva o anumită problemă și a-i încredința soluția (rezultatul a fost o recursivitate fără sfârșit, când fiecare mașină nouă a construit una similară și i-a delegat sarcina).
• Acronime recursive: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), etc.

Vezi si

• Secvența de întoarcere

Note

Fundația Wikimedia. 2010.

• Memorie video
• Radiatie electromagnetica

Vedeți ce este „Recursiune” în alte dicționare:

recursiunea- return, repetition Dicționar de sinonime rusești. substantiv recursiv, număr de sinonime: 1 ... Dicţionar de sinonime

recursiunea- - [] recursivitate În sens general, calculul unei funcții folosind un algoritm specific. Exemple de astfel de algoritmi sunt formule recurente care derivă calculul unui termen dat... ... Ghidul tehnic al traducătorului

Recursiune- în sens general, calculul unei funcții folosind un algoritm specific. Exemple de astfel de algoritmi sunt formulele recurente, care derivă calculul unui anumit termen al unei secvențe (cel mai adesea numeric) din calculul mai multor ... Dicţionar economico-matematic

Recursiune- Un model terapeutic în care o condiție sau un criteriu formulat în enunțul original este luat și aplicat enunțului în sine. De exemplu: nu am timp. Cât timp ai avut de petrecut pentru a te asigura că... ... Mare enciclopedie psihologică

RECURSIE- o metodă de determinare a funcțiilor, care face obiectul de studiu în teoria algoritmilor și a altor ramuri ale matematicii. logică. Această metodă a fost folosită mult timp în aritmetică pentru a determina secvențe numerice (progresie, numere Fibonacci etc.).... ... Enciclopedie matematică

recursiunea- (fond) (lat. recursio return). Una dintre cele trei faze ale articulației sunetului, indentarea. Transferarea organelor vorbirii într-o stare calmă sau începerea articulării sunetului următor. În cuvântul odihnă, recursiunea (indentarea) atunci când se articulează [t] se poate suprapune ... ... Dicţionar de termeni lingvistici T.V. Mânz

Acest cuvânt se referă la un proces care se referă la repetarea acelorași elemente într-un „mod auto-similar”. Un exemplu demn de un astfel de proces este păpușa rusă de cuibărit, iar dacă nu ar fi limita posibilităților, atunci o astfel de jucărie s-ar repeta la infinit.

Pe baza unor motive tehnice, recursiunea este încă o cantitate finită.

În programare, acest termen se referă la procesul prin care o funcție se autoapelează sau apelează una din interior. Desigur, apelurile recursive trebuie să aibă condiții de terminare complet fezabile, altfel programul cu alte condiții se va îngheța și se va prăbuși cu o stivă depășită.

Un exemplu de recursivitate matematică este exemplul deja destul de plictisitor de calcul al factorialului. De fapt, recursiunea în programarea web este folosită destul de des și totul pentru că recursiunea este singura opțiune pentru a ocoli orice structură standard atunci când nu știu exact despre dimensiunea reală și adâncimea de imbricare. De asemenea, construcția de grafice nu se poate face fără el. Aceasta este o opțiune clasică.

Pentru a vă asigura că acest proces este necesar, merită să încercați să construiți o hartă a site-ului cu secțiuni conform structurii ierarhice a listelor imbricate. Acest lucru va fi nerealist dacă nu vă limitați în avans la dimensiunea și profunzimea investiției. Dar dacă, până la urmă, construiești ceva asemănător, vei înțelege că la un moment dat întreaga ta structură se va îngheța și va înceta să funcționeze.

Recursiune în motoarele de căutare

Motoarele de căutare depind și de recursivitate. Din momentul în care a fost introdus criteriul autorității site-ului, măsurat prin numărul de link-uri, motoarele de căutare au căzut și ele în aceste rețele. Legătura „masă” a unui site constă în bucăți mici din „masa” tuturor acelor resurse care leagă la acesta. Pentru a calcula acest indicator pentru un site, este necesar să se calculeze „masa” tuturor opțiunilor de link, care, la rândul lor, constau din alte componente similare și așa mai departe, pe întreaga adâncime a rețelei de căutare. Atât pentru recursivitate în practică.

PageRank recursiv de la Google

Acesta este numele dat algoritmului de calcul creat și publicat de Google. Acest algoritm este cunoscut de multă vreme, dar de câte ori este transformat și completat cu tot felul de îmbunătățiri, se bazează în continuare pe aceeași metodă recursivă. Esența rămâne mereu aceeași: calcule, recalculări și din nou recalculări. Rezultatul este din nou aceeași funcție.

TCI recursiv de la Yandex

TIC creat de Yandex are exact aceeași structură ca algoritmul anterior. Singura diferență este că este calculată pentru întregul site ca întreg și nu pentru fiecare pagină individuală. Acesta este motivul pentru care motorul de căutare Yandex trăiește mult mai liber decât alții, deoarece există de multe ori mai puține site-uri decât pagini și este mult mai ușor să le numărați.

Cu toate acestea, acest indicator nu afectează rezultatele căutării în Yandex. În aceste scopuri, el are un VIC profund ascuns, care este analog cu PageRank. Deci, volumul calculelor de la Yandex este, de asemenea, considerabil.

Un algoritm de calcul recursiv bazat pe greutatea legăturilor a arătat că două site-uri care au link-uri unul către celălalt au o pondere nerealist de mare. Prin urmare, imediat după publicarea algoritmului PageRank, optimizatorii au început să promoveze linkurile recursive. Experimentele efectuate au confirmat că metoda utilizată are un rezultat eficient.

Comentează acest articol:

Vă rugăm să vă înregistrați pentru a comenta.

Din latină recursio (întoarcere). În general, acesta este numele dat procesului de repetare a elementelor într-o manieră „auto-similară”.

Un exemplu izbitor de recursivitate sunt păpușile de cuib. Definiție recursiva: „o păpușă de cuib este o păpușă detașabilă din lemn, care conține o păpușă mai mică în interior.” Aceasta este recursivitate în rusă. Și dacă nu ar fi limita capacităților maeștrilor, matrioșca ideală ar intra adânc în sine la nivel atomic. Sau chiar mai profund. Lefty pur și simplu nu avea un domeniu de aplicare suficient de puternic. Limita superioară este, de asemenea, teoretic nelimitată, dar baobabii de o dimensiune adecvată nu cresc pe planeta noastră. În general, din motive tehnice, recursiunea trebuie să fie finită.

În programare (ca și în matematică), recursiunea este procesul prin care o funcție se autoapelează (recursie directă), sau apelează funcția B din interiorul funcției A, care la rândul ei conține un apel la funcția A (recursie indirectă sau reciprocă). Desigur, apelurile recursive trebuie să aibă o condiție de ieșire satisfăcătoare, în caz contrar programul se va bloca, ca într-o buclă infinită - dar, spre deosebire de o buclă infinită, o recursivitate infinită se va prăbuși pe un depășire a stivei.

Exemplu de recursivitate

Cel mai enervant exemplu de recursivitate în programarea matematică este calculul factorial. Să nu ne schimbăm tradițiile glorioase. Pentru cei care nu au luat-o încă: N! (factorialul N) este produsul tuturor numerelor naturale de la unu la N (factorialul zero este 1).
Puteți înmulți prost numere de la 1 la N într-o buclă. Sau puteți construi o funcție factorială(n), care va conține o condiție și un apel către sine. Dacă n este egal cu unu, atunci funcția returnează valoarea 1, în caz contrar returnează valoarea lui n înmulțită cu factorial(n-1).
Schițe în PHP

Funcția factorial($n) ( if ($n == 1) ( return 1; ) else ( return intval($n * factorial($n - 1)); ) )

Aplicații practice ale recursiunii

„Ei bine, de ce este nevoie de asta aici?” - ne va întreba un tânăr cititor nerăbdător - „Prostii științifice, oboseală, tot felul de factoriali... Dar practic, de ce să aplici această recursivitate?”
„La ochiul negru al programării web”, vom răspunde fără ezitare. Și vom justifica acest lucru imediat.

De fapt, există mult mai multe utilizări ale recursiunii în programarea web decât pare. Deoarece recursiunea este, probabil, singura modalitate de a traversa orice structură de arbore atunci când nici dimensiunea, nici adâncimea cuibării nu sunt cunoscute dinainte. Apropo, construirea și parcurgerea graficelor nu se poate face fără el. Acesta este un clasic, domnilor - încercați să căutați fișierele necesare într-un arbore de directoare Unix într-un alt mod și vă va deveni imediat clar că fără recursire nu veți ajunge nicăieri.

Încercați să faceți fără ea construind o hartă a site-ului cu o structură ierarhică de secțiuni sub formă de liste imbricate. Ai prefera să te spânzurezi decât să-l construiești dacă nu știi dinainte exact la câte niveluri este limitată adâncimea cuibării. Și chiar dacă știți, dar încercați să faceți fără recursivitate, atunci în loc de o funcție simplă, transparentă și sigură, veți construi un software greoi „raft pe cârje”. Și când termini și îți ștergi fruntea transpirată, adevărul sumbru al vieții va răsări la tine: dacă schimbi adâncimea cuibării, structura ta de răspândire va înceta instantaneu să funcționeze corect. Prin urmare, este puțin probabil să îl puteți utiliza oriunde altundeva.

Recursiune în motoarele de căutare

Da exact. De asemenea, motoarele de căutare nu au unde să scape de recursivitate. De când a fost stabilit obiceiul de a măsura autoritatea unui site (document) după numărul de link-uri, motoarele de căutare au căzut într-o capcană recursivă și le-au lăsat să rătăcească în ea pentru totdeauna (aceasta este dorința sinceră a autorului). Legătura „greutate” a unui site constă în bucăți mici de „greutate” de la toate cele care leagă la acesta. Pentru a calcula această greutate pentru A, la care se referă B, C și D, trebuie să calculați greutatea lor, care, la rândul ei, este transmisă de tot felul de alții, a căror greutate trebuie de asemenea calculată... și așa mai departe în întreaga Rețea luată în considerare în motorul de căutare. O problemă complet recursivă. Și spui că este o teorie completă. Cea mai reală practică.

PageRank recursiv de la Google

Creatorii Google și-au publicat algoritmul de bază pentru calcularea PageRank cu mult timp în urmă. Și indiferent cum s-a schimbat de atunci, indiferent câte îmbunătățiri i-au fost adăugate, baza rămâne aceeași. Nu există nicio modalitate de a ști cât de mult PageRank transmite pagina B ca link către pagina A până când nu numărăm ce a primit pagina PageRank B de la toate celelalte pagini care au legat la ea și asta nu poate fi știut până când numărăm PageRank din acele pagini... vom continua? Probabil că nu mai este necesar. Este din nou Majestatea Sa Recursiune .

La Universitatea Națională din Ucraina de Est, numită după Vladimir Dahl

Recursiune

Informatica si tehnologia calculatoarelor

© Veligura A.V., Departamentul de Cibernetică Economică, 2004

Recursiunea este o tehnică de programare puternică care vă permite să împărțiți o problemă în părți din ce în ce mai mici până când acestea devin atât de mici încât rezolvarea acestor subprobleme se reduce la un set de operații simple.

Odată ce câștigi experiență cu recursiunea, o vei vedea peste tot. Mulți programatori care au stăpânit recent recursiunea se lasă duși de cap și încep să o folosească în situații în care este inutilă și uneori dăunătoare.

Ce este recursiunea?

Recursiunea apare atunci când o funcție sau o subrutină se autoapelează. Drept recursiunea(recursie directă) arată cam așa:

Funcție Factorial (num As Long) As Long

Factorial = num * Factorial(num - 1)

Când recursiunea indirectă(recursiune indirectă) o procedură recursivă apelează o altă procedură, care la rândul său o apelează pe prima:

Ping sub privat (număr ca întreg)

Private Sub Pong (număr ca întreg)

Recursiunea este utilă pentru rezolvarea problemelor care se descompun în mod natural în mai multe subprobleme, fiecare dintre acestea fiind un caz mai simplu al problemei inițiale. Vă puteți gândi la un copac ca la un „trunchi” cu doi copaci mai mici pe el. Apoi puteți scrie o procedură recursivă pentru a desena arbori:

Sub DrawTree privat()

Desenați „trunchiul”

Desenați un copac mai mic rotit -45 de grade

Desenați un copac mai mic rotit la 45 de grade

Deși recursiunea poate face unele probleme mai ușor de înțeles, oamenii, în general, nu gândesc recursiv. De obicei, se străduiesc să despartă sarcinile complexe în sarcini mai mici care pot fi finalizate una după alta până la finalizare. De exemplu, pentru a picta un gard viu, puteți începe de la marginea din stânga și puteți continua spre dreapta până când ați terminat. Probabil că nu vă gândiți la posibilitatea de a colora recursiv jumătatea din stânga a gardului mai întâi, și apoi de a colora recursiv jumătatea dreaptă atunci când efectuați o sarcină ca aceasta.

Pentru a gândi recursiv, trebuie să împărțiți o problemă în subprobleme, care pot fi apoi împărțite în subprobleme mai mici. La un moment dat, sarcinile secundare devin atât de simple încât pot fi efectuate direct. Când subsarcinile sunt finalizate, subsarcinile mai mari care sunt compuse din ele vor fi, de asemenea, finalizate. Sarcina inițială va fi finalizată când toate sarcinile sale secundare sunt finalizate.

1. Pericolele recursiunii

   1. Recursie infinită

Cel mai evident pericol al recursiunii este recursiunea infinită. Dacă algoritmul este construit incorect, funcția poate pierde condiția pentru oprirea recursiunii și se poate executa la nesfârșit. Cel mai simplu mod de a face această greșeală este să uitați pur și simplu să verificați condiția de oprire, așa cum se face în următoarea versiune eronată a funcției factoriale. Deoarece funcția nu verifică dacă a fost atinsă condiția de oprire a recursiunii, se va apela la nesfârșit.

Funcție privată BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)

O funcție se poate autodenomina și pe termen nelimitat dacă condiția de oprire nu termină toate căile posibile de recursivitate. În următoarea versiune buggy a funcției factoriale, funcția se va apela la nesfârșit dacă valoarea de intrare nu este un număr întreg sau dacă este mai mică de 0. Aceste valori nu sunt valori de intrare valide pentru funcția factorială, deci o verificare poate fi necesară într-un program care utilizează valorile de intrare ale acestei funcții. Cu toate acestea, va fi mai bine dacă funcția efectuează această verificare singură.

Funcție privată BadFactorial2(num As Double) As Double

BadFactorial2 = 1

BadFactorial2 = num * BadFactorial2(num-1)

Următoarea versiune a funcției Fibonacci este un exemplu mai complex. Condiția sa de oprire a recursiunii oprește doar câteva căi recursive și are aceleași probleme ca BadFactorial2 dacă valorile de intrare sunt negative sau neîntregi.

Funcție privată BadFib(num As Double) As Double

BadFib = BadPib (număr - 1) + BadFib (număr - 2)

Ultima problemă cu recursiunea infinită este că „infinit” înseamnă de fapt „până când spațiul stivei este epuizat”. Chiar și procedurile recursive bine scrise vor duce uneori la o depășire a stivei și la blocarea. Următoarea funcție, care calculează suma lui N + (N - 1) + ... + 2 +1, face ca spațiul de stivă să fie epuizat pentru valori mari ale lui N. Cea mai mare valoare posibilă a lui N la care programul va funcționa în continuare depinde de configurația computerului dvs.

Funcție privată BigAdd(N As Double) As Double

Daca N<= 1 Then

BigAdd=N + BigAdd(N - 1)

Programul BigAdd de pe discul exemplu demonstrează acest algoritm. Testați cât de mare o valoare de intrare puteți introduce în acest program înainte de a provoca o depășire a stivei pe computer.