9-mavzu. Chiziqsiz ma’lumotlar tuzilmasi. Daraxtsimon maʻlumotlar tuzilmalari. Binar va ko‘ptarmoqli daraxtlar. Taʻriflar va xususiyatlar. Daraxtlarni binar ko‘rinishga keltirish algoritmi. Rekursiya va ularni dasturlashda ishlatish

Rekusiv murojaat anatomiyasi

Ixtiyoriy o’suvchi x ning manfiy bo’lmagan butun n-darajasini aniqlovchi funksiya rekursiv funksiyaga misol bo’ladi. Uni aniqlovchi funksiya quyidagicha:

X ning n-darajasini hisoblovchi funksiya C++da quyidagi pow orqali to’g’ridan – to’g’ri hisoblanishi mumkin:

Bundan foydalanib, xning 4-darajasining qiymati quyidagicha yo’nalishda hisoblanishi mumkin:

Bunday ketma-ketlik rekursiv murojaatlar zanjirining so’nggi bosqichiga, ya’ni ildiziga olib boradi. Ildiz natijaga daraja 0 bo’lganda 1 qiymatni beradi; natija undan oldingi murojaatlarga o’tqaziladi. Ijrosi amalga oshayotgan murojaat x*1=x degan natija beradi. Keyin, bu raqam ikkinchi murojaaat uchun x*x orqali shunaqa natijani qaytaradi. So’ng, x * x * x natijasiga olib keladi.

call 1 x 4 = x · x 3       = x · x · x · x

call 2       x · x 2     = x · x · x

call 3         x · x 1   = x · x

call 4           x · x 0 = x · 1 = x

call 5             1or alternatively, as

call 1 power(x,4)

call 2       power(x,3)

call 3             power(x,2)

call 4                   power(x,1)

call 5                         power(x,0)

call 5                         1

call 4                   x

call 3             x · x

call 2       x · x · x

call 1 x · x · x · x

Funksiyalar ijrosi amalga oshayotganda sitema nima ish bajaradi? Barchamizga ma’lumki, Sistema amalga oshirish vaqti stekida barcha murojaatlar izlarini saqlab turadi.Funksiya ijrosidan so’ng ijro exe si qayerda saqlanganligini bilish uchun zarur. Buning uchun misol qilib , 102 yoki 105 raqamalari kiritilgandagi power() funksiyasi bir chiziqda yoadigan bo’lsin.

Rekursiv murojaatlar izi bu diagrammada ko’rsatilganidek oddiy.

call 1 power(5.6,2)

call 2       power(5.6,1)

call 3             power(5.6,0)

call 3             1

call 2       5.6

call 1 31.36

Chunki, ko’pgina operatsiyalar amalga oshirish vaqti stekida amalga oshirilgan. Funksiya 1 – marotaba ishga tushirilganda, 4 ta belgi amalga oshirish vaqti stekida suriladi: qaytuvchi adres 136, aktual parametrlar 5.6 va 2, va 1 ta power() orqali qaytarilgan qiymat uchun joyni aniqlovchi ishga tushadi. 5.2a chizma shu holatni namoyon etadi. (shunda va boshqa diagrammalarda, SP - stack pointer, AR - activation record, va so’roq belgilari qaytarilgan qiymatlar joyini aniqlahga xizmat qiladi. ) Hozir power() (daraja()) funksiyasi amalga oshirilgan.