Tártiplew máselelerin sheshiwge rekursiv ha’m apiwayi algoritmlardan paydalaniw Joba

Rekursiv Algoritmlar ham olardin tu’rleri
Rekursiya haqqında túsinik.
Funksiya ózine ózi tuwrıdan-tuwrı yamasa qanday da qural arqalı shaqırıq qılıw procesine rekursiya dep ataladı hám bunday funksiya rekursiv funksiya dep ataladı. Gúrriń degi mısalǵa qaytatuǵın bolsaq, jerde summa () atlı funksiya nátiyjesin esaplaw ushın oǵan bir neshe ret qayta shaqırıq etiwine tuwrı keldi. Naǵız ózi zat rekursiyaning mánisin quraydı. Lekin, jaysha tariyp járdeminde tuwrı hám qátesinińz isleytuǵın rekursiv funksiya dúziw qıyın, onıń ushın rekursiv funksiyanıń tiykarǵı shártlerin jaqsı biliw kerek. Rekursiya (ulıwma ) - bul ob'ektti usı ob'ektke murojat qılıw arqalı anıqlaw bolıp tabıladı.
Kópshilik strukturalar hám algoritmlardı rekursiyasiz oyda sawlelendiriw etip bolmaydı. Tree, Graph, Heap, QuickSort, MergeSort, … Bul kesteni ap-alıs dawam ettiriw múmkin. Ásirese, quramalı strukturalar bolǵan Tree hám Graphlarda rekursiya hár qádemde ushraydı. Programmistlikti bolsa olarsız oyda sawlelendiriw etip bolmaydı, bul bolsa óz ornında rekursiya qanshellilik zárúrligini belgilep beredi.
Rekursiya funksional programmalastırıwdıń tiykarǵı elementlerinen esaplanadı. Ele funksional programmalastırıw haqqında esitmegen bolsańız ol haqqında maǵlıwmat axtarib oqıp kóriwdi máslahát beremen. Bir sóz menen aytqanda, házirde programmalastırıw tarawı jedellik menen funksional programmalastırıw paradigması tárep ketmekte (Go hám Scala jaqtı úlgiler).
Taǵı bir qızıq maǵlıwmat, sonday programmalastırıw tilleri bar olarda ulıwma tákirarlanıw operatorları joq jáne bul boyınsha pútkilley rekursiyaga tayanadi. Haskell hám Erlang usılar gápinen. Álbette, bulardıń barlıǵı rekursiyani tákirarlaw operatorlarınan pútkilley artiqmashliǵin anglatmaydi. Tiykarınan, kóbinese programmistler rekursiya isletiwden shaǵılısıwadı. Bunıń tiykarǵı sebepleri bolsa :
Rekursiv sheshimde qáte qılıw múmkinshiligı joqarı. Aldın da aytqanimizdek, rekursiya oǵırı shalǵıtuvchi. Usınıń sebepinen, onı isletiwde ańsatǵana qáte etip qoyıw múmkin. Rekursiv sheshimdi qátesinińni tabıw qıyın. Bunday máselelerde qáte etip qoyıw múmkinshiligı joqarı bolıwı menen birge onı tawıp tuwırlaw da qıyın bolıwı múmkin. Bunıń tiykarǵı sebebi, bunday sheshimlerdi oyda sawlelendiriw qılıp alıw (hayolan depug qılıw ) júdá qıyın.
Rekursiv algoritmdıń quramalılıǵın esaplaw kóbinese júdá quramalı. Hátte, geyde tuwrı sheshimdi jazıwdıń ózi de kem bolıp qalıwı múmkin. Sebebi, onı iterativ sheshim menen salıstırıwda onıń quramalılıǵın esaplaw kerek boladı. Rekursiv algoritmlarda bul kóbinese júdá quramalı hám jaqsıǵana matematika talap etedi.
Rekursiv algoritm - bul algoritmı anıqlawda ózine tikkeley yamasa tikkeley bolmaǵan murojat qılıw bolıp tabıladı.
Eger maǵlıwmatlar strukturası elementleri de usı strukturaǵa uqsas struktura bolsa, ol halda bunday strukturaǵa rekursiv maǵlıwmatlar strukturası dep ataladı.
Rekursiv funksiyalar. Funksiya denesinde ózin ózi shaqırsa rekursiv funksiya dep ataladı.
Rekursiya eki qıylı boladı :
Ápiwayı - eger funksiya óz denesinde ózin shaqırsa ;
qurallı - eger birinshi funksiya ekinshi funksiyanı shaqırsa, ekinshisi bolsa óz
gezeginde birinshi funksiyanı shaqırsa.
Ádetde rekursiya matematikada keń qollanıladı. Sebebi kópshilik matematikalıq
Formulalarzrekursiv anıqlanadı.
Rekursiv funksiya dep, ózine ózi shaqırıq etiwshi funksiyaǵa aytıladı.
Rekursiya - sonday processki, bunda processni barıwı ózine shaqırıq qılıw menen baylanıslı boladı.
Rekursiv maǵlıwmatlar strukturasına mısal etip sonday strukturalardı alıw múmkin, bul strukturalardıń elementleriniń ózi xam tap sonday struktura boladı.

