8-hafta · Foundation

Rekursiya va fayllar

Bu darsda ikki kuchli mavzu. Birinchisi rekursiya: funksiyaning o'z-o'zini chaqirishi. Avval g'alati tuyuladi, lekin ba'zi masalalarni hayratlanarli darajada soddalashtiradi. Ikkinchisi fayllar: ma'lumotni dastur tugagandan keyin ham diskda saqlash. Rekursiyani jonli chaqiruv steki diagrammasida ko'ramiz.

Bu darsda nimani o'rganasiz

Rekursiya nima va asosiy holat nega muhimligini tushunasiz

Rekursiv funksiya muammoni kichraytirib yechishini ko'rasiz

Chaqiruv steki (call stack) qanday ishlashini kuzatasiz

Rekursiya va siklni solishtirasiz

Faylni fopen va fclose bilan ochib yopasiz

Faylga yozasiz (fprintf) va fayldan o'qiysiz (fgets)

8.1 Rekursiya nima?

Rekursiya (recursion) deganda funksiyaning o'z-o'zini chaqirishi tushuniladi. Birinchi marta eshitganda bu g'alati: funksiya o'zini qanday chaqiradi? Lekin g'oya sodda: katta masalani biroz kichikroq, lekin xuddi shunday masalaga aylantiramiz.

Tasavvur qiling, ikki oyna bir-biriga qaragan. Har bir oynada yana bir oyna, unda yana bir oyna, va hokazo. Rekursiya ham shunday: har bir chaqiruv ichida yana o'zining kichikroq nusxasi bor.

Misol uchun, sonni teskari sanash. sanash(3) avval 3 ni chiqaradi, so'ng sanash(2) ni chaqiradi, u 2 ni chiqaradi va sanash(1) ni chaqiradi, va hokazo. Har bir chaqiruv ozgina kichikroq.

Rekursiyaning ikkita qismi bor: asosiy holat (qachon to'xtash) va rekursiv qadam (kichikroq masalaga o'tish). Ikkalasini birga ko'rib chiqamiz.

8.2 Asosiy holat (base case)

Agar funksiya doim o'zini chaqiraversa, u hech qachon to'xtamaydi va dastur qulaydi. Shuning uchun har bir rekursiyada asosiy holat (base case) bo'lishi shart: bu rekursiyani to'xtatuvchi shart. Quyidagi teskari sanashda asosiy holat n == 0: bu yerga yetganda funksiya o'zini chaqirmaydi, shunchaki qaytadi.

sanash.c

