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

Če₁, a₂, a₃, a₄, a₅, a₆, ……..a_n,……je veliko nizov ali zaporedje, potem bo morala rekurzivna formula izračunati vse člene, ki so obstajali prej, da izračuna vrednost

a_n= a_{n-1 +}a₁

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

a_n= a_{n-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

a_n= a_{n-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

a_n= a_{n-1 +}d

podano,

d = 2

a₁= 3

torej,

a₂= a_(2-1)+ 2 = a₁+2 = 3+2 = 5

a₃= a_(3-1)+ 2 = a₂+2 = 5+2 = 7

a₄= a_(4-1)+ 2 = a₃+2 = 7+2 = 9

a₅= 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

a_n= r_*a_n-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

a_n= r_*a_n-1

a_n= 4

a_n-1= ?

podano,

r = 4

a₁= 2

torej,

a₂= a_(2-1)* 4 = a₁+ * 4 = 2 * 4 = 8

a₃= a_(3-1)* 4 = a₂* 4 = 8 * 4 = 32

a₄= a_(4-1)* 4 = a₃* 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

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

a₁= 4, a_n= 2. a_n-1