Рекурзивна функција је функција чија се вредност у било којој тачки може израчунати из вредности функције у неким претходним тачкама. На пример, претпоставимо функцију ф(к) = ф(к-2) + ф(к-3) која је дефинисана над целим бројем који није негативан. Ако имамо вредност функције на к = 0 и к = 2, њену вредност можемо пронаћи и на било ком другом ненегативном целом броју. Другим речима, можемо рећи да се рекурзивна функција односи на функцију која користи сопствене претходне тачке за одређивање наредних термина и тако формира низ термина. У овом чланку ћемо научити о рекурзивним функцијама заједно са одређеним примерима.

Шта је рекурзија?

Рекурзија се односи на процес у коме се рекурзивни процес понавља. Рекурзивна је врста функције једне или више променљивих, обично специфицираних одређеним процесом који производи вредности те функције континуираним спровођењем одређене релације са познатим вредностима функције.

Овде ћемо разумети рекурзију уз помоћ примера.

Претпоставимо да ћете ићи степеницама да бисте стигли до првог спрата из приземља. Дакле, да бисте то урадили, морате предузети кораке један по један. Постоји само начин да се пређе на други корак, а то је до стрмог првог корака. Претпоставимо да желите да пређете на трећи корак; прво морате да направите други корак. Овде можете јасно видети процес понављања. Овде можете видети да са сваким следећим кораком додајете претходни корак као поновљени низ са истом разликом између сваког корака. Ово је стварни концепт иза рекурзивне функције.

Корак 2: Корак 1 + најнижи корак.

Корак 3: Корак 2 + Корак 1 + најнижи корак.

4. корак: Корак 3 + корак 2 + корак 1+ најнижи корак и тако даље.

Скуп природних бројева је основни пример рекурзивних функција које почињу од један до бесконачности, 1,2,3,4,5,6,7,8, 9,…….инфинитив. Стога, скуп природних бројева показује рекурзивну функцију јер можете видети заједничку разлику између сваког члана као 1; показује сваки пут када се следећи термин понавља претходним термином.

Шта је рекурзивно дефинисана функција?

Рекурзивно дефинисане функције се састоје од два дела. Први део се бави дефиницијом најмањег аргумената, а са друге стране, други део се бави дефиницијом н-тог појма. Најмањи аргумент се означава са ф (0) или ф (1), док се н-ти аргумент означава са ф (н).

Следите дати пример.

Претпоставимо да је низ 4,6,8,10

Експлицитна формула за горњи низ је ф (н)= 2н + 2

Експлицитна формула за горњи низ је дата са

ф (0) = 2

ф(н) = ф (н-1) + 2

Сада можемо добити термине низа применом рекурзивне формуле на следећи начин ф(2) ф (1) + 2

ф(2) = 6

ф (0) = 2

ф(1) = ф(0) + 2

ф (1) = 2 + 2 = 4

ф(2 ) = ф (1) + 2

ф(2) = 4 + 2 = 6

ф(3 ) = ф (2) + 2

ф(3) = 6 + 2 = 8

Уз помоћ горње формуле рекурзивне функције можемо одредити следећи појам.

Шта чини функцију рекурзивном?

Да би било која функција била рекурзивна, потребан је сопствени термин за израчунавање следећег члана у низу. На пример, ако желите да израчунате н-ти члан датог низа, прво морате да знате претходни члан и члан пре претходног члана. Дакле, морате знати претходни термин да бисте утврдили да ли је низ рекурзиван или не. Дакле, можемо закључити да ако је функцији потребан претходни термин да одреди следећи термин у низу, функција се сматра рекурзивном функцијом.

Формула рекурзивне функције

Ако₁, а₂, а₃, а₄, а₅, а₆, ……..а_н,…… је много скупова или низа, онда ће рекурзивна формула морати да израчуна све чланове који су постојали раније да би израчунала вредност

а_н= а_{н-1 +}а₁

