Rekurzivna funkcija je funkcija, katere vrednost v kateri koli točki je mogoče izračunati iz vrednosti funkcije v nekaterih prejšnjih točkah. Na primer, predpostavimo, da je funkcija f(k) = f(k-2) + f(k-3), ki je definirana nad nenegativnim celim številom. Če imamo vrednost funkcije pri k = 0 in k = 2, lahko poiščemo njeno vrednost tudi pri katerem koli drugem nenegativnem celem številu. Z drugimi besedami, lahko rečemo, da se rekurzivna funkcija nanaša na funkcijo, ki uporablja lastne prejšnje točke za določanje naslednjih izrazov in tako tvori zaporedje izrazov. V tem članku bomo skupaj z nekaterimi primeri spoznali rekurzivne funkcije.
Kaj je rekurzija?
Rekurzija se nanaša na proces, v katerem se rekurzivni proces ponavlja. Rekurzivno je nekakšna funkcija ene ali več spremenljivk, običajno določena z določenim postopkom, ki proizvaja vrednosti te funkcije z neprekinjenim izvajanjem določenega odnosa do znanih vrednosti funkcije.
Tukaj bomo razumeli rekurzijo s pomočjo primera.
Recimo, da boste iz pritličja stopili v prvo nadstropje. Če želite to narediti, morate narediti korak za korakom. Do drugega koraka lahko pridete samo do strmega prvega koraka. Recimo, da želite iti na tretji korak; najprej morate narediti drugi korak. Tukaj lahko jasno vidite postopek ponavljanja. Tukaj lahko vidite, da z vsakim naslednjim korakom dodajate prejšnji korak kot ponavljajoče se zaporedje z enako razliko med vsakim korakom. To je dejanski koncept za rekurzivno funkcijo.
2. korak: 1. korak + najnižja stopnica.
3. korak: 2. korak + 1. korak + najnižja stopnica.
4. korak: Korak 3 + korak 2 + korak 1 + najnižja stopnica itd.
Niz naravnih števil je osnovni primer rekurzivnih funkcij, ki se začnejo od ena do neskončnosti, 1,2,3,4,5,6,7,8, 9,…….neskončno. Zato niz naravnih števil prikazuje rekurzivno funkcijo, ker lahko vidite skupno razliko med vsakim členom kot 1; pokaže vsakič, ko se naslednji izraz ponovi s prejšnjim izrazom.
Kaj je rekurzivno definirana funkcija?
Rekurzivno definirane funkcije so sestavljene iz dveh delov. Prvi del obravnava definicijo najmanjšega argumenta, na drugi strani pa drugi del obravnava definicijo n-tega člena. Najmanjši argument je označen z f (0) ali f (1), medtem ko je n-ti argument označen z f (n).
Sledite danemu primeru.
Recimo, da je zaporedje 4,6,8,10
Eksplicitna formula za zgornje zaporedje je f (n)= 2n + 2
Eksplicitna formula za zgornje zaporedje je podana z
f (0) = 2
f(n) = f (n-1) + 2
Zdaj lahko dobimo člene zaporedja z uporabo rekurzivne formule, kot sledi f(2 ) f (1) + 2
f(2) = 6
f (0) = 2
f(1) = f(0) + 2
f (1) = 2 + 2 = 4
f(2 ) = f (1) + 2
f(2) = 4 + 2 = 6
f(3 ) = f (2) + 2
f(3) = 6 + 2 = 8
S pomočjo zgornje formule rekurzivne funkcije lahko določimo naslednji člen.
Kaj naredi funkcijo rekurzivno?
Da bi katera koli funkcija postala rekurzivna, potrebuje svoj izraz za izračun naslednjega člena v zaporedju. Na primer, če želite izračunati n-ti člen danega zaporedja, morate najprej poznati prejšnji člen in člen pred prejšnjim členom. Zato morate poznati prejšnji izraz, da ugotovite, ali je zaporedje rekurzivno ali ne. Torej lahko sklepamo, da če funkcija potrebuje prejšnji člen za določitev naslednjega člena v zaporedju, se funkcija šteje za rekurzivno funkcijo.
Formula rekurzivne funkcije
Če1, a2, a3, a4, a5, a6, ……..an,……je veliko nizov ali zaporedje, potem bo morala rekurzivna formula izračunati vse člene, ki so obstajali prej, da izračuna vrednost
an= an-1 +a1
Zgornjo formulo lahko definiramo tudi kot aritmetično zaporedno rekurzivno formulo. V zgoraj omenjenem zaporedju lahko jasno vidite, da gre za aritmetično zaporedje, ki obsega prvi člen, ki mu sledijo drugi členi, in skupno razliko med vsakim členom. Skupna razlika se nanaša na število, ki jim ga dodate ali odštejete.
Rekurzivno funkcijo lahko definiramo tudi kot geometrijsko zaporedje, kjer imajo množice števil ali zaporedje skupni faktor ali skupno razmerje med seboj. Formula za geometrijsko zaporedje je podana kot
an= an-1 *r
Običajno je rekurzivna funkcija definirana v dveh delih. Prva je izjava prvega člena skupaj s formulo, druga pa je izjava prvega člena skupaj s pravilom, ki se nanaša na zaporedne člene.
Kako napisati rekurzivno formulo za aritmetično zaporedje
Če želite napisati rekurzivno formulo za formulo aritmetičnega zaporedja, sledite podanim korakom
Korak 1:
V prvem koraku se morate prepričati, ali je dano zaporedje aritmetično ali ne (za to morate sešteti ali odšteti dva zaporedna člena). Če dobite enak rezultat, se zaporedje vzame kot aritmetično zaporedje.
2. korak:
Zdaj morate najti skupno razliko za dano zaporedje.
3. korak:
Formulirajte rekurzivno formulo z uporabo prvega izraza in nato ustvarite formulo z uporabo prejšnjega člena in skupne razlike; tako boste dobili dani rezultat
an= an-1 +d
java priorityqueue
zdaj razumemo dano formulo s pomočjo primera
predpostavimo, da je 3,5,7,9,11 dano zaporedje
V zgornjem primeru zlahka ugotovite, da gre za aritmetično zaporedje, ker se vsak člen v zaporedju poveča za 2. Torej je skupna razlika med dvema členoma 2. Poznamo formulo rekurzivnega zaporedja
an= an-1 +d
podano,
d = 2
a1= 3
torej,
a2= a(2-1)+ 2 = a1+2 = 3+2 = 5
a3= a(3-1)+ 2 = a2+2 = 5+2 = 7
a4= a(4-1)+ 2 = a3+2 = 7+2 = 9
a5= a(5-1)+ 2 = a + 2 = 9+2 = 11 in postopek se nadaljuje.
Kako napisati rekurzivno formulo za geometrijsko zaporedje?
Če želite napisati rekurzivno formulo za formulo geometrijskega zaporedja, sledite podanim korakom:
Korak 1
V prvem koraku se morate prepričati, ali je dano zaporedje geometrijsko ali ne (za to morate vsak člen pomnožiti ali deliti s številom). Če dobite enak rezultat od enega do naslednjega izraza, se zaporedje obravnava kot geometrijsko zaporedje.
2. korak
Zdaj morate najti skupno razmerje za dano zaporedje.
3. korak
Formulirajte rekurzivno formulo z uporabo prvega izraza in nato ustvarite formulo z uporabo prejšnjega člena in običajnega razmerja; tako boste dobili dani rezultat
an= r*an-1
Zdaj razumemo dano formulo s pomočjo primera
java celo število v niz
predpostavimo, da je 2,8,32, 128,.dano zaporedje
V zgornjem primeru zlahka ugotovite, da gre za geometrijsko zaporedje, ker se naslednji člen v zaporedju dobi z množenjem 4 na prejšnji člen. Torej je skupno razmerje med dvema členoma 4. Poznamo formulo rekurzivnega zaporedja
an= r*an-1
an= 4
an-1= ?
podano,
r = 4
a1= 2
torej,
a2= a(2-1)* 4 = a1+ * 4 = 2 * 4 = 8
a3= a(3-1)* 4 = a2* 4 = 8 * 4 = 32
a4= a(4-1)* 4 = a3* 4 = 32 * 4 = 128 in postopek se nadaljuje.
Primer rekurzivne funkcije
Primer 1:
Določite rekurzivno formulo za zaporedje 4,8,16,32,64, 128,….?
rešitev:
Dano zaporedje 4,8,16,32,64,128,…..
Dano zaporedje je geometrijsko, ker če pomnožimo predhodni člen, dobimo zaporedne člene.
Za določitev rekurzivne formule za dano zaporedje jo moramo zapisati v obliki tabele
| Številke izrazov | Zaporedni izraz | Zapis funkcije | Subscript notation |
|---|---|---|---|
| 1 | 4 | f(1) | a1 |
| 2 | 8 | f(2) | a2 |
| 3 | 16 | f(3) | a3 |
| 4 | 32 | f(4) | a4 |
| 5 | 64 | f(5) | a5 |
| 6 | 128 | f(6) | a6 |
| n | . | f(n) | an |
Zato je rekurzivna formula v pojmu funkcije podana z
f(1) = 4, f(n) . f(n- 1)
V indeksnem zapisu je rekurzivna formula podana z
a1= 4, an= 2. an-1