> For the complete documentation index, see [llms.txt](https://isystem.gitbook.io/programming/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isystem.gitbook.io/programming/kengaytirilgan-kontent/1.-rekursiya.md). # 1. Rekursiya ### Rekursiya nima? Funksiya o'zini to'g'ridan -to'g'ri yoki bilvosita chaqirish jarayonini rekursiya, unga mos funksiyani esa rekursiv funksiya deb atashadi. Rekursiv algoritmdan foydalanib, ba'zi muammolarni juda oson hal qilish mumkin. Bunga Xanoy minoralari (TOH), Inorder/Preorder/Postorder Traversals, DFS of Graph va boshqalar misol bo'la oladi. ### Matematik talqini Dasturchi birinchi ***n*** natural sonlarning yig'indisini aniqlashi kerak bo'lgan muammoni ko'rib chiqaylik, buning bir necha yo'li bor, lekin eng oddiy yondashuv *1* dan *n* gacha bo'lgan sonlarni qo'shishdir. Shunday qilib, funksiya shunchaki shunday ko'rinadi: $$ f(n) = 1 + 2 + 3 +……..+ n $$ Lekin buni ifodalashning boshqa matematik yondashuvi bor, $$ f(n) = 1 \space \space \space \space n=1\newline f(n) = n + f(n-1) \space \space \space \space n>1 $$ Yondashuv (#1) va yondashuv (#2) o'rtasida oddiy farq bor va bu (2) yondashuvda "f ()" funksiyasining o'zi funksiya ichida chaqiriladi, shuning uchun bu hodisa rekursiya va o'z ichiga olgan funksiya deb nomlanadi. Rekursiya rekursiv funksiya deb ataladi, natijada bu dasturchilar qo'lida ba'zi muammolarni ancha oson va samarali kodlash uchun ajoyib vosita. ### Rekursiyada asosiy shart nima? Rekursiv dasturda asosiy holatning yechimi taqdim etiladi va katta masalaning yechimi kichikroq masalalar bilan ifodalanadi. ```cpp int fact(int n) { if (n < = 1) // asosiy holat return 1; else return n*fact(n-1); } ``` Yuqoridagi misolda, *n <= 1* uchun asosiy holat aniqlangan va sonning kattaroq qiymatini kichik songa aylantirish orqali hal qilish mumkin. ### Muayyan muammo rekursiya yordamida qanday hal qilinadi? Maqsad bitta yoki bir nechta kichikroq muammolarni ifodalash va rekursiyani to'xtatuvchi bir yoki bir nechta asosiy shartlarni qo'shishdan iborat. Masalan, agar biz **(n-1)** faktorialini bilsak, faktorial n ni hisoblaymiz. Faktorial uchun asosiy holat **n = 0** bo'ladi. **N = 0** bo'lganda 1 qaytaramiz. ### Nima uchun Stack Overflow xatosi rekursiyada paydo bo'ladi? Agar asosiy holatga erishilmagan yoki aniqlanmagan bo'lsa, unda *Stack Overflow* ( ma'lumotlar to'plamini ko'payib ketishi) muammosi paydo bo'lishi mumkin. Buni tushunish uchun misol keltiraylik. ```cpp int fact(int n) { // noto'g'ri holat (bu stack overflow ga olib kelishi mumkin). if (n == 100) return 1; else return n*fact(n-1); } ``` Agar *fakt (10)* chaqirilsa, u *fakt (9)*, *fakt (8)*, *fakt (7)* va boshqalarni chaqiradi, lekin bu raqam hech qachon 100ga etmaydi. Demak, asosiy holatga erishilmagan. Agar xotira bu funksiyalar tufayli to'plamda tugagan bo'lsa, bu to'plamni to'ldirish xatosiga olib keladi. ### To'g'ridan - to'g'ri va bilvosita rekursiya o'rtasidagi farq nima? Funksiya bir xil fun funksiyani chaqirsa, to'g'ridan - to'g'ri rekursiv deb ataladi. ```cpp // To'g'ridan -to'g'ri rekursiyaga misol void directRecFun() { // Ba'zi kod.... directRecFun(); // Ba'zi kod... } // Bilvosita rekursiyaga misol void indirectRecFun1() { // Ba'zi kod... indirectRecFun2(); // Ba'zi kod... } void indirectRecFun2() { // Ba'zi kod... indirectRecFun1(); // Ba'zi kod... } ``` ### Quyruqli va dumsiz rekursiya o'rtasidagi farq nima? Rekursiv funksiya quyruqli rekursivdir, agar rekursiv chaqiruv funksiya tomonidan bajariladigan oxirgi narsa bo'lsa. Tafsilotlar uchun quyruq rekursiyasi haqidagi maqolaga qarang. ### Rekursiyada turli xil funksional qo'ng'iroqlar uchun xotira qanday ajratiladi? Main **( )** dan biron - bir funksiya chaqirilganda, xotira unga to'plamda ajratiladi. Rekursiv funksiya o'zini - o'zi chaqiradi, chaqirilgan funksiyani xotirasi chaqiruv funksiyasiga ajratilgan xotira ustiga ajratiladi va har bir funksiya chaqiruvi uchun mahalliy o'zgaruvchilarning turli nusxalari yaratiladi. Asosiy holatga kelganda, funksiya o'z qiymatini o'zi chaqirgan funksiyaga qaytaradi va xotira ajratilmaydi va jarayon davom etadi. Keling, oddiy funksiyadan foydalanib, rekursiya qanday ishlashini olaylik. {% tabs %} {% tab title="C++" %} ```cpp // A C++ program to demonstrate working of // recursion #include using namespace std; void printFun(int test) { if (test < 1) return; else { cout << test << " "; printFun(test - 1); // statement 2 cout << test << " "; return; } } // Driver Code int main() { int test = 3; printFun(test); } ``` {% endtab %} {% tab title="JAVA" %} ```java // A Java program to demonstrate working of // recursion class GFG { static void printFun(int test) { if (test < 1) return; else { System.out.printf("%d ", test); printFun(test - 1); // statement 2 System.out.printf("%d ", test); return; } } // Driver Code public static void main(String[] args) { int test = 3; printFun(test); } } // This code is contributed by // Smitha Dinesh Semwal ``` {% endtab %} {% tab title="Python3" %} ```python # A Python 3 program to # demonstrate working of # recursion def printFun(test): if (test < 1): return else: print(test, end=" ") printFun(test-1) # statement 2 print(test, end=" ") return # Driver Code test = 3 printFun(test) # This code is contributed by # Smitha Dinesh Semwal ``` {% endtab %} {% tab title="C#" %} ```csharp // A C# program to demonstrate // working of recursion using System; class GFG { // function to demonstrate // working of recursion static void printFun(int test) { if (test < 1) return; else { Console.Write(test + " "); // statement 2 printFun(test - 1); Console.Write(test + " "); return; } } // Driver Code public static void Main(String[] args) { int test = 3; printFun(test); } } // This code is contributed by Anshul Aggarwal. ``` {% endtab %} {% tab title="PHP" %} ```php ``` {% endtab %} {% tab title="JavaScript" %} ```javascript ``` {% endtab %} {% endtabs %} #### Natija: ``` 3 2 1 1 2 3 ```