Rekursiv funkciyalar. Rekursiv funkciya dep ózine ózi murojjat etiwshi funkciyaǵa aytıladı. Mısal ushın faktorialni esaplaw funkciyasın keltiremiz:

long fact (int k)
{ if (k<0) return 0;
if (k==0) return 1;
return k*fact (k-1); }
Teris argument ushın funkciya 0 baha qaytaradı. Parametr 0 ge teń bolsa funkciya 1 baha qaytaradı. Keri jaǵdayda parametr baha birge kemeytirilgen halda funkciyanıń ózi shaqırıladı hám uzatılǵan parametrge kóbeytiriledi. Funkciyanıń óz ózin shaqırıwı formal parametr ma`nisi 0 ge teń bolǵanda toqtatıladı.
Keyingi mısalımızda qálegen haqıyqıy sannıń pútkil dárejesin esaplaw rekursiv funkciyası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 funkciyaǵa expo (2. 0, 3) formada shaqırıq etilgende rekursiv túrde funkciyanıń ekinshi parametri azayǵan halda murojjatlar payda boladı :

expo (2. 0, 3), expo (2. 0, 2), expo (2. 0, 1), expo (2. 0, 0). Bul shaqırıwlarda tómendege kóbeytpe esaplanadı : 2. 0*2. 0*2. 0*1 hám kerekli nátiyje payda etinadi.

SHuni kórsetip ótiw kerek bul funkciyamızda uǵımsızlıq bar bolıp tabıladı yaǵnıy 0. 0 ga teń sannıń 0 chi dárejesi 0 ge teń boladı. Matematikalıq nuktai názerden bolsa bul halda uǵımsızlıq kelip shıǵadı. Joqarıdaǵı ápiwayı mısallarda rekursiyasiz iterativ funkciyalardan paydalanıw maqsetke muwapıq bolıp tabıladı.
Mısalı dárejeni esaplaw funkciyanı tómendegishe dúziw múmkin:
Double
expo (double a, intzn)
{ifz (n==0) return 1;
ifz (a==0. 0) zreturnz0;
intzk= (n>0)? zn:-n;
for (doublezs=1. 0, int i=0;i
ifz (n>0) zreturnzszelse return 1/s;
} <>
Rekursiyaga mısal retinde sannı qatar formasında shıǵarıw máselesin kórip shıǵamız. San nomerleri teris tártipte payda boladı. Birinshi usılda nomerlerdi dızbekte saqlap keyininen teris tártipte shıǵarıw bolıp tabıladı.
Rekursiv usılda funkciya hár bir shaqiriqda bas nomerlerden nusqa alıw ushın óz ózine shaqırıq etedi, keyininen aqırǵı nomerdi basıp chikaradi.
printd (n)
int n;
(

int i;
if (n < 0)

cout<<'-';
n = -n;
if ((i = n/10 )! = 0)
printd (i);
cout<<=" " b=" " >
)
printd (123) shaqırıwda birinshi funkciya printd N = 123 mániske iye. Ol 12 bahanı ekinshi printd ga uzatadı, basqarıw ózine qaytqanda 3 ni chikaradi.
Na'muna mısal :
#include
using namespace std;
float f1 (float z)
{ float a=3. 246 ;
cout<<" formula 1 ";
return z*z-a;
}
float f2 (float z)
{ float b= 6. 46 ;
cout<<" formula 2 ";
return z*z*z-b;
float ffor (float xn, float xk, float h)
{ float x, y;
for (x=xn;x<=xk;x+=h)
{ if (x<3. 0) y=f1 (x);else y=f2 (x);
cout<< x<<” “<< y<<" \n" ; }
return 0;
}
void fwhile (float xn, float xk, float h)
{ float x, y;
x=xn;
while (x<=xk)
{ if (x<3. 0) y=f1 (x);else y=f2 (x);
cout< <<” “<< y<<" \n" ; <=" " b=" " >
x+=h;}
} void fdo (float xn, float xk, float h)
{ float x, y;
x=xn;
do
{ if (x<3. 0) y=f1 (x);else y=f2 (x);
cout<< x<<” “<< y<<" \n" ;
x+=h;
}

while (x<=xk);

}
int main ()
<<” << y<<" \n" >
{float xn, xk, h, y;
int n;
xn=1. 7; xk=5. 3; h=0. 4;
clrscr (); puts (" vvedi--1, esli for");
puts (" vvedi--2, esli while");
puts (" vvedi--3, esli do");
cin>>n;cout<<" \n";
if (n== 1) ffor (xn, xk, h); //sikl s parametrom
if (n== 2) fwhile (xn, xk, h); //sikl s predusloviem
if (n== 3) fdo (xn, xk, h); //sikl s postusloviem
getch ();
}.
Rekursiv triada.
Rekursiya bazası (hasası ) - másele sheshimi anıq bolǵan trivial jaǵday anıqlanadı, yaǵnıy bul jaǵdayda funksiyanı ózine murojat etiwi talap etilmeydi.;
Dekompozitsiya - ulıwma jaǵdaydı salıstırǵanda talay ápiwayı bolǵan ózgergen parametrli qisim máseleler arqalı ańlatadı.
Parametrizatsiya qılıw - másele shártini klassifikaciyalaw jáne onı sheshiw ushın parametrler anıqlanadı ;
Túsindirme: Rekursiv yamasa interatsion usıl natiyjeliligi berilgen máseleni sheshiwshi programmanı túrli baslanǵısh bahalarda analiz etiw arqalı anıqlaydı.
Rekursiv algoritmlardı natiyjeliligin asırıw kóbinese triada basqıshların qayta kórip shıǵıw nátiyjesinde ámelge asırıw múmkin.
Faktorialini esaplaw :
Rekursiv triada:
Parametrizatsiya:
n - nomanfiy pútkil san.
Rekursiya bazası :
n =0 hám n =1 ushın faktorial 1 ge teń.
Dekompozitsiya:
n! = (n-1)! *n.
n! =1*2*…*n=n* (n-1)!
int i, m, N; double long fact;
void factorial (int m);
void main ()
{
clrscr ();
cin>>N;
fact=1; factorial (N);
}
void factorial (int m)

{ if (m==1)

{cout< <<"! =" <
getch ();
exit (1); }
fact*=m; factorial (m-1); }
Terek túsinigi.
Terek-bul sızıqsız baylanısqan maǵlıwmatlar.
Terek óziniń tómendegi belgileri menen klassifikaciyalanadı :
Terekte sonday bir element bar, oǵan basqa elementlerden murojat joq. Usı elementke terek túbiri dep ataladı ;
Terekte qálegen elementke chekli sandaǵı kórsetkishler járdeminde murojat qılıw mmkin;
Terektiń hár bir elementi tek ǵana ózinden aldınǵı kelgen bir element menen baylanısqan. Terektiń hár bir túyini arqalı yamasa terminal (japıraq) bolıwı múmkin.
Terek basqıshları sanına terek biyikligi dep ataladı
Shıǵıw dárejeleri :
Túyinlerden shıǵıp atırǵan shohlar sanı túyinnen shıǵıw dárejesi dep ataladı.
Tereklerdi xarakteristikalaw
Logikalıq súwretlewde terekler baylanısqan kesteler kóriniste ańlatıladı. Bunda keste elementi túyin ma`nisi hám shıǵıw dárejesin óz ishine alıwshı informatsion maydanǵa hám de shıǵıw dárejesine teń bolǵan kórsetkishler maydanına iye boladı.
Terek grafik hám sızıqsız keste formasındaǵı suwretleniwi.