Сайфиев ж. Ф. С++ тилига кириш услубий қўлланма

Функциялар ҳақида қўшимча маълумот. Рекурсия.

Функция ўз – ўзини чақириши рекурсия дейилади. У икки хил – тўғри рекурсия ва билвосита рекурсия бўлиши мумкин. Агарда функция ўзини ўзи чақирса бу тўғри рекурсия дейилади. Агарда функция бошқа бир функцияни чақирса ва у функция ўз навбатида биринчисини чақириши эса билвосита рекурсия дейилади.
Айрим муаммолар рекурсия ёрдамида осонроқ ечилади. Агарда маълумотлар устида бирор процедура ишлатилса ва унинг натижаси устида ҳам худди шу процедура бажарилса, бундай ҳолларда рекурсияни ишлатиш лозим. Рекурсия икки хил натижа билан якунланади: у ёки охир – оқибат албатта тугайди ва бирор натижа қайтаради, иккинчиси ҳеч қачон тугалланмайди ва хатолик қайтаради.
Агарда функция ўзини ўзи чақирса, бу функцияни нусхаси чақирилишини айтиб ўтиш лозим. Рекурсия ёрдамида ечиладиган муаммо сифатида Фибоначчи қаторини кўрсатиш мумкин.
1, 1, 2, 3, 5, 8, 13, 21, 34 …
Бу қаторнинг ҳар бир сони (иккинчисидан кейин) ўзидан олдинги икки соннинг йиғиндисига тенг. Масала қуйидагидан иборат: Фибоначчи қаторини 12 – аъзоси нечага тенглигини аниқланг. Бу муаммонинг ечишнинг усулларидан бири қаторни батафсил таҳлил қилишдан иборатдир. Қаторнинг олдинги икки сони бирга тенг. Ҳар бир навбатдаги сон олдинги иккита соннинг йиғиндисига тенг. Яъни, ўн еттинчи сон ўн олтинчи ва ўн бешинчи сонлар йиғиндисига тенг. Умумий ҳолда n – соннинг йиғиндиси (n-2)- ва (n-1) – сонларнинг йиғиндисига тенг (n>2 ҳол учун).
Рекурсив функциялар учун рекурсияни тўхтатиш шартини бериш зарур. Фибоначчи қатори учун тўхтатиш шарти n<3 шартидир.
Бунда қуйидаги алгоритм қўлланилади:

1. 
   Фойдаланувчидан Фибоначчи қаторининг қайси аъзосини ҳисоблашини кўрсатишини сўраймиз.
   
2. 
   fib() функциясини чақирамиз ва унга фойдаланувчи томонидан берилган Фибоначчи қатори аъзоси тартиб номерини аргумент сифатида узатамиз.
   
3. 
   fib() функцияси (n) аргументни таҳлил қилади. Агарда n<3 бўлса, функция 1 қиймат қайтаради; акс ҳолда fib() функцияси ўзини ўзи чақиради ва унга аргумент сифатида n–2 қийматни беради, кейин яна ўз–ўзини чақиради ва бу функцияга n–1 ни қиймат сифатида беради. Бундан кейин эса уларнинг йиғиндисини қиймат сифатида узатади.
   

Агарда fib(1) функцияси чақирилса у 1 қийматни қайтаради. Агарда fib(2) функцияси чақирилса у ҳам 1 қийматни қайтаради. Агарда fib(3) функцияси чақирилса у fib(1) ва fib(2) функцияларини йиғиндисини қайтаради. fib(2) ва fib(1) функциялари 1 қийматни қайтарганлиги сабабли fib(3) функцияси қиймати 2 га тенг бўлади.
Агарда fib(4) функцияси чақирилса, бунда у fib(3) ва fib(2) функциялари йиғиндисини қиймат сифатида қайтаради. fib(3) функцияси 2 ва fib(2) функцияси 1 қиймат қайтаришидан fib(4) функцияси 3 ни қиймат сифатида қайтариши келиб чиқади. Демак, Фибоначчи қаторининг тўртинчи аъзоси 3 га тенг экан.
Юқорида, тавсифланган усул бу масалани ечишда унчалик самарали усул эмас. fib(20) функцияси чақирилса, у томонидан fib() функцияси 13529 марта чақирилади. Бундай ҳолларда эҳтиёт бўлиш лозим. Агарда Фибоначчи қаторининг жуда катта номерини берсак хотира етишмаслиги мумкин. Fib() функциясини ҳар сафар чақирилишида хотирадан маълум бир соҳа заҳираланади. Функциядан қайтиш билан хотира бўшатилади. Лекин, рекурсив тарзда функция чақирилса хотирадан унинг учун янги жой ажратилади ва токи ички функция ўз ишини тугатмагунча уни чақирган функция эгаллаган жой бўшатилмайди. Шунинг учун хотирани етишмай қолиш хавфи бор. Fib() функциясининг ишлатилиши 5.10. – листингда кўрсатилган.