Muhammad Al-Xoramiy nomidagi Toshkent Axborot Texnalogiyalari Unversisteti

Rekursiv va rekursiv sanaluvchi to‘plamlar


Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari.


Biror alfabit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz.
1- ta ’rif. Agar x so'zning M to'plamga qarashlilik muammosini
hal qila oladigan algoritm mavjud bo'lsa, holda M rekursiv to‘plami
deb ataladi.
2- t a ’ r i f . Agar M to ‘plamning hamma elementlarini sanab chiqa
oladigan algoritm mavjud bo ‘Isa, u holda M effektiv rekursiv sanaluvchi
to ‘plam deb ataladi.
Ta’rif: 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.
Rekursiyaga misolllar dastrulash tilada
1 - misol: berilgan chegaragacha bolgan sonlar yegindisi.
public class Main {
public static void main(String[] args) {
int result = sum(10);
System.out.println(result);
}
public static int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
}

1. 
   misol Factorialni hiosblash dasturi.
   

Masalan: 4! = 1 *2 * 3* 4 = 24
import java.util.Scanner;

public class Factorial {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("N = ");

double n = sc.nextInt();
double factorial = factorial(n);

System.out.println("Factorial = " + factorial);
}
public static double factorial(double a){

if(a == 0) return 1;
return (int) a * factorial(a-1);

}
}



Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari.
1- teorema. Agar M va L effektiv rekursiv sanaluvchi to 'plamlar
bo ‘Isa, и holda MUL va M∩L ham effektiv rekursiv sanaluvchi
to 'plam bo 'ladi.
Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. U
holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm
mavjudki, ular orqali mos ravishda M va L dagi hamma elementlami
sanab chiqish mumkin. MUL va M∩L to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi
algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi. ■
2-teorema (Post teorem asi). M to ‘plamning о ‘zi va to ‘Idiruvchisi C M effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to ‘plam rekursivdir.
Isboti. a) M to‘plam va uning CM to'ldiruvchisi effektiv rekursiv
sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlaming elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi. U holda M va CM to'plamlaming elementlarini sanab chiqish paytida ularning ro'yxatida x element uchraydi. Demak, shunday С algoritm yuzaga keladiki, u orqali x element M to'plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, M rekursiv to‘plam bo'ladi.
b) M rekursiv to‘plam bo'lsin. U holda, 1- ta’rifga asosan, x bu
to'plamning elementimi yoki elementi emasmi degan muammoni hal
70 qiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, M va CM to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va CM to‘plamlar elementlarini sanab chiquvchi ikkita A va В
algoritmni hosil qilamiz. Demak, M va CM to‘plamlar effektiv rekursiv
sanaluvchi to‘plamlar bo'ladi.
1- misol. M = {1,4,9,...,n^2} natural sonlar kvadratlari to‘plami effektiv rekursiv sanaluvchi to'plam bo‘lishi yoki bo'lmasligini aniqlaymiz.
M to'plam effektiv rekursiv sanaluvchi to'plam bo‘ladi, chunki uning elementlarini hosil qilish uchun ketma-ket natural sonlarni olib, ularni kvadratga ko‘tarish kerak. Bu to'plam ham rekursiv bo‘ladi. Haqiqatan ham, birorta x natural sonning M to‘plamga kirish yoki kirmasligini aniqlash uchun uni tub ko‘paytuvchilarga ajratish kerak. Bu usul x natural son biror natural sonning kvadratimi yoki yo‘qmi degan savolga javob topish imkonini beradi.
Algoritmlarga Dasturlash tillida misollar
Saralash algoritmiga doir masala.
BubbleSort algoritmi
public class Search {
public static void main(String[] args) {
int[] massiv = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
int n = massiv.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (massiv[i] > massiv[k]) {
int temp;
temp = massiv[i];
massiv[i] = massiv[k];
massiv[k] = temp;
}
}
for (int i = 0; i < massiv.length; i++) {
System.out.print(massiv[i] + ", ");
}
System.out.println("\n");
}
}
}



Xulosa
Men bu mavzuni o’rganish davomida o’zim uchun kerakli bo’lgan bilimlarni oldim.Algorimtlar kundalik hayotda juda ko’p duch kelishimiz yaqol misoli kunlik ish tartibimis.Meni soham uchun ham juda kerkali bolgan algoritlardan yana yangilarini kash etdim. Qo’yilgan masalani ketma ketligini tuzish uni loyihalash va yana ko’plar tushunchalarga ega bo’ldim.


Fodalanilgan adabiyotlar
1.H. T. To‘rayev, I. Azizov, “Tafakkur Bo'stoni nashriyoti”,
MATEMATIK MANTIQ VA DISKRET MATEMATIKA
Foydalanilgan internet tarmoqlari

1. 
   Google.com
   

2. 
   Dasturchi.uz
   
3. 
   Wikipedia