Rekursiv funktion

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 4 februari 2020; kontroller kräver 4 redigeringar .

En rekursiv funktion (från latin recursio - retur) är en numerisk funktion av ett numeriskt argument som innehåller sig själv i dess notation. Denna notation gör att värden kan beräknas från värden , liknande resonemang genom induktion . För att beräkningen ska slutföras för någon , är det nödvändigt att för vissa funktionen definieras icke-rekursivt (till exempel för ). $f(n)$ $f(n)$ $f(n-1),f(n-2),\ldots$ $n$ $n$ $n=0,1$

Exempel

Ett exempel på en rekursiv funktion som ger det n :te Fibonacci- talet :

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

Med hjälp av denna notation kan vi beräkna för vilket naturligt n som helst i ett ändligt antal steg. Det är sant att på vägen måste du dessutom beräkna värdena på . $F(n)$ $F(n-1),F(n-2),\ldots ,F(2)$

Stängt formulär

På grund av overheaden är det användbart att veta om en rekursiv funktion har en icke-rekursiv (sluten) form.

En sluten form kanske inte finns för alla rekursiva funktioner (relationer). För några av dem har endast ungefärliga slutna former hittats. Vissa rekursiva relationer, såsom den faktoriella , anses vara elementära matematiska operationer.

Till exempel, en rekursiv funktion som beskriver summan av naturliga tal:

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

kan översättas till sluten form: . $f={\frac {n(n+1)}{2}}$

Applikationer

Rekursiva funktioner spelar en viktig roll i teorin om algoritmer , eftersom många algoritmer har en rekursiv struktur.

Anteckningar

↑ Återkommande formel // Wikipedia. — 2020-03-07. Arkiverad från originalet den 7 juni 2022. (ryska)