Rekursiya
Rekursiya — funksiya o‘zini o‘zi chaqirishi. Faktorial va Fibonachchi sonlari misolida rekursiyaning tuzilishi, to‘xtash sharti va xavfli tomonlarini o‘rganamiz.
Mavzular ro‘yxati (3 / 11)
1-bob. Algoritmlar
2-bob. Ma’lumotlar tuzilmasi
3-bob. Ma’lumotlar bazalari
4-bob. Zamonaviy texnologiyalar va loyihalar
Rekursiya — funksiya o‘zining ishi davomida o‘zini chaqirishi. Murakkab masala xuddi shunday, lekin kichikroq masalaga keltiriladi; shu jarayon eng sodda holatga yetguncha davom etadi. Har qanday to‘g‘ri rekursiv funksiyada ikki qism bo‘ladi: to‘xtash sharti (rekursiyasiz javob beriladigan eng sodda holat) va rekursiv qadam (funksiya kichikroq ma’lumot bilan o‘zini chaqiradi).
Klassik misol — faktorial: n! = n · (n − 1)!, 0! = 1. Python’da bu shunday yoziladi: def f(n): return 1 if n == 0 else n * f(n - 1). f(3) chaqirilganda 3 * f(2), so‘ng 2 * f(1), so‘ng 1 * f(0) hisoblanadi; f(0) ga yetgach javoblar teskari tartibda qaytib, natija 6 chiqadi. To‘xtash sharti bo‘lmasa, funksiya cheksiz o‘zini chaqirardi.
Fibonachchi sonlari ham rekursiv aniqlanadi: fib(n) = fib(n - 1) + fib(n - 2), fib(0) = 0, fib(1) = 1. Biroq oddiy yozilganda bir xil qiymatlar qayta-qayta hisoblanadi va n oshgan sari vaqt juda tez o‘sadi; masalan, fib(40) ni shu usulda hisoblash sezilarli vaqt oladi. Bunday hollarda oraliq natijalarni saqlash yoki sikldan foydalanish samaraliroq.
Har bir rekursiv chaqiruv xotirada joy egallaydi, shuning uchun juda chuqur rekursiya xotira to‘lishiga olib keladi. Python’da chuqurlik cheklangan (odatda taxminan 1000 ta chaqiruv), undan oshsa RecursionError xatosi chiqadi. Rekursiya daraxtsimon ma’lumotlar va “bo‘lib hal qilish” algoritmlari uchun qulay, oddiy takrorlash uchun esa sikl ko‘pincha tezroq va xavfsizroq.
Asosiy xulosalar
- Rekursiya — funksiyaning o‘zini kichikroq ma’lumot bilan chaqirishi.
- Rekursiyada doim to‘xtash sharti va rekursiv qadam bo‘lishi shart.
- To‘xtash sharti bo‘lmasa, rekursiya tugamaydi va xato yuzaga keladi.
- Oddiy yozilgan rekursiv Fibonachchi bir xil qiymatlarni takror hisoblagani uchun sekin.
- Python’da rekursiya chuqurligi cheklangan (taxminan 1000).
Amaliy topshiriqlar
f(4)faktorialini rekursiv funksiya bo‘yicha qo‘lda hisoblang: barcha chaqiruvlarni va ularning qaytargan qiymatlarini ketma-ket yozing.- Rekursiv funksiya yozing:
ndan1gacha bo‘lgan sonlar yig‘indisini qaytarsin. Natijani siklli variant bilan solishtiring. - Rekursiv funksiya yordamida sonning raqamlari yig‘indisini toping (masalan, 2745 uchun 18). Maslahat:
n % 10— oxirgi raqam,n // 10— qolgan qism.
Mustahkamlash savollari
O‘zingizni sinab ko‘ring: avval o‘ylab ko‘ring, keyin javobni oching.
1Rekursiv funksiyaning ikki majburiy qismi nima?Javobni ko‘rishJavobni yashirish
To‘xtash sharti (eng sodda holat) va rekursiv qadam (funksiyaning o‘zini kichikroq ma’lumot bilan chaqirishi).2Nima uchun rekursiv `fib(40)` sekin ishlaydi?Javobni ko‘rishJavobni yashirish
Bir xil qiymatlar son-sanoqsiz marta qayta hisoblanadi, chaqiruvlar soni esa n oshgan sari juda tez ko‘payadi.3Python’da juda chuqur rekursiya qanday xatoga olib keladi?Javobni ko‘rishJavobni yashirish
`RecursionError`: chaqiruvlar chuqurligi cheklovdan (odatda ~1000) oshib ketadi.
Saytga kiring
Slaydlar va PDF faqat ro‘yxatdan o‘tgan foydalanuvchilar uchun: ko‘rish ham, yuklab olish ham. Kirish bepul.
Saytga kiring
Slaydlar va PDF faqat ro‘yxatdan o‘tgan foydalanuvchilar uchun: ko‘rish ham, yuklab olish ham. Kirish bepul.
0 / 11 mavzu o‘tildi
Kirib belgilash