15-dars: Rekursiya

4-blokO'z buyruqlaringizni yasash13–16 darslar

HayotdaPapkalar

Kompyuterda papka ichida papka bor, uning ichida yana papka. “Bu papkadagi barcha fayllarni sana” degan masalani sikl bilan yechish qiyin, chunki chuqurlik oldindan ma’lum emas. Papkani sanash uchun “har ichki papkani ham xuddi shunday sana” deyish yetadi — bu rekursiya.

Bu darsdan keyin siz

• rekursiv funksiyaning ikki majburiy qismini ayta olasiz
• rekursiya qanday ochilib, keyin qanday yopilishini kuzatasiz
• RecursionError qachon va nega chiqishini bilasiz

Nazariya

Ikki qism — ikkisi ham majburiy

Rekursiv funksiya o’zini chaqiradi. Buning ishlashi uchun ikki narsa kerak: bazaviy holat (o’zini chaqirmaydigan holat) va kichikroq masala (har chaqiruvda masala kichrayishi).

rekursiyarecursion

Funksiyaning o’zini chaqirishi. Masalani xuddi shu turdagi kichikroq masalaga keltirish usuli.

bazaviy holatbase case

Rekursiya to’xtaydigan holat. U bo’lmasa chaqiruvlar cheksiz davom etadi.

faktorial.pyNusxalash

1def faktorial(n):2  if n <= 1:        # bazaviy holat3      return 14  return n * faktorial(n - 1)    # kichikroq masala5print(faktorial(4))     # 24

Ikki yo’nalishda ishlaydi

Rekursiya avval pastga tushadi: har chaqiruv o’zidan kichigini chaqiradi va javob kutib turadi. Bazaviy holatga yetgach, javoblar yuqoriga qaytadi va har qatlam o’z hisobini bajaradi.

Shuning uchun faktorial(4) da 4 ta chaqiruv ochiladi va 4 ta qaytish bo’ladi. Hisob esa pastdan boshlanadi: 1, keyin 2×1, keyin 3×2, oxirida 4×6.

◆Asosiy g'oya

Rekursiv funksiyani o’qiyotganda “u o’zini chaqiradi” degan gapda to’xtamang. Ikki savolni bering: qachon to’xtaydi va nima kichrayadi? Ikkisidan biriga javob bo’lmasa, kod ishlamaydi.

Stek chuqurligi cheksiz emas

Har chaqiruv stekda kadr oladi (14-dars). Chaqiruvlar juda ko’p bo’lsa stek to’ladi va Python RecursionError beradi. Standart chegara — taxminan 1000 chaqiruv.

Bu himoya, kamchilik emas: chegarasiz bo’lsa xotira tugaydi va butun programma qulaydi. Chegaraga urilish deyarli har doim bitta narsani bildiradi — bazaviy holat yo’q yoki unga hech qachon yetilmaydi.

Rekursiya har doim kerakmi

Yo’q. Faktorial va yig’indini sikl bilan yozish osonroq va tezroq. Rekursiya tuzilma o’zi ichma-ich bo’lganda foyda beradi: papkalar, oila shajarasi, ichma-ich lug’atlar (12-dars).

Qoida sodda: masalaning shakli rekursiv bo’lsa, kod ham rekursiv bo’lsin.

Bashorat qiling

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1def sanoq(n):2  if n == 0:3      return4  print(n)5  sanoq(n - 1)6sanoq(3)

Sizning bashoratingizTekshirish

Javobni ko'rish

3
2
1

Har chaqiruv avval o'z sonini chop etadi, keyin kichigini chaqiradi. Shuning uchun sonlar kamayib boradi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1def sanoq(n):2  if n == 0:3      return4  sanoq(n - 1)5  print(n)6sanoq(3)

Sizning bashoratingizTekshirish

Javobni ko'rish

1
2
3

Ikki qator joyi almashdi. Endi har chaqiruv avval pastga tushadi, chop etish esa QAYTISHDA bajariladi — natija teskari tartibda chiqadi.

Sinab ko’r

Uch variantni ketma-ket bajaring. Uchinchisi — «Bazaviy holat yo’q» — majburiy: rekursiyani tushunish uchun uning qanday buzilishini ko’rish kerak.

Rekursiya daraxti

Variantni tanlab qadamlang: chaqiruvlar ochiladi, keyin yopiladi. Klaviatura: → keyingi qadam.

Bu simulyatorda rekursiv chaqiruvlar qadamlab ochiladi va yopiladi. Chuqurlik chekinish bilan ko'rinadi, har chaqiruv javobini kutib turadi.

