Functie recursiva

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 februarie 2020; verificările necesită 4 modificări .

O funcție recursivă (din latină recursio - return) este o funcție numerică a unui argument numeric care se conține în notația sa. Această notație permite ca valorile să fie calculate din valori , similar raționamentului prin inducție . Pentru ca calculul să se finalizeze pentru orice , este necesar ca pentru unii funcția să fie definită nerecursiv (de exemplu, pentru ). $f(n)$ $f(n)$ $f(n-1),f(n-2),\ldots$ $n$ $n$ $n=0,1$

Exemple

Un exemplu de funcție recursivă care dă al n -lea număr Fibonacci :

$F={\begin{cases}F(0)=0;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cazuri}}$ [unu]

Ghidați de această notație, putem calcula pentru orice n natural într-un număr finit de pași. Adevărat, pe parcurs, va trebui să calculați suplimentar valorile . $F(n)$ $F(n-1),F(n-2),\ldots ,F(2)$

Formular închis

Din cauza supraîncărcării, este util să știți dacă o funcție recursivă are o formă nerecursivă (închisă).

Este posibil să nu fie găsită o formă închisă pentru toate funcțiile recursive (relații). Pentru unele dintre ele s-au găsit doar forme aproximative închise. Unele relații recursive, cum ar fi factorialul , sunt considerate operații matematice elementare.

De exemplu, o funcție recursivă care descrie suma numerelor naturale:

$f={\begin{cases}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{cases))$

poate fi tradus în formă închisă: . $f={\frac {n(n+1)}{2}}$

Aplicații

Funcțiile recursive joacă un rol important în teoria algoritmilor , deoarece mulți algoritmi au o structură recursivă.

Note

↑ Formula recurentă // Wikipedia. — 07-03-2020. Arhivat din original pe 7 iunie 2022. (Rusă)