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.

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.

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.

// 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.

C++

// A C++ program to demonstrate working of
// recursion
#include <bits/stdc++.h>
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);
}

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

Python3

# 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

C#

// 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.

PHP

<?php
// PHP program to demonstrate
// working of recursion

// function to demonstrate
// working of recursion
function printFun($test)
{
	if ($test < 1)
		return;
	else
	{
		echo("$test ");
		
		// statement 2
		printFun($test-1);
		
		echo("$test ");
		return;
	}
}

// Driver Code
$test = 3;
printFun($test);

// This code is contributed by
// Smitha Dinesh Semwal.
?>

JavaScript

<script>

// JavaScript program to demonstrate working of
// recursion

function printFun(test)
	{
		if (test < 1)
			return;
		else {
			document.write(test + " ");
			printFun(test - 1); // statement 2
			document.write(test + " ");
			return;
		}
	}

// Driver code
	let test = 3;
	printFun(test);

</script>

Natija:

3 2 1 1 2 3