JavaScript'siz mashq: faktorial(4) hisoblanishini qo'lda yozib chiqing — 4 * (3 * (2 * 1)). Pastga tushish to'rt qatlam, yuqoriga qaytish ham to'rt qatlam. Uchinchi variant esa bazaviy holat yo'q bo'lsa nima bo'lishini ko'rsatadi: RecursionError.

faktorial(4)yigindi(3)Bazaviy holat yo'q

OrqagaKeyingi qadamQayta boshlash

Ikki sanoq variantini eslang: print ni rekursiv chaqiruvdan oldin yoki keyin qo’yish natijani teskari o’zgartiradi. Sabab shu simulyatorda ko’rinadi — pastga tushish va yuqoriga qaytish ikki alohida yo’nalish.

Xatoni toping

×Bu kod ataylab buzuq — xatoni toping

Buzuq kodNusxalash

1def kamayt(n):2  print(n)3  kamayt(n - 1)4kamayt(3)

Python shunday javob beradi:

3
2
1
0
-1
...
File "kamayt.py", line 3, in kamayt
  kamayt(n - 1)
RecursionError: maximum recursion depth exceeded

Sababi va tuzatish

Bazaviy holat yo'q. n kamayib boradi, lekin hech qachon to'xtamaydi — manfiy sonlarga o'tib ketadi.

Ekranda sonlar chiqqani chalg’itadi: programma «ishlayotgandek» ko’rinadi. Aslida u birinchi qadamdan buzuq edi.

tuzatilgan.pyNusxalash

1def kamayt(n):2  if n < 0:          # bazaviy holat qo'shildi3      return4  print(n)5  kamayt(n - 1)6kamayt(3)

Shartni yozganda chegarani tekshirib ko’ring: if n == 0 bo’lsa ham ishlaydi, lekin kamayt(-5) chaqirilsa yana cheksiz ketadi. n < 0 esa har qanday kirishda to’xtaydi.

O’zingizni sinang

1Rekursiv funksiyaning ikki majburiy qismi qaysi?

Javobni ko'rish

Bazaviy holat (o’zini chaqirmaydigan holat) va kichikroq masala (har chaqiruvda masala kichrayishi).

2faktorial(4) da hisob qaysi tomondan boshlanadi?

Javobni ko'rish

Pastdan: bazaviy holat 1 qaytaradi, keyin 2×1, 3×2, oxirida 4×6 = 24. Chaqiruvlar pastga tushadi, hisob yuqoriga qaytadi.

3RecursionError chiqdi. Birinchi navbatda nimani tekshirasiz?

Javobni ko'rish

Bazaviy holatni: u bormi va unga yetish mumkinmi. Deyarli har doim muammo shu ikkisidan biri.

4print ni rekursiv chaqiruvdan keyin qo'ysangiz nima o'zgaradi?

Javobni ko'rish

Chop etish qaytish yo’nalishida bajariladi, demak natija teskari tartibda chiqadi.

5Qaysi masalada rekursiya siklga afzalroq?

Javobni ko'rish

Tuzilmaning o’zi ichma-ich bo’lganda: papka ichidagi papkalar, ichma-ich lug’atlar, shajara. Oddiy yig’indi uchun sikl osonroq.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

sanoq(n) funksiyasini yozing: n dan 1 gacha sonlarni chop etsin. Keyin print qatorini rekursiv chaqiruvdan keyinga ko’chirib, natija qanday o’zgarganini daftaringizga yozing.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

yigindi(n) funksiyasini rekursiya bilan yozing (1 dan n gacha). Keyin xuddi shu funksiyani sikl bilan ham yozing. Ikki variantni solishtirib, qaysi biri o’qishga osonroq va nega — izohda yozing. yigindi(2000) chaqirib ko’ring va natijani izohlang.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Ichma-ich lug’atdagi barcha sonlarni yig’adigan rekursiv funksiya yozing: lug’at ichida lug’at, ichida ro’yxat bo’lishi mumkin. Chegara holatlarini tekshiring: bo’sh lug’at, faqat sonlar, aralash qiymatlar. Keyin bir savolga javob bering: bu masalani sikl bilan yechish uchun nima qilish kerak bo’lardi?

⏸AI hozircha kutib tursin

Bu darsning topshiriqlarini AI'dan so'ramang. Yechimni ko'rgan miya o'z modelini qurmaydi — model qurmagan odam esa uch oydan keyin AI'siz bir qator ham yoza olmaydi. AI bilan to'g'ri ishlashni 20-darsda o'rganasiz: u yerda AI sizga emas, siz AI'ga baho berasiz.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim