370
www.namspi.uz
universaljurnal.uz
C++ muhitida Rekursiv funksiyalar haqida ma`lumotlar va dasturlarni
ko`rib chiqish
Alijonova Kamola
Namangan davlat universiteti “Kompyuter ilmlari va dasturlash
texnologiyalari” 2-kurs talabasi
E-mail:kamolaalijonova1004@gmail.com
Tel:+998934964974
Ubaydullayeva Diloromxon Maxmudjon Qizi
Namangan Davlat Universiteti “Raqamli ta`lim texnologiyalari” kafedrasi
o`qituvchisi
diloromubaydullayeva2010@gmail.com
+998940677715
Annotatsiya:
Bu maqola, funksiyalar va rekursiv funksiyalar
mavzusidagi algoritmlar-ni yaratishning asosiy usullarini o'rgatadi. Ushbu
maqola, dasturlash sohasidagi muhim kontseptlarni tushunish uchun funksiya va
rekursiv funksiyalar- ni qanday samarali qo'llab-quvvatlashni va ulardan
foydalanishni ko'rsatadi.
Kalit so'zlar:
Funksiyalar, Rekursiya, Dasturlash, Tushuncha,
Samarali, Qo'llab-quvvatlash, O'zlashtirish, Tasavvur, O'rganish.
Annotation:
This article teaches the basic techniques for creating
algorithms on the topic of functions and recursive functions. This article shows
how to effectively support and use functions and recursive functions to understand
important programming concepts.
Keywords:
Functions, Recursion, Programming, Concept, Efficient,
Support, Mastery, Imagination, Learning.
Аннотация
:
В
этой
статье
рассказывается
об
основных
методах
создания
алгоритмов
на
тему
функций
и
рекурсивных
функций
.
В
этой
статье
показано
,
как
эффективно
поддерживать
и
использовать
функции
и
рекурсивные
функции
для
понимания
важных
концепций
программирования
.
Ключевые
слова
:
Функции
,
рекурсия
,
программирование
,
концепция
,
эффективность
,
поддержка
,
мастерство
,
воображение
,
обучение
.
KIRISH
Dasturlash sohasida funksiya va rekursiv funksiyalar qo'llash
algoritmlarini o'rganish, dasturchilarning tajribalarini rivojlantirish, kodni
tizimlash va optimallashtirish jarayonlarini tushuntirishga qaratilgan integrativ
maqoladir. Funksiyalar: Funksiyalar, kodni qo'shimcha tuzilganlik va o'zlashtirish
uchun asosiy vositalardir. Maqolada, funksiya yaratish, uni chaqirish,
argumentlarni qabul qilish, va qiymatlarni qaytarish jarayonlari ko'rsatiladi.
Misollar orqali funksiyalar yordamida kodni modulyar qilishning muhimligi
o'rgatiladi. Rekursiv Funksiyalar: Rekursiv funksiyalar, o'z o'zini chaqirish orqali
yechim topishda ishlatiladi. Maqolada, rekursiv funksiyalar yaratish, ularni aniq
371
www.namspi.uz
universaljurnal.uz
va samarali shakllantirish, va ulardan to'g'ri foydalanishning ilmiy jihatlari
o'rgatiladi. Rekursivlik, maslahatlarni darhol hal qilishda va dasturlashda yechim
topishda qanday yordam bera olishni ko'rsatadi.
C ++ dasturlash tilida funksiyalar o`z – o`zini chaqirish imkoniyatiga
ega. Bunday funksiyalar rekursiyali (o`z – o`zini chaqiruvchi) funksiya deyiladi.
Rekursiyali funksiyalarga qoyiladigan asosiy talab, qandaydir qiymatda rekursiya
0- yolg`on yoki 1-rost qiymat qabul qilishi kerak. Shundagina chaqirilgan
funksiyalar qaytadi. Aks holda funksiya o`z – o`zini davomli ravishda chaqiradi
va xatolik sodir bo’ladi.
Funksiya o’z – o’zini chaqirishi rekursiya deyiladi. U ikki xil – to’g’ri
rekursiya va bilvosita rekursiya bo’lishi mumkin. Agarda funksiya o’zini o’zi
chaqirsa bu to’g’ri rekursiya deyiladi. Agarda funksiya boshqa bir funktsiyani
chaqirsa va u funksiya o’z navbatida birinchisini chaqirishi esa bilvosita rekursiya
deyiladi.
Agar funksiya o‘zidan yordamchi funksiya sifatida foydalanadigan
bo‘lsa, bunday funksiyalar rekursiv deyiladi.
Rekursiv funksiyalar ikki turga bo‘linadi:
a) to‘g‘ri rekursiya. Bunda dastur o‘ziga-o‘zi murojaat qiladi.
b) yondosh rekursiya. Bunda A funksiya B ga, B funksiya A ga
murojaat qiladi.
Rekursiv funksiya yozish uchun avvalo: 1) rekkurent munosabat;
2) shu munosabat uchun boshlang‘ich holatlar aniqlangan bo‘lishi shart.
Rekkurent munosabat deganda qaralayotgan jarayonga doir muayyan
bosqichlami avvalgi bosqichlar bilan bog‘lovchi munosabatlar tushuniladi.
Masalan, N! =N-(N—1)! formulani N! uchun rekkurenti munosabat deb qarash
mumkin. Boshlang‘ich holat sifatida esa 1!=1 olinadi.
Keltirilgan m a’lumotlami hisobga olsak, faktorialni hisoblash
masalasi uchun rekkurent va boshlang‘ich munosabatlar quyidagicha bo`ladi:
Ko‘rinib turibdiki, N! ni hisoblash uchun (N-1)! ma’lum bo‘lishi kerak.
Lekin,
(N-1)!=(N-2)!*(N-1) bo‘lgani uchun o‘z navbatida (N-2)! ni topish talab
qilinadi. (N-2)! esa (N-3)!*(N-2) ga teng va hokazo. Bu yerda N! ni hisoblash
algoritmi o‘zining ichiga o ‘zi “cho‘kib” borishi hodisasi ro‘y bermoqda. Cho‘kish
jarayoni boshlang‘ich holat sodir bo‘lgunga qadar, ya’ni 1! gacha davom etadi.
Shundan keyin, “cho‘kish” jarayoni to‘xtaydi, 1!=1 ekanligi haqida ko‘rsatma
olgan kompyuter yuqoriga qarab “suzib” chiqish bosqichini boshlaydi. Ya’ni,
2!=1,
2!=1*2=2, 3!=2!*3=6 va hokazo. Bu holat to N! hisoblanmaguncha davom
etaveradi.
Funksiya o'ziga o'zi to'g'ridan-to'g'ri yoki qandaydir vosita orqali
murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv
funksiya deb ataladi.
Rekursiyani to'g'ri tashkil qilish shartlari:
Har qanday to'g'ri tuzilgan rekursiya asosini ikkita shart tashkil qiladi.
372
www.namspi.uz
universaljurnal.uz
Rekursiya asos sharti:
Funksiyaning o'ziga o'zgartirilgan argument bilan murojaat qilish.
Rekursiya
— Funksiya o
ʻ
ziga o
ʻ
zi to
ʻ
g
ʻ
ridan-to
ʻ
g
ʻ
ri yoki qandaydir vosita
orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv
funksiya deb ataladi. Rekursiv funksiya o
ʻ
zini — o
ʻ
zi chaqirgani uchun
dasturchilar orasida quyi oldin rekursiya nimagligini tushunish kerak“ — Stephen
Hawking.
Rekursiya
funksional
dasturlashning
asosiy
elementlaridan
hisoblanadi.
Rekursiya
deyarli
hamma
joyda
ishlatiladi.
Ba
ʼ
zi
masalalarning
iterativ yechimi
juda ham uzun bo
ʻ
lib ketishi mumkin. Rekursiya
esa
kodni
bir
necha
barobar
qisqartirib
berishi
mumkin.
Aksariyat
tuzilmalar
va
algoritmlarni
rekursiyasiz
tasavvur
qilib
bo
ʻ
lmaydi.
Tree
,
Graph
,
Heap
,
Quick Sort
,
Merge Sort
, … Bu
ro'yhatni
juda uzoq
davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo
ʻ
lgan Tree va
Graphlarda rekursiya har qadamda uchraydi.[1. B 243]
Rekursiv funksiya qaysidir vaqtga kelib o'ziga murojaat qilishni
to'xtatishi kerak bo'ladi. Aynan shu narsani rekursiya asos sharti ta'minlab beradi.
Hikoyamizdagi misolga qaytadigan bo'lsak, Abdullajon summa() funksiyasiga bir
necha marta murojaat qildi va oxirida funksiyaga keluvchi massivda faqat bitta
element qolganda to'xtadi. Bu masala uchun arrayda yagona element qolishi asos
shart bo'lib xizmat qiladi va shu yerga yetganda dastur to'xtashi kerakligini bilib
oladi. Rekursiv funksiya tuzishda asos shartni to'g'ri qo'yish juda ham muhim
hisoblanadi. Hali bunga yana to'xtalamiz.
Keyingi shartda o'zgartirilgan argument deganda, odatda masala
boshidagi argumentdan kichikroq argument tushiniladi (ba'zi hollarda kattaroq
bo'lishi mumkin). Misolimizda, Abdullajon har safar summa() funksiyasiga
murojaat qilganda undagi massiv hajmini bittaga kamaytirib bordi. Bu narsa ham
juda muhim, chunki bir xil argument bilan qayta-qayta murojaat qilinganda yoki
argument notog'ri o'zgartirilganda funksiya o'zini cheksiz marta chaqirishiga
to'g'ri kelib qoladi. Bu haqida ham batafsil yana gaplashamiz.
Nima uchun rekursiya kerak:
Aslini olganda, har qanday rekursiv ishlangan masalani iterativ usulda
ishlash mumkin va buning aksi ham to'g'ri.Buning ustiga rekursiv yechim har
doim xotiradan qo'shimcha joy talab qiladi.
Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning yetarlicha
sabablari bor:
Rekursiya deyarli hamma joyda ishlatiladi. Ya'ni, lo'nda qilib aytganda
undan qochib qutilishning iloji yo'q. Harakat qilib ko'rish esa qimmatga tushishi
aniq )
Ba'zi holatlarda rekursiv yechim ancha soddaroq. Ayniqsa, ba'zi
masalalarning iterativ yechimi juda ham uzun bo'lib ketishi mumkin. Rekursiya
esa kodni bir necha barobar qisqartirib berishi mumkin.
Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo'lmaydi.
Tree, Graph, Heap, QuickSort, MergeSort, … Bu ro'yhatni juda uzoq davom
ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo'lgan Tree va Graphlarda
373
www.namspi.uz
universaljurnal.uz
rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib
bo'lmaydi, bu esa o'z o'rnida rekursiya qanchalik muhimligini belgilab beradi.
Rekursiya
funksional
dasturlashning
asosiy
elementlaridan
hisoblanadi. Hali funksional dasturlash haqida eshitmagan bo'lsangiz u haqida
ma'lumot axtarib o'qib ko'rishni maslahat beraman. Bir so'z bilan aytganda,
hozirda dasturlash sohasi jadallik bilan funksional dasturlash paradigmasi tomon
ketmoqda (Go va Scala yorqin namunalar).
Yana bir qiziq ma'lumot, shunday dasturlash tillari borki ularda umuman
takrorlanish operatorlari yo'q va bu borada butunlay rekursiyaga tayanadi. Haskell
va Erlang shular jumlasidan.
NATIJALAR
Albatta, bularning barchasi rekursiyani takrorlash operatorlaridan butunlay
ustunligini anglatmaydi. Aslida, ko'p hollarda dasturchilar rekursiya ishlatishdan
Masala.
f(n) funksiyaning qiymatlari f(0 )=1 , f(2n)= f{n) va
f (2n+1)=f (n)+1 ifodalar yordamida topiladi. Berilgan k natural soni uchun
f(k) ni
masala shartida keltirilganligi ishni yanada osonlashtiradi.
Misol 1:Faktorialni hisoblang:
Misol 2:Fibonachi qatorini hisoblang:
374
www.namspi.uz
universaljurnal.uz
Misol 3: Massiv elementlarining yig'indisini hisoblash:
Foydalanilgan adabiyotlar ro`yhati:
1.
https://uz.wikipedia.org/wiki/Rekursiya
2.
https://arxiv.uz/uz/documents/referatlar/informatika-va-at/rekursiv-
funksiyalar-1
3.
https://oefen.uz/uz/documents/diplom-ishlar/umumiy/c-dasturlash-tilida-ko-
rsatkichlar-funksiyalar-va-rekursiv-funksiyalar-asosida-murakkab-
jarayonlarni-dasturlash
4.
https://www.texnoman.uz/post/rekursiya--hayotdan-misol-va-undan-unumli-
foydalanish.html
5.
https://azkurs.org/reja-rekursiv-funksiya-haqida-malumot.html
