Noțiunea de recurență. Funcții recursive. exemplu
Recursiunea (din latină recursio - întoarcere) este o modalitate de a organiza un proces de calcul în care o procedură sau o funcție, în timpul executării operatorilor constituenți, se transformă în ea însăși.
Pentru ca un astfel de apel să nu fie infinit, textul subprogramului trebuie să conțină o condiție pentru realizarea căreia nu se produce nici o conversie ulterioară. Astfel, inversarea recursivă poate fi inclusă numai în una din ramuri.
Rutinele în Pascal nu există restricții privind apelurile subrutina recursive, trebuie doar să înțeleagă că fiecare rezultate succesive apel recursiv într-o nouă copie a rutinele obiectelor locale și toate copiile, lanțul corespunzător de apeluri recursive activate și completate există în mod independent unul de celălalt
Recursia este folosită pe scară largă în programare, care se bazează pe natura recursivă a multor algoritmi matematici. De asemenea, ar trebui să știți că orice algoritm recursiv poate fi transformat într-un echivalent iterativ (adică folosind construcții ciclice).
În programele mari și complexe, uneori este necesar să se înlocuiască recursiunea prin iterație. Faptul este că recursiunea este asociată cu mai multe apeluri de procedură, iar acest lucru este oarecum mai puțin eficient atunci când se efectuează comparativ cu utilizarea buclelor. Cu toate acestea, versiunile recursive ale programelor, de regulă, sunt mult mai scurte și mai evidente.
O bună ilustrare a mecanismului de recursiune este funcția de calcul al factorială a unui număr natural. Reamintim că factorialul unui număr este produsul tuturor numerelor naturale de la 1 la acest număr inclusiv:
N! = 1 * 2 * 3 *. * (N-2) * (N-1) * N1! = 1 0! = 1
În primul rând, vom arăta funcția obișnuită non-recursivă pentru calculul factorialului, care realizează un algoritm de calcul iterativ:
Funcția NonRecFact (N: întreg). LongInt; Var i. întreg; Res. LongInt; Începeți Res: = 1; pentru i: = 1 la N face res: = Res * i; NonResFact: = Res; End;
Articole similare
Trimiteți-le prietenilor: