Rekurzív függvény

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. február 4-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A rekurzív függvény (a latin recursio - return szóból) egy numerikus argumentum numerikus függvénye , amely önmagát tartalmazza a jelölésében. Ez a jelölés lehetővé teszi az értékek kiszámítását az értékekből , hasonlóan az indukciós érveléshez . Ahhoz, hogy bármelyik esetén a számítás befejeződjön , bizonyos esetekben a függvényt nem rekurzívan kell definiálni (például ). $f(n)$ $f(n)$ $f(n-1),f(n-2),\ldots$ $n$ $n$ $n=0,1$

Példák

Példa egy rekurzív függvényre, amely az n- edik Fibonacci - számot adja meg :

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

Ettől a jelöléstől vezérelve, tetszőleges természetes n -re kiszámíthatunk véges számú lépésben. Igaz, az út során még ki kell számítania az értékeket . $F(n)$ $F(n-1),F(n-2),\ldots ,F(2)$

Zárt űrlap

A többletköltség miatt hasznos tudni, hogy egy rekurzív függvénynek van-e nem rekurzív (zárt) alakja.

Előfordulhat, hogy nem található minden rekurzív függvény (reláció) zárt alakja. Némelyikük esetében csak megközelítőleg zárt formákat találtunk. Egyes rekurzív relációk, például a faktoriális elemi matematikai műveleteknek minősülnek.

Például egy rekurzív függvény, amely leírja a természetes számok összegét:

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

zárt formára fordítható: . $f={\frac {n(n+1)}{2}}$

Alkalmazások

A rekurzív függvények fontos szerepet játszanak az algoritmusok elméletében , mivel sok algoritmus rekurzív szerkezettel rendelkezik.

Jegyzetek

↑ Ismétlődő képlet // Wikipédia. — 2020-03-07. Archiválva az eredetiből 2022. június 7-én. (Orosz)