105
C++ DASTURLASH TILIDA REKURSIYADAN FOYDALANISH
ИСПОЛЬЗОВАНИЕ РЕКУРСИИ В ЯЗЫКЕ ПРОГРАММИРОВАНИЯ C++
USING RECURSION IN THE C++ PROGRAMMING LANGUAGE
Shermatova Xilola Mirzayevna
FarDU Axborot texnologiyalari kafedrasi dotsenti
shermatovahilola1978@gmail.com
Abdumalikova Shalola Alimardon qizi
FarDU Axborot tizimlari va tehnologiyalari yo’nalishi 1-kurs talabasi
xonshalola818@gmail.com
https://doi.org/10.5281/zenodo.15182233
Annotatsiya.
Rekursiya - bu funksiyaning o‘zini o‘zi chaqirishi orqali muammolarni hal
qilish usuli bo‘lib, C++ dasturlash tilida keng qo‘llaniladi. U asosan daraxt va bog‘langan
ro‘yxatlar kabi ma’lumot tuzilmalarini qayta ishlash, shuningdek, matematik masalalarni
yechishda ishlatiladi. Rekursiv yondashuv kodni soddalashtiradi, biroq noto‘g‘ri ishlatilsa, stek
to‘lib qolishi mumkin. Shuning uchun, rekursiyadan samarali foydalanish uchun to‘g‘ri chiqish
shartlarini belgilash va rekursiv chaqiruvlarni nazorat qilish muhimdir.
Аннотация.
Рекурсия - это метод программирования, при котором функция
вызывает саму себя для решения подзадач. В языке C++ рекурсия часто используется
для работы со структурами данных, такими как деревья и списки, а также для решения
математических задач, например, вычисления факториала или чисел Фибоначчи. Хотя
рекурсия делает код более читаемым и элегантным, чрезмерное её использование
может привести к переполнению стека. Поэтому важно грамотно управлять
рекурсивными вызовами и предусматривать условия выхода из рекурcuu.
Abstract.
Recursion is a programming technique in which a function calls itself to solve
subproblems. In C++, recursion is commonly used for working with data structures such as
trees and linked lists, as well as solving mathematical problems like calculating factorials or
Fibonacci numbers. While recursion makes code more readable and elegant, excessive use can
lead to stack overflow. Therefore, it is crucial to manage recursive calls properly and define
base cases to prevent infinite recurce.
Kalit so‘zlar:
Rekursiya, funksiya, C++, ma’lumot tuzilmalari, daraxt, bog‘langan ro‘yxat,
matematik masalalar, faktorial, Fibonachchi sonlari, stek, chiqish sharti.
Ключевые слова:
Рекурсия, функция, C++, структуры данных, дерево, связанный
список, математические задачи, факториал, числа Фибоначчи, стек, условие выхода.
Keywords:
Recursion, function, C++, data structures, tree, linked list, mathematical
problems, factorial, Fibonacci numbers, stack, base case.
KIRISH
Zamonaviy dasturlash tillari orasida keng qo‘llaniladigan va yuqori darajadagi
imkoniyatlarga ega bo‘lgan C++ tili, algoritmik fikrlashni chuqurroq anglash imkonini beruvchi
vositalardan biridir. Ayniqsa, C++ tilida
rekursiya
tushunchasi dasturchilar uchun muhim
mavzulardan biri hisoblanadi. Rekursiya — bu funksiyaning o‘zini-o‘zi chaqirishi orqali
muammoni kichik qismlarga ajratib hal qilish usuli bo‘lib, murakkab masalalarni
soddalashtirib, kodni ixcham va tushunarli qilish imkonini beradi.
Rekursiv funksiyalar ko‘pincha matematik va algoritmik muammolarni hal qilishda,
masalan, faktorial hisoblash, Fibonachchi sonlarini topish, binar daraxtlarni ko‘rish, qidiruv va
tartiblash algoritmlarida keng qo‘llaniladi. Ushbu maqolada C++ dasturlash tilida rekursiya
106
qanday ishlashi, uning afzalliklari va kamchiliklari, shuningdek, amaliy misollar orqali qanday
qo‘llanilishi batafsil yoritiladi. Maqola nafaqat nazariy tushunchalarni, balki rekursiyani to‘g‘ri
va samarali ishlatish bo‘yicha tavsiyalarni ham o‘z ichiga oladi.
Rekursiya - bu funksiyaning o‘zini-o‘zi chaqirishi orqali bajariladigan dasturlash usuli
bo‘lib, u murakkab muammolarni soddalashtirib yechish imkonini beradi. C++ dasturlash tilida
rekursiya muhim mavzulardan biri hisoblanadi, chunki u yordamida ba’zi muammolarni ancha
ixcham va tushunarli tarzda ifodalash mumkin.
Rekursiv funksiyalar ikki asosiy elementdan iborat bo‘ladi. Birinchisi - bu bazaviy holat
bo‘lib, u rekursiv jarayonning to‘xtash nuqtasini bildiradi. Ikkinchisi esa rekursiv chaqiriq
bo‘lib, funksiyaning o‘zini kichikroq muammoga nisbatan qayta chaqirishidir. Har bir rekursiv
chaqiriq dastur stekida yangi kontekst yaratadi, bu esa ma’lum bir nuqtada xotira tugash xavfini
keltirib chiqarishi mumkin. Shu sababli, rekursiyani to‘g‘ri ishlatish, ya’ni bazaviy holatni aniq
belgilash va har bir chaqiriqda unga yaqinlashib borishni ta’minlash muhim ahamiyatga ega.
Rekursiya orqali ko‘plab algoritmik masalalarni samarali yechish mumkin. Masalan,
matematik hisob-kitoblar, jumladan faktorial yoki Fibonachchi sonlarini hisoblash, turli daraxt
ko‘rinishidagi tuzilmalarni ko‘rish va analiz qilish, grafiklarda qidiruv bajarish, fayl tizimlarida
papkalar va fayllarni tahlil qilish kabilarda rekursiya keng qo‘llaniladi.
Rekursiyaning afzalliklariga to‘xtaladigan bo‘lsak, u kodni sodda va ixcham yozishga
imkon beradi, ayniqsa strukturalashtirilgan yoki takrorlanuvchi muammolarda foydali bo‘ladi.
Rekursiv yondashuv ko‘pincha muammoning mohiyatini yanada tushunarliroq tarzda
ifodalaydi. Biroq, rekursiyaning kamchiliklari ham bor: u ko‘p hollarda ko‘proq xotira talab
qiladi va noto‘g‘ri ishlatilganda dasturda stack overflow xatosi yuzaga kelishi mumkin. Shu
sababli ba’zi holatlarda tsikllar asosida ishlovchi yondashuvlar rekursiyaga qaraganda
samaraliroq bo‘lishi mumkin.
Haqiqatan ham, natural sonlarni quyidagicha ifodalash mumkin:
Natural son:
1 - natural son.
Natural sondan keyin keluvchi son - natural son.
Xuddi shunday faktorial tushunchasi n!=1·2·3·…·(n-1)·n ni ham rekursiya yordamida
tushuntirish mumkin:
Faktorial: 0!=1 (shartli qabul qilingan).
n>0 uchun n! = n * (n - 1)
Rekursiv triada:
Masalalarni rekursiv usulda yechish uchun rekursiv triada deb ataluvchi quyidagi
bosqichlar ishlab chiqiladi:
Parametrlarni aniqlash – masalaning shartlarini tavsiflash uchun va yechimni olishda
qo’llaniladigan parametrlarni tanlash;
Rekursiya tayanchi– yechimni olish vaqtida funktsiyaning o’zigamurojaatni talab
etmaydigan arzimas holatlarni aniqlash;
Dekompozitsiya – umumiy masalani parametrlarni o’zgartirish orqali ancha sodda qism
masalalarga ajratgan holda ifodalash xatolik qilmaydigandek ko’rinadi.
Parametrlarni aniqlash: n – manfiy bo’lmagan butun son. Rekursiya tayanchi: n =0 uchun
faktorial 1 ga teng.
107
Navbatdagi Fibanachchi sonini topish undan oldingi ikkita f1 va f2 o’zgaruvchilarda
saqlanayotgan sonlarga bog’liq ekanligi ma’lum. Oldin f1=1 va f2=0 larni qabul qilib, keyingi
fibanachchi sonini hisoblaymiz va uni x o’zgaruvchiga saqlab qo’yyamiz. Endi f2 qiymat bizga
kerak emas, shuning uchun f1 ni f2 ga va x ni f1 ga nusxalaymiz.
Dasturning asosiy kodi
int Fib2(int n)
{ int i, f1=1, f2=0, x;
for (i=2; i<=n; i++) {
x=f1+f2; //keyingi son
f2=f1; f1=x; //qiymatlarni siljitish
}
return x; }
Parametrlarni aniqlash: n – manfiy bo’lmagan butun son.
Bazaviy holat
– rekursiyani to‘xtatish sharti, aks holda funksiya cheksiz chaqirilib qolishi
mumkin.
Rekursiv chaqiriq
– funksiya o‘zini o‘zi chaqirib, masalani kichikroq qismga ajratadi.
Stack memory
– har bir rekursiv chaqiriq stack xotirada yangi joy egallaydi, shuning
uchun rekursiya juda chuqur bo‘lsa, stack overflow xatosi yuzaga kelishi mumkin.
#include <iostream>
using namespace std;
// Rekursiv funksiya
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 10;
cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
return 0;
}
XULOSA
C++ dasturlash tilida
rekursiya
— bu murakkab muammolarni sodda, takrorlanuvchi
qismlarga ajratib hal qilish imkonini beruvchi samarali vositadir. Rekursiv funksiyalar ko‘p
hollarda algoritmlarni yanada ixcham va tushunarli yozishga xizmat qiladi. Ayniqsa, matematik
hisob-kitoblar, daraxt ko‘rinishidagi tuzilmalarni ko‘rish, qidiruv, tartiblash va kombinatorik
masalalarda rekursiya orqali kod soddalashtiriladi va algoritm mantig‘i yanada ravshan bo‘ladi.
Biroq, rekursiyadan foydalanishda ehtiyotkorlik talab qilinadi. Har bir rekursiv chaqiriq
xotirada yangi funksiyalar stekini yaratadi, bu esa noto‘g‘ri ishlatilsa,
xotira to‘lib ketishiga
olib kelishi mumkin. Shu sababli, rekursiv funksiyalarni yozishda
asosiy holat
to‘g‘ri
aniqlanishi va har bir chaqiriq bazaviy holatga yaqinlashib borishi ta’minlanishi lozim.
Xulosa qilib aytganda, rekursiya C++ dasturlash tilining kuchli imkoniyatlaridan biri
bo‘lib, u orqali ko‘plab masalalarni samarali hal qilish mumkin. Dasturchilar rekursiyani to‘g‘ri
108
tushunib, uni oqilona qo‘llay bilsalar, ular o‘z dasturlarini nafaqat toza va ixcham, balki samarali
va yuqori darajadagi algoritmik yechimlarga asoslangan holatda yozish imkoniyatiga ega
bo‘ladilar.
Foydalanilgan adabiyotlar/Используемая литература/References:
1.
Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и
алгоритмы. Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с
2.
Adam Drozdek. Data structures and algorithms in C++. Fourth edition. Cengage Learning,
2013.
3.
Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi
СПб: ООО «ДиаСофтЮП», 2003. 560с.
4.
Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar.
5.
O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
6.
Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов.
- Краснодар: КубГАУ. 2000. - 261 с., ил.
7.
Koenig A., Moo B.E. Accelerated C++: Practical Programming by Example – Addison-
Wesley, 2000.
8.
ISO/IEC 14882:2017. Programming Languages – C++ – International Organization for
Standardization, 2017.
9.
Eckel B. Thinking in C++ – Prentice Hall, 2000.
10.
Balagurusamy E. Object-Oriented Programming with C++ – McGraw-Hill Education, 2013.
11.
Sutter H. Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions
– Addison-Wesley, 2000.
12.
Horton I. Beginning C++: The Complete Guide to C++ Programming – Wrox, 2014.
13.
Schildt H. C++: The Complete Reference – McGraw-Hill, 2012.
14.
Savitch W.J. Problem Solving with C++ – Pearson, 2018.
15.
Malik D.S. C++ Programming: From Problem Analysis to Program Design – Cengage
Learning, 2017.