1void sanash(int n) {

2 if (n == 0) return; // asosiy holat

3 printf("%d\n", n);

4 sanash(n - 1); // rekursiv qadam

Bajar tugmasini bosing, sanash(3) qanday ishlashini ko'ring:

Teskari sanash Bajar

terminal

«Bajar» tugmasini bosing: 3, 2, 1 chiqadi, so'ng n == 0 ga yetganda to'xtaydi.

8.3 Rekursiv qadam

Rekursiv qadamda muammo har safar kichikroq bo'ladi va asosiy holatga yaqinlashadi. Klassik misol: faktorial. n! bu 1 dan n gacha sonlarning ko'paytmasi. Rekursiv ta'rifi juda chiroyli: n! = n * (n-1)!, va asosiy holat 1! = 1.

factorial.c

1int factorial(int n) {

2 if (n == 1) return 1; // asosiy holat

3 return n * factorial(n - 1);

Sonni tanlang va faktorial qanday yoyilishini ko'ring:

Faktorial yoyilishi sonni tanlang

n =

terminal

8.4 Chaqiruv steki (call stack)

Endi eng muhim qismi: rekursiya ichida nima sodir bo'ladi? Har bir funksiya chaqiruvi xotirada chaqiruv steki (call stack) ga yangi freym qo'shadi. Bu o'tgan haftadagi stek (LIFO) ning aynan o'zi! Chaqiruvlar taxlanib boradi, asosiy holatga yetganda esa birma-bir qaytib, javoblar ko'paytirilib chiqadi.

Keyingi qadam bilan factorial(4) ni kuzating. Yashil freym hozir qaytayotgan chaqiruv:

Chaqiruv steki izlagichi qadamlang

stek tepasi (oxirgi chaqiruv)

E'tibor bering: chaqiruvlar avval pastga (4, 3, 2, 1) taxlanadi, so'ng asosiy holatdan boshlab yuqoriga qaytadi (1, 2, 6, 24). Aynan shu sabab rekursiya stek ustiga quriladi.

8.5 Rekursiya vs sikl

Faktorialni sikl bilan ham yozsa bo'lardi. Ko'p masalani ikkala usul ham yecha oladi. Tanlov ravshanlik va masala tabiatiga bog'liq:

Xususiyat	Rekursiya	Sikl
Kod ko'rinishi	ba'zan soddaroq, tabiiy	ba'zan uzunroq
Xotira	stek freymlari (ko'proq)	ixcham
Juda chuqur	stek to'lib ketishi mumkin	muammo yo'q
Mos masala	daraxt, papka, bo'linadigan	oddiy takrorlash

Qisqacha: oddiy takrorlash uchun sikl yaxshi. Lekin masala o'zini kichik nusxalarga bo'linsa (daraxt yurish, papkalar ichidagi papkalar), rekursiya ancha tabiiy va o'qishga oson.

8.6 Misol: Fibonachchi

Fibonachchi ketma-ketligi rekursiyaning mashhur misoli. Har bir son o'zidan oldingi ikkitasining yig'indisi: fib(n) = fib(n-1) + fib(n-2). Asosiy holatlar: fib(0) = 0 va fib(1) = 1. Ketma-ketlik: 0, 1, 1, 2, 3, 5, 8, 13, ...

Sonni tanlang va natijani hamda ketma-ketlikni ko'ring:

Fibonachchi sonni tanlang

fib(

) = 13

Diqqat: oddiy rekursiv Fibonachchi sekin, chunki bir xil qiymatni qayta-qayta hisoblaydi (fib(5) ichida fib(3) bir necha marta chaqiriladi). Buni keyinroq, xotirlash (memoization) bilan tezlashtirish mumkin.

8.7 Fayllar: ochish va yopish

Endi ikkinchi mavzu. Hozirgacha dastur tugagach, barcha ma'lumot yo'qolardi. Fayl ma'lumotni diskda saqlaydi, shuning uchun dastur qayta ishga tushganda ham u joyida turadi. C da fayl bilan ishlash uchun avval uni ochamiz, ishlatamiz, so'ng yopamiz.

fayl.c

1FILE *f = fopen("matn.txt", "w"); // ochish

2// ... fayl bilan ishlash ...

3fclose(f); // yopish, shart!

fopen faylni ochib, unga pointer (FILE *) qaytaradi. Ikkinchi parametr rejim: u faylni nima maqsadda ochishni bildiradi:

"r" o'qish (read): mavjud fayldan o'qish uchun
"w" yozish (write): yangi yozish, eski mazmun o'chadi
"a" qo'shish (append): oxiriga qo'shib yozish

Faylni ishlatib bo'lgach fclose qilish shart, xuddi malloc'dan keyingi free kabi. Aks holda yozilgan ma'lumot diskka to'liq saqlanmay qolishi mumkin.

8.8 Faylga yozish

Faylga matn yozish uchun fprintf ishlatamiz. U aynan printf kabi, faqat birinchi parametri sifatida fayl pointerini oladi: fprintf(f, "%s\n", matn). Pastda satr kiriting va faylga yozing:

Faylga yozish (fprintf) satr qo'shing

matn.txt

8.9 Fayldan o'qish

Fayldan o'qish uchun fgets bir qatorni o'qiydi, yoki fscanf formatlangan ma'lumotni o'qiydi. Odatda biz faylni boshidan oxirigacha, qatorma-qator o'qib chiqamiz, fayl tugaguncha. Pastda fayl tayyor. Keyingi qatorni o'qi bilan birma-bir o'qing:

Fayldan o'qish (fgets) qatorma-qator

royxat.txt

terminal

Bashorat qiling

factorial(3) qanday natija qaytaradi?

8.10 Chuqurroq advanced

Rekursiya va fayllarning yana bir nechta muhim jihati.

Stek to'lib ketishi

Agar rekursiya juda chuqur bo'lsa (yoki asosiy holat noto'g'ri bo'lib, hech to'xtamasa), chaqiruv steki to'lib ketadi. Bu stek to'lib ketishi (stack overflow) deyiladi va dasturni qulatadi. Shuning uchun asosiy holat to'g'ri va har doim erishiladigan bo'lishi kerak.

Matn va ikkilik fayllar

Fayllar ikki turli bo'ladi. Matn fayllar (txt) odam o'qiy oladigan harflardan iborat. Ikkilik fayllar (rasm, video, baza) esa to'g'ridan-to'g'ri baytlardan iborat va maxsus dastur orqali o'qiladi. Ikkalasi ham fopen bilan ochiladi, faqat rejim va o'qish usuli farq qiladi.

Rekursiya va fayllar bir-biriga bog'liq joyi bor: papkalar ichidagi papkalarni ko'rib chiqish uchun rekursiya juda mos. Har bir papka ichida yana papkalar bo'lishi mumkin, bu aniq rekursiv tuzilma.

Atamalar lug'ati

rekursiyafunksiyaning o'z-o'zini chaqirishi.

asosiy holatrekursiyani to'xtatuvchi shart.

chaqiruv stekifunksiya chaqiruvlari saqlanadigan stek.

fopen / fclosefaylni ochish va yopish.

fprintffaylga formatlangan matn yozadi.

fgetsfayldan bir qatorni o'qiydi.

8.11 Bilim testi

16 ta savol. Haftani yakunlash uchun kamida 11 tasiga to'g'ri javob bering.

Tabriklaymiz! 8-hafta yakunlandi

Endi siz rekursiyani va fayllar bilan ishlashni tushunasiz: asosiy holat, chaqiruv steki, hamda fayl ochish, yozish va o'qish. Faqat bitta hafta qoldi, deyarli yetib keldingiz!

Keyingi hafta: Debugging va yakuniy loyiha (xato turlari, ularni topish va loyiha qurish). Bu Foundation kursining oxirgi haftasi!

Yakuniy modulga o'tish