Горња формула се такође може дефинисати као рекурзивна формула аритметичке секвенце. Можете јасно видети у горе поменутом низу да је то аритметички низ, који се састоји од првог члана праћеног осталим терминима и заједничке разлике између сваког члана. Уобичајена разлика се односи на број који им додајете или одузимате.

Рекурзивна функција се такође може дефинисати као геометријски низ, где скупови бројева или низ имају заједнички фактор или заједнички однос између њих. Формула за геометријски низ је дата као

а_н= а_{н-1 *}р

Обично се рекурзивна функција дефинише у два дела. Први је исказ првог члана заједно са формулом, а други је исказ првог члана заједно са правилом везаним за узастопне чланове.

Како написати рекурзивну формулу за аритметички низ

Да бисте написали рекурзивну формулу за формулу аритметичког низа, следите дате кораке

Корак 1:

У првом кораку морате да проверите да ли је дати низ аритметички или не (за ово морате да додате или одузмете два узастопна члана). Ако добијете исти излаз, онда се низ узима као аритметички низ.

Корак 2:

Сада морате пронаћи заједничку разлику за дати низ.

Корак 3:

Формулишите рекурзивну формулу користећи први термин, а затим креирајте формулу користећи претходни термин и уобичајену разлику; тако ћете добити дати резултат

а_н= а_{н-1 +}д

сада, разумемо дату формулу уз помоћ примера

стринг у цео број

претпоставимо да је 3,5,7,9,11 дати низ

У горњем примеру, лако можете пронаћи да је то аритметички низ јер се сваки члан у низу повећава за 2. Дакле, заједничка разлика између два члана је 2. Знамо формулу рекурзивног низа

а_н= а_{н-1 +}д

Дато,

д = 2

а₁= 3

тако,

а₂= а_(2-1)+ 2 = а₁+2 = 3+2 = 5

а₃= а_(3-1)+ 2 = а₂+2 = 5+2 = 7

а₄= а_(4-1)+ 2 = а₃+2 = 7+2 = 9

а₅= а_(5-1)+ 2 = а + 2 = 9+2 = 11, а процес се наставља.

Како написати рекурзивну формулу за геометријски низ?

Да бисте написали рекурзивну формулу за формулу геометријског низа, следите дате кораке:

Корак 1

У првом кораку, морате да се уверите да ли је дати низ геометријски или не (за ово морате сваки појам помножити или поделити бројем). Ако добијете исти излаз од једног до другог појма, низ се узима као геометријски низ.

Корак 2

Сада морате пронаћи заједнички однос за дати низ.

Корак 3

Формулишите рекурзивну формулу користећи први термин, а затим креирајте формулу користећи претходни термин и уобичајени однос; тако ћете добити дати резултат

а_н= р_*а_н-1

Сада разумемо дату формулу уз помоћ примера

претпоставимо да је 2,8,32, 128,.дати низ

У горњем примеру, лако можете пронаћи да је то геометријски низ јер се узастопни члан у низу добија множењем 4 на претходни члан. Дакле, заједнички однос између два члана је 4. Знамо формулу рекурзивног низа

нпм очисти кеш

а_н= р_*а_н-1

а_н= 4

а_н-1= ?

Дато,

р = 4

а₁= 2

тако,

а₂= а_(2-1)* 4 = а₁+ * 4 = 2 * 4 = 8

а₃= а_(3-1)* 4 = а₂* 4 = 8 * 4 = 32

а₄= а_(4-1)* 4 = а₃* 4 = 32* 4 = 128, а процес се наставља.

Пример рекурзивне функције

Пример 1:

Одредити рекурзивну формулу за низ 4,8,16,32,64, 128,….?

Решење:

Дати низ 4,8,16,32,64,128,…..

Дати низ је геометријски јер ако помножимо претходни члан, добијамо узастопне чланове.

Да бисмо одредили рекурзивну формулу за дати низ, потребно је да је запишемо у табеларном облику

Дакле, рекурзивна формула у појму функције је дата са

ф(1) = 4, ф(н) . ф(н- 1)

У индексној нотацији, рекурзивна формула је дата са

а₁= 4, а_н= 2. а_н-1