264
www.namspi.uz
universaljurnal.uz
REKURSIV ALGORITMLAR YORDAMIDA MASALALAR
YECHISH USLUBIYOTI
1
Otabayeva Feruza Toxirovna,
2
Mansurova Maxliyoxon Abdumalikovna
1,2
Namangan davlat universiteti,
1
Teacher,
2
Magistr
E-mail:
azuref78@list.ru
Annotatsiya:
Ushbu maqolada rekursiya, rekursiv algoritmlar tahlil
qilib chiqilgan. Rekursiv algoritmlar yordamida masalalar yechishda qo‘llash
uchun usullar tavsiya etilgan. Rekursiv algoritmlar yordamida fibonachi va
factorial masalalarini yechish dasturlari 2 xil dasturlash tillarida keltirilgan.
Kalit so‘zlar:
rekursiya, algoritm, rekursiv algoritmlar, bo‘laklarga
ajratish usuli, memorization, qayta tekshirish.
Аннотация
:
В
данной
статье
изучаются
и
анализируются
рекурсия
и
рекурсивные
алгоритмы
.
Рекомендуются
методы
решения
задач
с
использованием
рекурсивных
алгоритмов
.
Программы
для
решения
задач
Фибоначчи
и
факториала
с
использованием
рекурсивных
алгоритмов
представлены
на
двух
разных
языках
программирования
.
Ключевые
слова
:
рекурсия
,
алгоритм
,
рекурсивные
алгоритмы
,
метод
разделения
на
части
,
запоминание
,
перепроверка
.
Annotation:
In this article, recursion and recursive algorithms are
analyzed and analyzed. Rekomenduyutsya metody reshenia zadach s
ispolzovaniem rekursivnyx algoritmov. Programs for solving Fibonacci and
factorial problems with the use of recursive algorithms are presented in two
different programming languages.
Key words
: recursion, algorithm, recursive algorithms, method of division
into parts, memorization, rechecking.
KIRISH
Algoritmlar hayotimizda har bir sohada muhim o‘rin egallaydi.
Algoritmlar nafaqat texnik jarayonlarni avtomatlashtirish, balki hayotimizni
yanada qulay va samarali qilishda ham muhim rol o‘ynaydi. Ular har bir sohada
muammolarni hal qilish va qarorlar qabul qilishda yordam beradi. Rekursiv
algoritmlar esa ko‘plab muammolarni hal qilishda samarali va tushunarli
yechimlar taqdim etadi.
Rekursiya bu bir funksiyaning o‘zini chaqirish orqali muammoni hal qilish
usuli. Rekursiya dasturlashda va matematikada keng qo‘llaniladi. Uning asosiy
tamoyili, muammoni kichikroq va oddiyroq qismga bo‘lish va shu qismni hal
qilishdir.
Rekursiyani o‘rganishdan maqsad o‘zini-o‘zi chaqiruvchi funksiyalarni
ishlatish orqali dasturlashda muhim tushunchalarni o‘zlashtirish, murakkab
masalalarni oddiy va qulay yechimlarga ajratish, ko‘p darajali muammolarni
intuitiv tarzda tushunish osonlashadir. Rekursiv algoritmlar ko‘plab kompyuter
265
www.namspi.uz
universaljurnal.uz
fanlari va matematikada qo‘llaniladi. Rekursiya yordamida algoritmlarni yaratish
va ularning samaradorligini tahlil qilish ko‘nikmalarini rivojlantirish mumkin.
Shuningdek, rekursiyani o‘rganish dasturlashda muvaffaqiyatli bo‘lish
uchun zarur ko‘nikma bo‘lib, dasturchilarning fikrlash uslubini kengaytiradi.
Rekursiyaning afzalliklari:
- Muammolarni oddiy va tushunarli tarzda hal qilish imkonini beradi.
- Kichik qismlarga bo‘lib, kodni qisqartirishga yordam beradi.
Kamchiliklari:
- Stack overflow (ko‘p darajada chaqirish) xavfi.
- Ba‘zi hollarda iterativ usuldan ko‘ra sekinroq bo‘lishi mumkin.
ADABIYOTLAR TAHLILI VA METODLAR
Rekursiyaning asosiy nazariyalaridan birini Alonzo Church yaratgan.
Kompyuter fanlari va matematika sohasida, rekursiyaning dasturlashdagi
qo‘llanilishi bilan ishlagan olim John von Neumann. Dasturlash algoritmlarini
o‘rganish bo‘yicha yetakchi olim Donald Knuth. U "The Art of Computer
Programming" asarida rekursiya va uning ishlashini keng qamrovli bayon qilgan.
Algoritmlar va dasturlash paradigmalari bo‘yicha muhim ishlar qilgan olim
Edward Dijkstra. U rekursiyani va uning samaradorligini o‘rgatgan. Bu olimlar
rekursiyaning nazariyasi va amaliyotida muhim hissalar qo‘shgan.
Donald Knuth rekursiya va algoritmlar bo‘yicha juda muhim ishlar qilgan
olim. Uning "The Art of Computer Programming" asari, ayniqsa, rekursiyani
chuqur o‘rganish uchun muhim manba hisoblanadi. Ushbu asarda Knuth
rekursiyalarning asosiy tamoyillari, ularni qanday yozish, optimallashtirish va
amaliy dasturlarda qo‘llash usullarini keltirib o‘tadi.
Knuth, shuningdek, rekursiv algoritmlarning samaradorligini tahlil
qilishga e'tibor qaratadi va rekursiyaning vaqt va xotira xarajatlarini baholash
usullarini muhokama qiladi. U dasturlashda rekursiyaning afzalliklari va
kamchiliklarini ko‘rsatib beradi, bu esa dasturchilar uchun rekursiv
yondashuvlar tanlashda yordam beradi.
NATIJALAR
Rekursiyaning ikki asosiy elementi bor:
1. Asosiy holat (base case): Bu rekursiyadan chiqish sharti. Bu holatga
yetganda funksiyaning o‘zini chaqirishni to‘xtatish kerak. Misol uchun, factorial
hisoblashda 0! = 1 asosiy holatdir.
2. Rekursiv holat (recursive case): Bu holatda funksiya o‘zini yana
chaqiradi, lekin har safar muammoni kichikroq qismga bo‘lish orqali. Masalan, n!
ni hisoblashda n! = n * (n-1)! formulasi ishlatiladi.
Odatda rekursiya matematikada keng qo‘llaniladi. Chunki aksariyat
matematik formulalar rekursiv aniqlanadi.
Rekursiv algoritmlar ko‘plab muammolarni hal qilishda samarali va
tushunarli yechimlar taqdim etadi. Ularni o‘rganish, amaliyotda qo‘llash va turli
xil masalalarni yechish orqali rekursiya tushunchasini mustahkamlashingiz
mumkin.
266
www.namspi.uz
universaljurnal.uz
Rekursiyaga oid masalalarni yechish uchun quyidagi usullarni qo‘llash
mumkin:
1. Masalani qismlarga bo‘lib yechish:
- Masalani kichikroq va oddiyroq bo‘laklarga ajratish. Har bir bo‘lakni
alohida yechib, natijalarni birlashtirish.
2. Asosiy holatni belgilash:
- Rekursiya to‘xtash nuqtasini aniqlash. Bu, odatda, muammo eng kichik
qismga yetganda bo‘ladi. Masalan, n = 0 yoki n = 1 kabi shartlar.
3. Rekursiv formulani yozish:
- Muammoning yechimi qanday qilib o‘zini chaqirishini aniqlash. Har
bir qadamda qanday amal bajarilishi kerakligini ko‘rsatish.
4. Mavjud natijalarni saqlash (Memoization)
- Agar bir xil hisoblash bir necha marta amalga oshirilsa, natijalarni
saqlash orqali hisoblash vaqtini qisqartirish. Bu usul ko‘pincha dinamik dasturlash
bilan birga qo‘llaniladi.
5. Iterativ yechimni ko‘rib chiqish
- Ba’zi hollarda rekursiv yechimni iterativ yechimga o‘zgartirish ham
mumkin. Bu xotira sarfini kamaytiradi va tezlikni oshiradi.
6. Qayta tekshirish
- Rekursiv funksiyani sinab ko‘rish va har bir qadamda natijani
tekshirish. Muammoning to‘g‘ri yechilganini tasdiqlash uchun bu muhimdir.
7. Dasturlash tillari bilan tanishish
- Har bir dasturlash tilida rekursiya ishlash usuli farq qilishi mumkin.
O‘z tilingizda rekursiya qo‘llanmasini o‘rganing va uning sintaksisini yaxshi bilib
oling.
MUHOKAMA
Ilmiy tadqiqot ishimiz davomida rekursiyaga oid masalalarni yechishda
qo‘llaniladigan usullar ko‘rib chiqildi. Va shu asosda matematik masalalarni
yechishda rekursiv algoritmlardan foydalanib C++ va Python dasturlash tillarida
dasturlar ishlab chiqildi.
1-misol:
=
(0 <
< 1,
∈
)
funktsiya qiymatini eng kam
amallardan foydalanib hisoblang.
Python va C++ dasturlash tillarida rekursiya masalalari yechimi dasturini
keltiramiz.
def recursive_power(a, n):
if n == 0:
return 1 # Asosiy holat uchun: a^0 = 1
else:
return a * recursive_power(a, n - 1) #
Рекурсивный
шаг
# Rekursiya funktsiya shartlarini tekshirish va chaqirish uchun asosiy
funktsiya
def calculate_power(a, n):
if 0 < a < 1 and isinstance(n, int) and n > 0:
return recursive_power(a, n)
267
www.namspi.uz
universaljurnal.uz
else:
return "
Условия
0 < a < 1
и
n -
натуральное
число
не
выполнены
"
# Qo‘llashga doir misollar
a = 0.5
n = 3
result = calculate_power(a, n)
print("y =", result)
Izoh:
1.
Asosiy holat: agar n=0
n
= 0
n
=0 bo‘lsa, funksiya 1 ni qaytaradi, chunki a
0
=1
a^0 = 1 a
0
=1.
2. Rekursiv qadam: n>0
n
> 0
n
>0 uchun funktsiya a ni o'zini n
−
1
n
- 1
n
−
1
parametri bilan chaqirish natijasiga ko'paytiradi.
3. calculate_power funksiyasida 0<a<10 < a < 10<a<1 va n natural son
shartlar tekshiriladi. Agar shartlar bajarilsa, recursive_power rekursiv funksiyasi
chaqiriladi.
Misol:
a = 0.5 va n = 3 da natija y = 0.125 bo‘ladi.
#include <iostream>
using namespace std;
// Rekursiv funksiya: a^n ni hisoblaydi
double power(double a, int n) {
// Asosiy holat: n = 0 bo'lsa, a^0 = 1
if (n == 0)
return 1;
// Asosiy holat: n = 1 bo'lsa, a^1 = a
if (n == 1)
return a;
// Optimal bo'lishi uchun n/2 ga bo'lib hisoblaymiz
double halfPower = power(a, n / 2);
// Agar n juft bo'lsa, natija halfPower^2
if (n % 2 == 0)
return halfPower * halfPower;
// Agar n toq bo'lsa, natija halfPower^2 * a
else
return halfPower * halfPower * a;
}
int main() {
double a;
int n;
cout << "a (0 < a < 1) ni kiriting: ";
cin >> a;
if (a <= 0 || a >= 1) {
cout << "a 0 dan katta va 1 dan kichik bo'lishi kerak!" << endl;
268
www.namspi.uz
universaljurnal.uz
return 1;
}
cout << "n (natural son) ni kiriting: ";
cin >> n;
if (n < 0) {
cout << "n natural son (0 yoki undan katta) bo'lishi kerak!" << endl;
return 1;
}
double result = power(a, n);
cout << "Natija: " << result << endl;
return 0;
}
Misol:
a (0 < a < 1) ni kiriting: 0.5
n (natural son) ni kiriting: 3
Natija: 0.125
Yoqorida keltirilgan misollardan rekursiv algoritmlardan foydalanish
masala yechimini oson va tez olish imkonini berishi ko‘rinib turibdi.
Xulosa
Rekursiv algoritmlar algebraik masalalarni yechishda kuchli va
moslashuvchan usulni taqdim etadi. Ularni turli xil algebraik ifodalar,
kombinatsiyalar va algoritmlar orqali amaliyotda sinab ko'rish, rekursiya
tushunchasini mustahkamlashga yordam beradi. Shuningdek, rekursiv algoritmlar
geometrik masalalarni yechishda kuchli vosita hisoblanadi. Ularni turli xil
geometrik ob'ektlar, maydonlar va hajmlar orqali amaliyotda sinab ko'rish,
rekursiya tushunchasini yanada chuqurroq anglashga yordam beradi. Har bir
masalani yechishda rekursiyaning qanday ishlashini tushunish muhimdir, chunki
bu mantiqiy va amaliy yechimlar yaratishda yordam beradi.
Rekursiv algoritmlar massivlar bilan ishlashda qulay va samarali
yechimlarni taqdim etadi. Yuqorida keltirilgan misollarni o'zlashtirish,
rekursiyaning qanchalik kuchli va moslashuvchan ekanligini ko'rsatadi.
Amaliyotda ushbu usullarni qo'llab, turli xil muammolarni yechishda tajriba
orttirishingiz mumkin.
Adabiyotlar ro‘yxati:
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein: "Introduction to Algorithms". The MIT Press Cambridge, Massachusetts
London, England. 2022 y.
2. Donald E. Knuth: "The Art of Computer Programming". United States.
2022 y.
269
www.namspi.uz
universaljurnal.uz
3. F.Otabayeva. Technology using the case-study method in the study of
computer graphics. Scientific Bulletin of Namangan State University 1 (12). 2019
y.
4. Robert Sedgewick, Kevin Wayne: "Algorithms". Addison-Wesley, Upper
Saddle River, NJ, 2011 y.
5. Mark Allen Weiss: "Data Structures and Algorithm Analysis in C++".
Pearson, 2014 y.
6. Gayle Laakmann McDowell: "Cracking the Coding Interview". Cracking
the Interview & Career 2015 y.
7. Steven S. Skiena: "The Algorithm Design Manual". British Library
Cataloguing in Publication Data. 2008 y.
