The stack

Ushbu bo'lim qo'ng'iroqlar to'plamini qamrab oladi. Bu dasturlashda muhim tushuncha. Qo'ng'iroqlar to'plami umumiy dasturlashda muhim tushunchadir va uni rekursiyadan foydalanganda tushunish ham muhimdir.

Aytaylik, siz barbekyu tashlayapsiz. Siz barbekyu uchun qilinadigan ishlar ro'yxatini yopishqoq yozuvlar to'plami shaklida saqlaysiz.

Barbecue

Esingizdami, biz massivlar va ro'yxatlar haqida gaplashganimizda va sizda vazifalar ro'yxati bor edi? Roʻyxatning istalgan joyiga vazifalarni qoʻshishingiz yoki tasodifiy elementlarni oʻchirishingiz mumkin. Yopishqoq qog'ozlar to'plami ancha sodda. Elementni qo'shganingizda, u ro'yxatning yuqori qismiga qo'shiladi. Biror narsani o'qiyotganingizda, siz faqat eng yuqori elementni o'qiysiz va u ro'yxatdan o'chiriladi. Shunday qilib, sizning vazifalar ro'yxati faqat ikkita amaldan iborat: surish (qo'shish) va pop (o'chirish va o'qish).

push and pop

Keling, bajariladigan ishlar ro'yxatini amalda ko'rib chiqaylik

TODO

Ushbu ma'lumotlar strukturasi stek deb ataladi. Stack oddiy ma'lumotlar strukturasidir. Siz o'zingiz bilmagan holda butun vaqt davomida stekdan foydalandingiz!

The call stack

Sizning kompyuteringiz qo'ng'iroqlar to'plami deb ataladigan ichki stekdan foydalanadi. Keling, buni amalda ko'rib chiqaylik. Mana oddiy funksiya:

greet()

Python

def greet(name):
    print "hello, " + name + "!"
    greet2(name)
    print "getting ready to say bye..."
    bye()

Golang

func greet(name string) {
    fmt.Println("hello, " + name + "!")
    greet2(name)
    fmt.Println("getting ready to say bye...")
    bye()
}

Bu funksiya sizni kutib oladi va keyin yana ikkita funksiyani chaqiradi. Mana bu ikkita funktsiya:

Two function

Python

def greet2(name):
    print "how are you, " + name + "?"

def bye():
    print "ok bye!

Golang

func greet2(name string) {
    fmt.Println("how are you, " + name + "?")
}

func bye() {
    fmt.Println("ok bye!")
}

print Python-da funksiyadir, ammo bu misol uchun ishlarni osonlashtirish uchun biz bunday emas deb o'ylaymiz. Faqat birga o'ynang.

Funktsiyani chaqirganingizda nima sodir bo'lishini ko'rib chiqaylik

Aytaylik, siz print("maggie") deb chaqirasiz. Birinchidan, kompyuteringiz ushbu funktsiya chaqiruvi uchun xotira qutisini ajratadi.

box of memory

Endi xotiradan foydalanamiz. O'zgaruvchining nomi "maggie" ga o'rnatiladi. Bu xotirada saqlanishi kerak

variable

Har safar funktsiya chaqiruvi qilganingizda, kompyuteringiz ushbu qo'ng'iroq uchun barcha o'zgaruvchilar uchun qiymatlarni shunday xotirada saqlaydi. Keyin, hello, maggie!, chop etasiz! Keyin siz greet2("maggie") ga qo'ng'iroq qilasiz. Shunga qaramay, sizning kompyuteringiz ushbu funktsiya chaqiruvi uchun xotira qutisini ajratadi.

two variables

Sizning kompyuteringiz ushbu qutilar uchun stekdan foydalanmoqda. Ikkinchi quti birinchisining ustiga qo'shiladi. Siz chop etasizmi, how are you, maggie? Keyin siz funktsiya chaqiruvidan qaytasiz. Bu sodir bo'lganda, stek ustidagi quti chiqib ketadi.

pop stack

Endi stekdagi eng yuqori quti greet funksiyasi uchun, ya'ni siz greet funksiyasiga qaytdingiz. greet2 funksiyasini chaqirganingizda greet funksiyasi qisman bajarildi. Bu bo'lim ortidagi katta g'oya: funksiyani boshqa funksiyadan chaqirganingizda, chaqiruvchi funksiya qisman tugallangan holatda to'xtatiladi. Ushbu funktsiya uchun o'zgaruvchilarning barcha qiymatlari hali ham xotirada saqlanadi. Endi greet2 funksiyasi bilan ishlashni tugatganingizdan so'ng, greet funksiyasiga qaytdingiz va to'xtagan joydan davom etasiz. Avval getting ready to say bye…. chop etiladi. Siz bye funksiyasini chaqirasiz.

bye() function

Ushbu funktsiya uchun quti stekning yuqori qismiga qo'shiladi. Keyin ok bye chop etiladi va funktsiya chaqiruvidan qaytish.

call bye() function

Va siz greet funksiyasiga qaytdingiz. Boshqa hech narsa qilish shart emas, shuning uchun siz greet funksiyasidan ham qaytasiz. Bir nechta funksiyalar uchun o'zgaruvchilarni saqlash uchun foydalaniladigan bu stek chaqiruv stegi deb ataladi.

EXERCISE

3.1 Aytaylik, men sizga shunday qo'ng'iroqlar to'plamini ko'rsataman

exercise 3.1

Ushbu qo'ng'iroqlar to'plamiga asoslanib, menga qanday ma'lumot bera olasiz? Keling, qo'ng'iroqlar to'plamini rekursiv funksiya bilan ishlayotganini ko'rib chiqaylik.

The call stack with recursion

Rekursiv funktsiyalar qo'ng'iroqlar to'plamidan ham foydalanadi! Keling, buni faktorial funksiya bilan amalda ko'rib chiqaylik. faktorial(5) 5! sifatida yoziladi va u quyidagicha aniqlanadi: 5! = 5 * 4 * 3 * 2 * 1. Xuddi shunday, faktorial(3) 3 * 2 * 1 ga teng. Mana, sonning faktorialini hisoblash uchun rekursiv funksiya:

Python

def fact(x):
    if x == 1:
        return 1
    else 
        return x * fact(x-1)    

Golang

func fact(x int) int {
    if x == 1 {
        return 1
    } else {
        return x * fact(x-1)
    }
}

Endi siz fakt(3) ni chaqirasiz. Keling, ushbu qo'ng'iroqni satr bo'ylab ko'rib chiqamiz va stek qanday o'zgarganini ko'ramiz. Esingizda bo'lsin, stekdagi eng yuqori quti sizga hozirda qaysi factni chaqirayotganingizni ko'rsatadi.

fact(x)

fact(x)

E'tibor bering, har bir factga qo'ng'iroq o'zining x nusxasiga ega. Siz boshqa funksiyaning x nusxasiga kira olmaysiz. Rekursiyada stek katta rol o'ynaydi. Ochilish misolida kalitni topish uchun ikkita yondashuv mavjud edi. Mana yana birinchi yo'l.

recursion

Shunday qilib, siz qidirish uchun qutilar to'plamini yaratasiz, shuning uchun siz har doim qanday qutilarni qidirishingiz kerakligini bilasiz.

file of boxes

Ammo rekursiv yondashuvda hech qanday qoziq yo'q.

recursion

Agar qoziq bo'lmasa, sizning algoritmingiz qanday qutilarni ko'rib chiqishingiz kerakligini qanday biladi? Mana bir misol:

checking boxes

Ushbu nuqtada qo'ng'iroqlar to'plami shunday ko'rinadi.

calls

"Qutilar uyumi" stekda saqlanadi! Bu yarim tugallangan funksiya qo'ng'iroqlari to'plami bo'lib, ularning har biri ko'rib chiqilishi kerak bo'lgan o'zining yarim to'liq ro'yxatiga ega. Stackdan foydalanish qulay, chunki siz o'zingiz qutilar to'plamini kuzatib borishingiz shart emas - stek buni siz uchun qiladi.

Stackdan foydalanish qulay, ammo xarajati bor: barcha ma'lumotlarni saqlash juda ko'p xotirani egallashi mumkin. Ushbu funktsiya chaqiruvlarining har biri biroz xotirani egallaydi va sizning stekingiz juda baland bo'lsa, bu sizning kompyuteringiz ko'plab funktsiya chaqiruvlari uchun ma'lumotni saqlayotganini anglatadi. Bu vaqtda sizda ikkita variant bor:

• Buning o'rniga loopdan foydalanish uchun kodingizni qayta yozishingiz mumkin.

• Siz quyruq rekursiyasi deb ataladigan narsadan foydalanishingiz mumkin. Bu ilg'or rekursiya mavzusi bo'lib, bu kitobning doirasiga kirmaydi. Bundan tashqari, hamma emas, faqat ba'zi tillar tomonidan qo'llab-quvvatlanadi.

EXERCISE

3.2 Faraz qilaylik, siz tasodifan abadiy ishlaydigan rekursiv funktsiyani yozdingiz. Ko'rib turganingizdek, kompyuteringiz har bir funktsiya chaqiruvi uchun stekga xotira ajratadi. Sizning rekursiv funktsiyangiz abadiy ishlaganda stek bilan nima sodir bo'ladi?