Qoyilg’an ma’sele

unsigned int factorial(unsigned int n) {
if(n==0) return 1; else return n*factorial(n–1);
}
Mashqala júdá kritik kórinedi, sebebi funksiya óz-ózin shaqırıwı arqalı tuwrı nátiyjeni bere alıwın túsiniw qıyınshılıq tuwdıradı. Kóp kompyuterlerde rekursiyalar ushın steklardan paydalanıp qollanıladı, rekursiyanı ámelge asırıwdıń barlıq jumısın operatsion sistemada ámelge asırıladı, onıń ushın programma kodında birpara belgi;arni kirgiziw zárúrshiligi da

tug'ilmaydi. E. W. Dijkstra tominidan rekursiyani engiziwde steklardan paydalanıw ideyasın bergen. Rekursiyani ha'm onıń qanday islewin jaqsılaw túsiniw ushın funksiyaǵa shaqırıwlar procesin úyreniw ha'm Sistema tárepinen ámelge asırılıp atırǵan operatsiyalrni baqlaw maqul.
Funksiya shaqırıwları
Funksiyaǵa shaqırıq etilgende ne júz boladı? Funksiya formal parametrlerge iye bolsa, ámeldegi aktual parametrler qimatlariga ózgertiliwi kerek. Bunnan taashqari, sistema programma juwmaqlawshı exe atqarılıwın qay jerge saqlap dawam ettiriwi kerekligin biliwi kerek. Funksiyalar basqa at menen, yamasa tiykarg'i programma (the function main ()) menen da shaqırılıwı múmkin. Funksiyanı qay jerden shaqırıp alıw, sistema tárepinen saqlap qolinshi kerek boladı. Bul qaytıw adreslerin tiykarg'i yadta saqlap barıw arqalı ámelge asırılıwı múmkin, lekin bizge qansha jay kerekligi belgisiz bolsa, onıń ushın kóp awısıq jay ajıratıp ketiw yaramaydi. Funksiyaǵa shaqırıwlarda bolsa adres qaytarıwǵa qaraǵanda kóbirek maǵlıwmatlar saqlap qalınıwi kerek. Sol sebepli, steklardan paydalanıp dinamikalıq jaylastırıw jaqsı nátiyjelerge alıp keledi.
Mudamıǵı esitip charchagan ha'm derlik hesh nárse tushunmagan tariypingiz… Sebebi bul jaysha ilimiy tariyp odan tezde neni bolıp tabıladı túsiniw ańsat emes. Bunıń ústine birpara máselelerde rekursiv usıldı, iterativ usıl menen salıstırıw qıyınshılıq tuwdıradı. Sol sebepli rekursiyani ápiwayılaw túsintiremiz ha'm onı iterativ usıl menen salıwtirib kóremiz
Kishi gúrriń…
Oyda sawlelendiriw etiń siz qulflangan bólme ishindesiz ha'm sizde ishinde gilti bar qutı bar. Lekin, qutini ishin ochsangiz onıń ishinde bir neshe kishilew qutilar shıqtı. Giltni tabıw ushın keyingi qádemińiz qanday bo'lar edi?
1-usıl: (Iterativ usıl)
1. Hámme qutilarni qatar etip qoyıp alamız
2. Qatarımizda qutı qolmagunicha tómendegi jumıslardı etemiz
3. Qatardaǵı birinshi qutini alamız
4. Eger onıń ishinen taǵı qutı chiqsa onı qatar aqırıǵa qosamız.
5. Eger gilt chiqsa ishimiz juwmaqlanadı
6. 2-qádemge qaytamız
2-usıl: (Rekursiv usıl)
1. Qutı ishindegi hámme zattı kórip boramiz
2. Eger gilt chiqsa, ishimiz juwmaqlanadı
3. Eger qutı chiqsa sol qutı ushın 1-qádemge qaytamız
4. Qutı ishinde hesh nárse qolmasa bir aldınǵı qutida qalǵan jayimizda dawam etemiz.
Qaysı usıl ápiwayılaw tuyilyapti? Eki usılda da biz aqırıda óz maqsetimizga erisemiz, yaǵnıy giltni tabamız. Rekursiv usıl bizge tezlikten jutıwǵa járdem bermiydi kerisinshe geyde rekursiv usıl iterativ usıldan kóre ástelew islewi múmkin. Lekin rekursiya másele sheshimin ápiwayılaw bólimlerge ajıratıp sheshiwge múmkinshilik beredi.
Eger siz ele da rekursiya nimaligini túsiniwge qiynalayotgan bolsańız ha'm tepadagi túsindiriwdi oqıwǵa erinseńiz rekursiyani eki awız gáp menen túsindiriwge háreket etemiz.
Eger rekursiyani 5 yoshli balaǵa túsindiriw kerek bolǵanda…
Oyda sawlelendiriw etiń eger sizdan rekursiyani túsindiriw talap etilse ne etken bo'lardingiz. Mende tómendegishe usınıs bar:
Rekursiya nimaligini ózińizden bir jas kishi adamǵa túsintirasiz ha'm ol da sol jumıstı etiwi kerekligin aytasiz. Bul zattı tokı 6 yoshli bala 5 yoshli balaǵa rekursiya nimaligini túsintirip berguncha dawam ettirasiz.) (Derek: reddit)
Tepadagi jaǵdaydaǵı rekursiyani sezim qilyapsizmi..? Úmit etemenki rekursiya qanday islewi sal oydinlashdi. Endi rekursiyaga sal ilimiylew tárepden yondashamiz.
Rekursiya qanday isleydi ha'm qaysı jaǵdaylarda qollanıladı
Rekursiyani qóllawda tiykarg'i ekew qaǵıyda bar:
1. Máseleni rekursiv sheship bolıwı ushın onı kishi bólimlerge bolǵanda hámme bólim ushın da ulıwma sheshim tuwrı islewi kerek.
2. Hámme rekursiv sheshimde toqtap qalıw noqatını kórsetiwshi tiykarg'i shárt (base case) bolıwı shárt.
Mashina (kompyuter) rekursiv máseleni sheshiw processinde Stack dep atalıwshı estelik maydanın isletedi. Bunda
aqırıǵa yetmay qalǵan sheshimler (joqarıdaǵı mısalda oxirgacha kórip shıǵıp ulgurilmagan qutilar) sol stackda saqlanıp turıladı.
Mısalı, kópshilik biletuǵın faktorialni tabıwdaǵı rekursiv usıl tómendegishe isleydi:
Aldın funksiya tiykarg'i shártga jetip borgunicha stackda barlıq shaqırılǵan funksiyalardı saqlap turadı. Keyin bolsa stackdan arttan aldınǵa qaray bul sheshimlerdi shıǵarıp aladı ha'm aqırıda nátiyje shıǵadı.
Bilgenimizdey, kompyuter yadı shegaralanǵan, sol sebepli ol hár bir programma ushın shegaralanǵan jay ajratadı. Usınıń sebepinen biziń stackimiz da shegaralanǵan boladı.
Eger biz tiykarg'i shártni qáte qoyǵan bolsaq, rekursiv usıl hesh qashan sheshim aqırıına shekem bora almaydı ha'm nátiyjede stack to'lib, tamaqtasıb ketedi ha'm bul jaǵday StackOverflow dep ataladı.
Endi sol programmashılar arasındaǵı eń belgili forum atı qay jerden alınǵanın sezgan bolsańız kerek.)
Rekursiv usıldı iterativ usıldan kemshilikleri
Rekursiv usıl joqarıdaǵı aytilgan yad stackidan paydalanǵanı ushın iterativ usıldan kóre yaddan kóp jay aladı. Bunıń ústine kópshilik rekursiv usılda sheshilgen máselelerdi islew quramalılıǵın esaplaw júdá quramalı bolıp ketedi.
Rekursiv usıldı iterativ usıldan avfzalliklari
Hár qanday rekursiv sheshimdi iterativ usılǵa ótkeriw múmkin ha'm hákis jaǵday da tuwrı esaplanadı. Lekin, birpara programmalastırıw máseleleri ushın iterativ sheshim júdá quramalı kóriniske kelip qaladı, biraq rekursiv usıl talay ápiwayı bolıwı múmkin (Tap joqarıdaǵı mısalǵa qusap). Mısalı, quramalı maǵlıwmatlar strukturaları (terekler, graflar) ústindegi ámellerde rekursiya júdá qol keledi. Bunday jaǵdaylarda rekursiyani qóllaw usınıs etiledi.
Bul darsimiz oǵırı sozılıp ketpewi ushın bul temaǵa ha'm oǵan tiyisli mısallarǵa keyingi sabaqlarimizda taǵı qaytamız.
Rekursiv funktsiyalar. Rekursiv funktsiya dep ózine uzi murojjat etiwshi funktsiyaǵa aytıladı. Mısal ushın faktorialni esaplaw funktsiyasın
keltiremiz:
Long fact (int k)
{if (k<0) return 0;
if (k==0) return 1;
return k*fact (k-1);
}
Keri argument ushın funktsiya 0 baha qaytaradı. Parametr 0 ga teń bolsa funktsiya 1 baha qaytaradı. Bolmasa parametr baha birge
kemeytirilgen halda funktsiyanıń ózi shaqırıladı ha'm uzatilgan parametrge kóbeytiriledi. Funktsiyanıń uz uzini shaqırıw formal parametr ma`nisi
0 ga teń bolǵanda tuhtatiladi. Keyingi mısalimizda ihtiyoriy haqıyqıy sannıń pútkil dárejesin esaplaw rekursiv funktsiyasın keltiremiz.
Double expo (double a, int n)
{ if (n==0) return 1;
if (a==0. 0) return 0;
if (n>0) return a*expo (a, n-1);
if (n<0) return expo (a, n+1) /a;
}
Mısal ushın funktsiyaǵa expo (2. 0, 3) formada shaqırıq etilgende rekursiv túrde funktsiyanıń ekinshi parametri azayǵan halda murojjatlar
ónim boladı:
Expo (2. 0, 3), expo (2. 0, 2), expo (2. 0, 1), expo (2. 0, 0). Bul shaqırıwlarda tómendege kupaytma esaplanadı: 2. 0*2. 0*2. 0*1 ha'm kerekli nátiyje ónim
etiledi.
Sonı kursatib ótiw kerek bul funktsiyamizda uǵımsızlıq mavjud bolıp tabıladı yaǵnıy 0. 0 ga teń sannıń 0 chi dárejesi 0 ga teń boladı. Matematikalıq noqatı
názerden bolsa bul halda uǵımsızlıq kelip shıǵadı. Joqarıdaǵı ápiwayı mısallarda rekursiyasiz iterativ funktsiyalardan paydalanıw maqsetke
muwapıq bolıp tabıladı.
Mısalı dárejeni esaplaw funktsiyanı tómendegishe dúziw múmkin:
Double expo (double a, int n)
{ if (n==0) return 1;
if (a==0. 0) return 0;
int k= (n>0)? n:-n;
for (double s=1. 0, int i=0;iif (n>0) return s else return 1/s;
}
Rekursiyaga mısal sıpatında sannı qatar formasında shıǵarıw máselesin kórip shıǵamız. San nomerleri teris tártipte ónim boladı. Birinshi usılda
nomerlerdi dızbekde saqlap keyininen teris tártipte shıǵarıw bolıp tabıladı.
Rekursiv usılda funktsiya hár bir shaqiriqda bas nomerlerden nusha olsih ushın óz ózine shaqırıq etedi, keyininen ohirgi rakamni basıp
shıǵaradı.
printd(n) /* print n in decimal (recursive)*/
int n;
(
int i;
if (n < 0)
putchar('-');
n = -n;
if ((i = n/10) != 0)
printd(i);
putchar(n % 10 + '0');
)
PRINTD(123) shaqirig’inda birinshi funkciya PRINTD N = 123 ma’niske iye. Ol 12 ma’nisin ekinshi PRINTD g’a uzatadi, basqariw o‘zina
qaytqanda 3 ti shig’aradi.