Rekursioni në logjikë. Rekursioni dhe laku i bishtit

30.07.2019 Hekuri

Rekursioni është vetia e një objekti për të imituar vetveten. Një objekt është rekurziv nëse pjesët e tij duken të njëjta si i gjithë objekti. Rekursioni përdoret gjerësisht në matematikë dhe programim:

strukturat e të dhënave:
- një grafik (në veçanti pemët dhe listat) mund të shihet si një koleksion i një nyje të vetme dhe një nëngrafi (një graf më i vogël);
- një varg përbëhet nga karakteri i parë dhe një nënvarg (varg më i vogël);
modelet e projektimit, për shembull. Një objekt dekorues mund të përfshijë objekte të tjera që janë gjithashtu dekorues. McColm Smith studioi në detaje modelet rekursive, duke theksuar në librin e tij modelin e përgjithshëm të dizajnit - Rekursion;
funksionet rekurzive (algoritmet) e quajnë veten.

Artikulli i kushtohet analizës së kompleksitetit të algoritmeve rekursive, jepet informacioni i nevojshëm matematikor, shqyrtohen shembuj. Përveç kësaj, përshkruhet mundësia e zëvendësimit të rekursionit me një lak, rekursioni i bishtit.

Shembuj të algoritmeve rekurzive

Algoritmi rekurziv gjithmonë e ndan problemin në pjesë, të cilat në strukturën e tyre janë të njëjta me problemin origjinal, por më të thjeshta. Për të zgjidhur nëndetyrat, funksioni thirret në mënyrë rekursive dhe rezultatet e tyre kombinohen disi. Ndarja e problemit ndodh vetëm kur ai nuk mund të zgjidhet menjëherë (është shumë i ndërlikuar).

Për shembull, detyra e përpunimit të një grupi shpesh mund të reduktohet në përpunimin e pjesëve të tij. Ndarja në pjesë kryhet derisa ato të bëhen elementare, d.m.th. mjaft e thjeshtë për të marrë rezultatin pa thjeshtim të mëtejshëm.

Gjetja e një elementi vargu

Fillimi; kërkimi (vargu, fillimi, fundi, elementi); kërkimet për një element me një vlerë të elementit në grup midis indekseve fillojnë dhe mbarojnë nëse fillimi> rezultati përfundimtar: = false; elementi nuk gjendet ndryshe nëse vargu = rezultati i elementit: = i vërtetë; elementi i gjetur ndryshe rezultat: = kërkimi (array, fill + 1, fund, element) fund; ktheni rezultatin

Algoritmi e ndan grupin origjinal në dy pjesë - elementin e parë dhe një grup elementësh të tjerë. Ka dy raste të thjeshta ku nuk kërkohet ndarja - të gjithë elementët janë përpunuar ose elementi i parë është ai i dëshiruar.

Në algoritmin e kërkimit, do të ishte e mundur të ndahej grupi në një mënyrë tjetër (për shembull, në gjysmë), por kjo nuk do të ndikonte në efikasitetin. Nëse grupi është i renditur, atëherë këshillohet ndarja e tij në gjysmë, pasi në çdo hap, sasia e të dhënave të përpunuara mund të zvogëlohet përgjysmë.

Kërkimi binar në një grup

Kërkimi binar kryhet mbi një grup të renditur. Në çdo hap, elementi i kërkuar krahasohet me vlerën në mes të grupit. Në varësi të rezultateve të krahasimit, ose ana e majtë ose e djathtë mund të "fshihet".

Fillimi; binary_search (arreti, fillimi, fundi, elementi); kërkon një element me vlerë elementi; në një grup vargu në rritje; midis indekseve fillojne dhe mbarojne if fill> end end; ktheje false - nuk u gjet asnjë element në mes: = (fund + fillim) div 2; llogaritja e indeksit të elementit në mes të pjesës së konsideruar të grupit nëse vargu = fundi i elementit; kthen true (elementin e gjetur) nëse vargu< element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Llogaritja e numrave Fibonacci

Numrat e Fibonaçit përcaktohen nga një shprehje rekursive, d.m.th. të tillë që llogaritja e elementit të të cilit shprehet nga elementët e mëparshëm: \ (F_0 = 0, F_1 = 1, F_n = F_ (n-1) + F_ (n-2), n> 2 \).

Fillimi; fibonacci (numër) nëse numri = 0 fundi; ktheni 0 nëse numri = 1 fund; kthej 1 fib_1: = fibonacci (numri-1) fib_2: = fibonacci (numri-2) rezultat: = fib_1 + fib_2 fund; ktheni rezultatin

Renditja e shpejtë

Algoritmi i renditjes së shpejtë në çdo hap zgjedh një nga elementët (pivot) dhe, në lidhje me të, e ndan grupin në dy pjesë, të cilat përpunohen në mënyrë rekursive. Në njërën pjesë vendosen elementë më të vegjël se boshti, kurse pjesa tjetër në tjetrën.

Tabela e rrjedhës së algoritmit të renditjes së shpejtë

Merge sort

Algoritmi i renditjes së bashkimit bazohet në aftësinë për të kombinuar shpejt vargje (ose lista) të renditura në mënyrë që rezultati të renditet. Algoritmi ndan grupin origjinal në dy raste rastësisht (zakonisht në gjysmë), i rendit ato në mënyrë rekursive dhe bashkon rezultatin. Ndarja ndodh për sa kohë që madhësia e grupit është më e madhe se një, pasi një grup bosh dhe një grup i një elementi janë gjithmonë të renditura.

Diagrami i bllokut të renditjes së bashkimit

Në çdo hap të bashkimit, artikulli i parë i papërpunuar zgjidhet nga të dyja listat. Artikujt krahasohen, më i vogli prej tyre i shtohet rezultatit dhe shënohet si i përpunuar. Bashkimi ndodh derisa njëra nga listat të jetë bosh.

Fillimi; bashkimi (Array1, Size1, Array2, Size2); vargjet origjinale janë të renditura; rezultati është një grup i renditur me gjatësi Size1 + Size2 i: = 0, j: = 0 cikli_i përjetshëm nëse i> = Size1 shtoj elemente nga j në Size2 të grupit Array2 në fund të rezultatit del nga cikli nëse j> = Size2 shtoni elemente nga i në Size1 të grupit Array1 në fund të rezultatit; dilni nga cikli nëse Array1 [i]< Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Array2 [j]) rezultat: = Vargu2 [j] j: = j + 1 fund; ktheni rezultatin

Analiza e algoritmeve rekursive

Kur llogaritet kompleksiteti i përsëritjeve dhe numri i tyre në rastet më të këqija, më të mira dhe mesatare. Megjithatë, ju nuk do të jeni në gjendje ta aplikoni këtë qasje për një funksion rekurziv, pasi Rezultati do të jetë një lidhje përsëritëse. Për shembull, që një funksion të gjejë një element në një grup:

$
\ fillojë (ekuacioni *)
T ^ (kërkim) _n = \ fillojë (rastet)
\ mathcal (O) (1) \ katër dhe \ tekst ($ n = 0 $) \\
\ mathcal (O) (1) + \ mathcal (O) (T ^ (kërkim) _ (n-1)) \ katër & \ tekst ($ n> 0 $)
\ fundi (rastet)
\ fundi (ekuacioni *)
$

Marrëdhëniet e përsëritura nuk na lejojnë të vlerësojmë kompleksitetin - ne thjesht nuk mund t'i krahasojmë ato, dhe për këtë arsye të krahasojmë efikasitetin e algoritmeve përkatëse. Është e nevojshme të merret një formulë që do të përshkruajë lidhjen e përsëritjes - një mënyrë universale për ta bërë këtë është të zgjidhni një formulë duke përdorur metodën e zëvendësimit dhe më pas të provoni korrespondencën e formulës me relacionin me metodën e induksionit matematik.

Metoda e zëvendësimit (përsëritjes).

Ai konsiston në zëvendësimin vijues të pjesës së përsëritur në shprehje për të marrë shprehje të reja. Zëvendësimi kryhet derisa të jetë e mundur të kapet parimi i përgjithshëm dhe të shprehet në formën e një formule jo-përsëritëse. Për shembull, për të gjetur një element në një grup:

$
T ^ (kërkim) _n = \ mathcal (O) (1) + \ mathcal (O) (T ^ (kërkim) _ (n-1)) =
2 \ herë \ mathcal (O) (1) + \ mathcal (O) (T ^ (kërkim) _ (n-2)) =
3 \ herë \ mathcal (O) (1) + \ mathcal (O) (T ^ (kërkim) _ (n-3))
$

Mund të supozojmë se \ (T ^ (kërkim) _n = T ^ (kërkim) _ (nk) + k \ herë \ mathcal (O) (1) \), por pastaj \ (T ^ (kërkim) _n = T ^ (kërko) _ (0) + n \ herë \ mathcal (O) (1) = \ mathcal (O) (n) \).

Ne kemi nxjerrë formulën, por hapi i parë përmban një supozim, d.m.th. nuk ka asnjë provë të korrespondencës së formulës me shprehjen e përsëritur - metoda e induksionit matematik lejon marrjen e provës.

Metoda e induksionit matematik

Ju lejon të vërtetoni vërtetësinë e disa pohimeve (\ (P_n \)), që përbëhet nga dy hapa:

vërtetimi i deklaratës për një ose disa raste të veçanta \ (P_0, P_1, ... \);
vërtetimi i \ (P_ (n + 1) \) rrjedh nga e vërteta e \ (P_n \) (hipoteza induktive) dhe raste të veçanta.

Le të vërtetojmë saktësinë e supozimit të bërë kur vlerësojmë kompleksitetin e funksionit të kërkimit (\ (T ^ (kërkim) _n = (n + 1) \ herë \ mathcal (O) (1) \)):

\ (T ^ (kërkim) _ (1) = 2 \ herë \ mathcal (O) (1) \) është e vërtetë nga kushti (mund të zëvendësohet në formulën origjinale rekursive);
le të themi të vërtetë \ (T ^ (kërko) _n = (n + 1) \ herë \ matematikore (O) (1) \);
kërkohet të vërtetohet se \ (T ^ (kërkim) _ (n + 1) = ((n + 1) +1) \ herë \ mathcal (O) (1) = (n + 2) \ herë \ mathcal ( O) (një)\);
1. zëvendësoni \ (n + 1 \) në relacionin e përsëritjes: \ (T ^ (kërkim) _ (n + 1) = \ mathcal (O) (1) + T ^ (kërkim) _n \);
2. në anën e djathtë të shprehjes, është e mundur të bëhet një zëvendësim bazuar në hipotezën induktive: \ (T ^ (kërkim) _ (n + 1) = \ mathcal (O) (1) + (n + 1) \ herë \ mathcal (O) (1) = (n + 2) \ herë \ mathcal (O) (1) \);
3. vërtetohet deklarata.

Shpesh, një provë e tillë është një proces mjaft i mundimshëm, por është edhe më e vështirë të identifikosh një model duke përdorur metodën e zëvendësimit. Në këtë drejtim, përdoret e ashtuquajtura metodë e përgjithshme.

Metoda e përgjithshme (kryesore) për zgjidhjen e marrëdhënieve të përsëritjes

Metoda e përgjithshme nuk është universale; për shembull, nuk mund të përdoret për të vlerësuar kompleksitetin e algoritmit të mësipërm për llogaritjen e numrave Fibonacci. Megjithatë, ai është i zbatueshëm për të gjitha rastet e përdorimit përça dhe sundo:

\ (T_n = a \ cdot T (\ frac (n) (b)) + f_n; a, b = konst, a \ geq 1, b> 1, f_n> 0, \ përgjithmonë n \).

Ekuacionet e këtij lloji fitohen nëse problemi origjinal ndahet në një nëndetyrë, secila prej të cilave përpunon elementet \ (\ frac (n) (b) \). \ (f_n \) - kompleksiteti i operacioneve të ndarjes së problemit në pjesë dhe kombinimit të zgjidhjeve. Përveç llojit të relacionit, metoda e përgjithshme vendos kufizime në funksionin \ (f_n \), duke dalluar tre raste:

\ (\ ekziston \ varepsilon> 0: f_n = \ mathcal (O) (n ^ (\ log_b a - \ varepsilon)) \ Shigjeta djathtas T_n = \ Theta (n ^ (\ log_b a)) \);
\ (f_n = \ Theta (n ^ (\ log_b a)) \ Shigjeta djathtas T_n = \ Theta (n ^ (\ log_b a) \ cdot \ log n) \);
\ (\ ekziston \ varepsilon> 0, c< 1: f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)\).

Korrektësia e pohimeve për çdo rast vërtetohet zyrtarisht. Problemi i analizës së algoritmit rekurziv tani është reduktuar në përcaktimin e rastit të teoremës kryesore, e cila korrespondon me relacionin e përsëritjes.

Analiza e Algoritmit të Kërkimit Binar

Algoritmi i ndan të dhënat origjinale në 2 pjesë (b = 2), por përpunon vetëm njërën prej tyre (a = 1), \ (f_n = 1 \). \ (n ^ (\ log_b a) = n ^ (\ log_2 1) = n ^ 0 = 1 \). Funksioni i ndarjes së problemit dhe i kompozimit të rezultatit rritet me të njëjtin ritëm si \ (n ^ (\ log_b a) \), kështu që është e nevojshme të përdoret rasti i dytë i teoremës:

\ (T ^ (binarySearch) _n = \ Theta (n ^ (\ log_b a) \ cdot \ log n) = \ Theta (1 \ cdot \ log n) = \ Theta (\ log n) \).

Analiza e algoritmit të kërkimit

Funksioni rekurziv e ndan problemin origjinal në një nëndetyrë (a = 1), të dhënat ndahen në një pjesë (b = 1). Ne nuk mund të përdorim teoremën kryesore për të analizuar këtë algoritëm, sepse kushti \ (b> 1 \) nuk plotësohet.

Për të kryer analizën, mund të përdoret metoda e zëvendësimit ose arsyetimi i mëposhtëm: çdo thirrje rekursive zvogëlon dimensionin e të dhënave hyrëse me një, kështu që do të ketë n në total, secila prej të cilave ka kompleksitet \ (\ mathcal (O) (1) \). Pastaj \ (T ^ (kërko) _n = n \ cdot \ mathcal (O) (1) = \ mathcal (O) (n) \).

Analiza e Algoritmit Merge Sort

Të dhënat origjinale ndahen në dy pjesë, të dyja përpunohen: \ (a = 2, b = 2, n ^ (\ log_b a) = n \).

Kur përpunohet një listë, ndarja mund të kërkojë kryerjen e operacioneve \ (\ Theta (n) \) dhe për një grup, ai kryhet në kohë konstante (\ (\ Theta (1) \)). Megjithatë, do të duhet \ (\ Theta (n) \) për t'u bashkuar me rezultatet gjithsesi, kështu që \ (f_n = n \).

Përdoret rasti i dytë i teoremës: \ (T ^ (mergeSort) _n = \ Theta (n ^ (\ log_b a) \ cdot \ log n) = \ Theta (n \ cdot \ log n) \).

Analiza e kompleksitetit të renditjes së shpejtë

Në rastin më të mirë, grupi origjinal ndahet në dy pjesë, secila përmban gjysmën e të dhënave origjinale. Ndarja do të kërkojë n operacione. Kompleksiteti i kompozimit të rezultatit varet nga strukturat e të dhënave të përdorura - për një grup \ (\ mathcal (O) (n) \), për një listë të lidhur \ (\ mathcal (O) (1) \). \ (a = 2, b = 2, f_n = b \), kështu që kompleksiteti i algoritmit do të jetë i njëjtë me atë të renditjes së bashkimit: \ (T ^ (Rregullimi i shpejtë) _n = \ mathcal (O) (n \ cdot \ log n) \ ).

Megjithatë, në rastin më të keq, elementi minimal ose maksimal i grupit do të zgjidhet vazhdimisht si referencë. Pastaj \ (b = 1 \), që do të thotë se përsëri nuk mund të përdorim teoremën kryesore. Megjithatë, ne e dimë se në këtë rast do të ekzekutohen n thirrje rekursive, secila prej të cilave e ndan grupin në pjesë (\ (\ mathcal (O) (n) \)) - prandaj kompleksiteti i algoritmit \ (T ^ (QuickSort ) _n = \ mathcal (O) (n ^ 2) \).

Kur analizohet renditja e shpejtë me zëvendësim, duhet të merren parasysh veçmas rastet më të mira dhe më të këqija.

Rekursioni dhe laku i bishtit

Analizimi i kompleksitetit të funksioneve rekurzive është shumë më i vështirë sesa vlerësimi i sytheve, por arsyeja kryesore pse sythe janë të preferueshme është kostoja e lartë e një thirrjeje funksioni.

Pas thirrjes kontrolli është transferuar funksion tjetër. Për të transferuar kontrollin, mjafton të ndryshoni vlerën e regjistrit të numëruesit të programit, në të cilin procesori ruan numrin e komandës së ekzekutuar aktualisht - në të njëjtën mënyrë, kontrolli transferohet në degët e algoritmit, për shembull, kur përdorni një operator i kushtëzuar. Megjithatë, një thirrje nuk është vetëm një transferim i kontrollit, sepse pasi funksioni i thirrur të përfundojë llogaritjet, duhet rimarrë kontrollin deri në pikën ku është kryer thirrja, dhe gjithashtu rivendosni vlerat e variablave lokale që ekzistonin atje përpara thirrjes.

Për të zbatuar këtë sjellje, përdoret një pirg (pirg i thirrjeve, pirg i thirrjeve) - numri i komandës për t'u kthyer dhe informacioni rreth variablave lokale vendosen në të. Stacki nuk është i pafund, prandaj algoritmet rekursive mund të çojnë në tejmbushjen e tij; në çdo rast, mund të marrë një pjesë të konsiderueshme të kohës për të punuar me të.

Në disa raste, është mjaft e lehtë të zëvendësohet një funksion rekurziv me një lak, për shembull, ato të diskutuara më sipër. Në disa raste, kërkohet një qasje më kreative, por më shpesh një zëvendësim i tillë është i mundur. Përveç kësaj, ekziston një lloj i veçantë i rekursionit ku thirrja rekursive është operacioni i fundit i kryer nga funksioni. Natyrisht, në këtë rast, funksioni i thirrjes nuk do të ndryshojë rezultatin në asnjë mënyrë, që do të thotë se nuk ka kuptim që ai të kthejë kontrollin. Të tillë rekursioni quhet rekursion i bishtit- përpiluesit e zëvendësojnë automatikisht me një lak.

Shpesh ndihmon për të bërë rekursionin e bishtit metoda e parametrit të grumbullimit, i cili konsiston në shtimin e një argumenti shtesë të akumuluesit në funksion, në të cilin akumulohet rezultati. Funksioni kryen llogaritjet e akumulatorit përpara thirrjes rekursive. Një shembull i mirë i përdorimit të kësaj teknike është funksioni faktorial:
\ (fakt_n = n \ cdot fakt (n-1) \\
fakt_3 = 3 \ cdot fakt_2 = 3 \ cdot (2 \ cdot fakt_1) = 3 \ cdot (2 \ cdot (1 \ cdot fakt_0)) = 6 \\
fakt_n = faktTail_ (n, 1) \\
\\
factTail_ (n, akumulator) = faktTail (n-1, akumulator \ cdot n) \\
factTail_ (3, 1) = factTail_ (2, 3) = factTail_ (1, 6) = factTail_ (0, 6) = 6
\)

Si një shembull më kompleks, merrni parasysh funksionin për llogaritjen e numrave Fibonacci. Funksioni kryesor thërret funksionin ndihmës, i cili përdor metodën e parametrit akumulues dhe kalon vlerën fillestare të iteratorit dhe dy akumulatorëve (dy numrat e mëparshëm Fibonacci) si argumente.

Fillimi; fibonacci (numri) kthimi fibonacci (numri, 1, 1, 0) fund fillimi; fibonacci (numri, iterator, fib1, fib2) nëse iterator == numri kthen fib1 kthen fibonacci (numër, përsëritës + 1, fib1 + fib2, fib1) fund

Një funksion me një parametër akumulues kthen rezultatin e grumbulluar nëse është llogaritur numri i caktuar i numrave, përndryshe ai rrit numëruesin, llogarit një numër të ri Fibonacci dhe bën një thirrje rekursive. Përpiluesit optimizues mund të zbulojnë se rezultati i një thirrjeje funksioni kalon i pandryshuar në daljen e funksionit dhe zëvendësohet me një lak. Kjo teknikë është veçanërisht e rëndësishme në gjuhët e programimit funksional dhe logjik, meqë programuesi nuk mund të përdorë në mënyrë eksplicite konstruksione ciklike në to.

Letërsia

Server Qt me shumë fije. Pellg fijesh. Modeli i dekoruesit [Burimi elektronik] - mënyra e hyrjes: https: // faqe / arkiva / 1390. Data e hyrjes: 21.02.2015.
Jason McColm Smith: Trans. nga anglishtja - M.: SH.PK “I.D. Williams”, 2013. - 304 f.
Skiena S. Algoritmet. Udhëzuesi i Zhvillimit.-2nd ed .: trans. nga anglishtja-SPb.: BHV-Petersburg, 2011.-720p .: ill.
Vasiliev V.S., Analiza e kompleksitetit të algoritmeve. Shembuj [Burimi elektronik] - mënyra e hyrjes: https: // faqe / arkiva / 1660. Data e hyrjes: 21.02.2015.
A. Aho, J. Hopcroft, J. Ullman, Strukturat e të dhënave dhe Algoritmet, M., Williams, 2007.
Miller, R. Algoritmet sekuenciale dhe paralele: Qasja e përgjithshme / R. Miller, L. Boxer; per. nga anglishtja - M.: BINOM. Laboratori i Dijes, 2006 .-- 406 f.
Sergievsky G.M. Programimi funksional dhe logjik: tekst shkollor. manual për studentët e nivelit të lartë. studim. institucionet / G.M. Sergievsky, N.G. Volçenkov. - M .: Qendra Botuese "Akademia", 2010.- 320s.

Nga lat recursio (kthim). Në përgjithësi, ky është emri për procesin e përsëritjes së elementeve në një mënyrë "të ngjashme".

Kukullat Matryoshka janë një shembull i mrekullueshëm i rekursionit. Përkufizimi rekurziv: "Matryoshka është një kukull e zbrazët prej druri e ndarë me një matryoshka më të vogël brenda." Këtu është një rekursion në Rusisht. Dhe nëse nuk do të ishte për kufirin e aftësive të zotërinjve, matryoshka ideale do të hynte thellë në vetvete deri në nivelin atomik. Dhe akoma më thellë. Thjesht Lefty nuk kishte një hapësirë të vogël të forcës së mjaftueshme. Kufiri i sipërm është gjithashtu teorikisht i pakufizuar, por baobabët me madhësi të përshtatshme nuk rriten në planetin tonë. Në përgjithësi, për arsye teknike, rekursioni duhet të jetë i kufizuar.

Në programim (si në matematikë), rekursioni është procesi i një funksioni që thërret veten (rekursion i drejtpërdrejtë), ose një thirrje nga brenda funksionit A të funksionit B, i cili nga ana tjetër përmban një thirrje për funksionin A (rekursion indirekt ose i ndërsjellë). Natyrisht, thirrjet rekursive duhet të kenë një kusht përfundimi të kënaqshëm, përndryshe një program i tillë do të "varet" si në një lak të pafund - por, ndryshe nga një lak i pafund, me një rekursion të pafund, ai do të rrëzohet me një tejmbushje stek.

Shembull i rekursionit

Shembulli më i mërzitshëm i rekursionit në programimin matematikor është llogaritja e faktorialit. Të mos tradhtojmë traditat e lavdishme. Për ata që nuk e kanë bërë akoma: N! (faktoriali N) është prodhimi i të gjithë numrave natyrorë nga një në N (faktoriali i zeros është 1).
Ju mund të shumëzoni në mënyrë budallaqe numrat nga 1 në N në një lak. Ose mund të ndërtoni një funksion faktorial (n), i cili do të përmbajë një kusht dhe do të thërrasë veten. Nëse n është e barabartë me një, atëherë funksioni kthen vlerën 1, përndryshe kthen vlerën n të shumëzuar me faktorialin (n-1).
Skicë PHP

Funksioni faktorial ($ n) (nëse ($ n == 1) (kthim 1;) tjetër (intval i kthimit ($ n * faktorial ($ n - 1));))

Përdorime praktike të rekursionit

"Epo, dhe pse është e nevojshme kjo këtu?" - do të na pyesë një lexues i ri i padurueshëm - "Marrëzia shkencore, lodhja, lloj-lloj faktorësh... Dhe praktikisht për çfarë të zbatohet ky rekursion?"
"Për syrin e zi të programimit në internet" - ne do të përgjigjemi pa hezitim. Dhe atëherë do ta justifikojmë.

Në fakt, ka shumë më tepër përdorime të rekursionit në programimin në ueb sesa duket. Sepse rekursioni është ndoshta mënyra e vetme për të përshkuar çdo strukturë peme, kur as madhësia e saj dhe as thellësia e foleve nuk dihen paraprakisht. Nga rruga, ndërtimi dhe kalimi i grafikëve gjithashtu nuk mund të bëjë pa të. Ky është një klasik, zotërinj - provoni në një mënyrë tjetër të kërkoni skedarët që ju nevojiten në pemën e drejtorisë unix dhe menjëherë do të kuptoni se pa rekursion, nuk mund të shkoni askund.

Mundohuni të bëni pa të duke ndërtuar një hartë faqeje me një strukturë hierarkike të seksioneve në formën e listave të mbivendosura. Preferoni të varni veten sesa ta ndërtoni nëse nuk e dini paraprakisht saktësisht se në sa nivele është e kufizuar thellësia e foleve. Dhe edhe nëse e dini, por përpiquni të bëni pa rekursion, atëherë në vend të një funksioni të thjeshtë, transparent dhe pa probleme, ndërtoni një softuer të rëndë "raft në paterica". Dhe kur të keni mbaruar dhe fshirë nga balli juaj i djersitur, e vërteta e errët e jetës do të arrijë tek ju: kur thellësia e foleve të ndryshojë, struktura juaj e përhapjes do të ndalojë menjëherë punën e duhur. Prandaj, nuk ka gjasa të jeni në gjendje ta aplikoni atë diku tjetër.

Rekursioni i motorit të kërkimit

Po tamam. Edhe motorët e kërkimit nuk kanë ku të shkojnë nga rekursioni. Meqenëse u krijua zakoni i matjes së autoritetit të një siti (dokumenti) me numrin e lidhjeve, motorët e kërkimit ranë në një kurth rekurziv dhe i lanë të enden në të përgjithmonë (kjo është një dëshirë e sinqertë e mirë e autorit). Lidhja "pesha" e një faqeje përbëhet nga copa të vogla "peshe" nga të gjitha ato që lidhen me të. Për të llogaritur këtë peshë për A, referuar nga B, C dhe D, ju duhet të llogaritni peshën e tyre, e cila nga ana tjetër transmetohet nga të gjitha llojet e të tjerëve, pesha e të cilave gjithashtu duhet të llogaritet ... e kështu me radhë gjatë gjithë kohës. i gjithë Ueb-i i numëruar në motorin e kërkimit. Një problem tërësisht rekurziv. Dhe ju thoni - një teori e fortë. Pjesa më e madhe që as nuk është praktikë e vërtetë.

Rankimi i faqeve rekursive nga Google

Krijuesit e Google publikuan algoritmin e tyre bazë për llogaritjen e PageRank shumë kohë më parë. Dhe sado që ka ndryshuar që atëherë, sado është plotësuar me përmirësime, baza mbetet e njëjtë. Ju nuk mund ta dini se sa PageRank lidhet me faqen A derisa ne të kemi llogaritur se sa ka marrë PageRank Page B nga të gjitha faqet e tjera që janë lidhur me të, dhe kjo nuk mund të dihet derisa të llogarisim PageRank e atyre faqet... vazhdo? Ndoshta nuk është më e nevojshme. Është përsëri Ajo - Madhëria e Saj Rekursioni .

YouTube kolegjial

1 / 5
Në matematikë, rekursioni i referohet metodës së përcaktimit të funksioneve dhe serive të numrave: dhënë në mënyrë rekursive një funksion përcakton vlerën e tij duke iu referuar vetes me argumente të tjera. Në këtë rast, dy opsione janë të mundshme:
e = 2 + 2 2 + 3 3 + 4 4 +… = 2 + f (2) (\ stili i shfaqjes e = 2 + (\ cfrac (2) (2 + (\ cfrac (3) (3 + (\ cfrac ( 4) (4+ \ ldots)))))) \; = 2 + f (2)), ku f (n) = n n + f (n + 1) (\ stili i ekranit f (n) = (\ cfrac (n) (n + f (n + 1)))) Llogaritja e drejtpërdrejtë duke përdorur formulën e mësipërme do të shkaktojë një rekursion të pafund, por mund të vërtetohet se vlera e f (n) tenton në një me rritje n (prandaj, pavarësisht pafundësisë së serisë, vlera e numrit të Euler-it është e fundme). Për një llogaritje të përafërt të vlerës së e, mjafton që të kufizohet artificialisht thellësia e rekursionit në një numër të caktuar të paracaktuar paraprakisht, dhe me arritjen e tij, përdoret në vend të f (n) (\ stili i shfaqjes f (n)) njësi.
Një shembull tjetër i rekursionit në matematikë është një seri numerike, e dhënë nga një formulë rekursive, kur çdo term tjetër në seri llogaritet si rezultat i një funksioni nga n anëtarë të mëparshëm. Kështu, me ndihmën e një shprehjeje të fundme (e cila është një kombinim i një formule të përsëritur dhe një grup vlerash për n anëtarët e parë të një serie), mund të përcaktohet një seri e pafundme.

Struktura element_of_lista (element_of_list * tjetër; / * tregues për elementin tjetër të të njëjtit lloj * / int të dhëna; / * disa të dhëna * /);

Meqenëse një numër i pafund objektesh të mbivendosur nuk mund të vendosen në memorien e fundme, në realitet struktura të tilla të përcaktuara në mënyrë rekursive janë gjithmonë të fundme. Në qelizat përfundimtare (terminale), zakonisht shkruhen tregues null, të cilët janë në të njëjtën kohë flamuj që tregojnë për programin që përpunon strukturën se është arritur fundi i tij.

Rekursioni është një fenomen mjaft i zakonshëm që ndodh jo vetëm në fushat e shkencës, por edhe në jetën e përditshme. Për shembull, efekti Droste, trekëndëshi i Sierpinskit, etj. Mënyra më e lehtë për të parë rekursionin është të drejtoni kamerën në ekranin e kompjuterit, natyrisht, pasi ta keni ndezur. Kështu, kamera do të regjistrojë imazhin e ekranit të kompjuterit dhe do ta shfaqë atë në këtë ekran, do të dalë diçka si një lak i mbyllur. Si rezultat, ne do të vëzhgojmë diçka që duket si një tunel.

Në programim, rekursioni është i lidhur ngushtë me funksionet, më saktë, falë funksioneve në programim, ekziston një gjë e tillë si rekursioni ose funksioni rekurziv. Me fjalë të thjeshta, rekursioni është përcaktimi i një pjese të një funksioni (metode) përmes vetvetes, domethënë është një funksion që thërret veten, drejtpërdrejt (në trupin e tij) ose tërthorazi (nëpërmjet një funksioni tjetër). Problemet tipike rekursive janë problemet: gjetja e n !, numri Fibonacci. Ne kemi zgjidhur tashmë probleme të tilla, por duke përdorur sythe, domethënë në mënyrë të përsëritur. Në përgjithësi, gjithçka që zgjidhet në mënyrë iterative mund të zgjidhet në mënyrë rekursive, domethënë duke përdorur një funksion rekurziv. E gjithë zgjidhja zbret në zgjidhjen e rastit bazë ose, siç quhet ndryshe, rastit bazë. Ekziston një gjë e tillë si një hap rekursioni ose një thirrje rekursive. Në rastin kur një funksion rekurziv thirret për të zgjidhur një problem kompleks (jo një rast bazë), kryhen një sërë thirrjesh ose hapash rekurzive për ta reduktuar problemin në një problem më të thjeshtë. Dhe kështu me radhë derisa të marrim një zgjidhje bazë. Le të zhvillojmë një program që deklaron një funksion rekurziv që llogarit n!

"stdafx.h" #include << "Enter n!: "; cin >> n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// kodi Kodi :: Blloqe

// Kodi Dev-C ++

// factorial.cpp: përcakton pikën hyrëse për aplikacionin e konsolës. #përfshi duke përdorur hapësirën e emrave std; int faktorial i panënshkruar (gjatë int i panënshkruar);// prototipi i funksionit rekurziv int i = 1; // inicializimi i një ndryshoreje globale për numërimin e numrit të thirrjeve rekursive të rezultatit int të panënshkruar; // variabël globale për ruajtjen e rezultatit të kthyer të funksionit rekurziv int main (int argc, char * argv) (int n; // variabël lokale për kalimin e numrit të futur nga cout i tastierës<< "Enter n!: "; cin >> n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

V rreshtat 7, 9, 21 lloji i të dhënave është i panënshkruar gjatë int, pasi vlera faktoriale rritet shumë shpejt, për shembull, tashmë 10! = 3 628 800. Nëse madhësia e llojit të të dhënave nuk është e mjaftueshme, atëherë si rezultat marrim një vlerë krejtësisht të gabuar. Ka më shumë operatorë të deklaruar në kod sesa nevojiten për të gjetur n !. Kjo është bërë në mënyrë që, pasi të punohet, programi do të tregojë se çfarë ndodh në çdo hap të thirrjeve rekursive. Vini re linjat e theksuara të kodit, rreshtat 23, 24, 28Është një zgjidhje rekursive n !. Rreshtat 23, 24 janë zgjidhja bazë e një funksioni rekurziv, domethënë, sa më shpejt që vlera në ndryshore f do të jetë e barabartë me 1 ose 0 (pasi e dimë se 1! = 1 dhe 0! = 1), thirrjet rekursive do të ndalojnë dhe vlerat do të fillojnë të kthehen, për çdo thirrje rekursive. Kur kthen vlerën për thirrjen e parë rekursive, programi do të kthejë vlerën e faktorialit të llogaritur. V rreshti 28 funksioni faktorial () thërret veten, por tashmë argumenti i tij është një më pak. Argumenti zvogëlohet çdo herë për të arritur një zgjidhje të caktuar. Rezultati i programit (shih Figurën 1).

Shkruani n !: 5 Hapi 1 Rezultati = 0 Hapi 2 Rezultati = 0 Hapi 3 Rezultati = 0 Hapi 4 Rezultati = 0 5! = 120

Figura 1 - Rekursioni në C ++

Sipas rezultatit të programit, çdo hap është qartë i dukshëm dhe rezultati në çdo hap është i barabartë me zero, përveç thirrjes së fundit rekursive. Ishte e nevojshme të llogariteshin pesë faktoriale. Programi bëri katër thirrje rekursive; në thirrjen e pestë, u gjet rasti bazë. Dhe sapo programi mori një zgjidhje për rastin bazë, ai zgjidhi hapat e mëparshëm dhe nxori rezultatin e përgjithshëm. Figura 1 tregon vetëm katër hapa sepse në hapin e pestë u gjet një zgjidhje e veçantë, e cila përfundimisht ktheu zgjidhjen përfundimtare, pra 120. Figura 2 tregon një diagram të llogaritjes rekursive prej 5 !. Diagrami tregon qartë se rezultati i parë kthehet kur arrihet një zgjidhje e caktuar, por jo menjëherë, pas çdo thirrjeje rekursive.

Figura 2 - Rekursioni në C ++

Pra, për të gjetur 5! duhet të dini 4! dhe shumëzojeni atë me 5; 4! = 4 * 3! etj. Sipas skemës së paraqitur në Figurën 2, llogaritja do të reduktohet në gjetjen e një rasti të veçantë, domethënë 1 !, pas së cilës vlerat do të kthehen në secilën thirrje rekursive me radhë. Thirrja e fundit rekursive do të kthehet 5 !.

Le të ribëjmë programin për gjetjen e faktorialit në mënyrë që të marrim një tabelë faktoriale. Për ta bërë këtë, ne do të deklarojmë një cikli for në të cilin do të thërrasim një funksion rekurziv.

duke përdorur hapësirën e emrave std; int faktorial i panënshkruar (gjatë int i panënshkruar);// prototipi i funksionit rekurziv int i = 1; // inicializimi i një ndryshoreje globale për numërimin e numrit të thirrjeve rekursive të rezultatit int të panënshkruar; // variabël globale për ruajtjen e rezultatit të kthyer të funksionit rekurziv int main (int argc, char * argv) (int n; // variabël lokale për kalimin e numrit të futur nga cout i tastierës<< "Enter n!: "; cin >> n; për (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <> n; për (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <
// kodi Kodi :: Blloqe

// Kodi Dev-C ++

// fibonacci.cpp: përcakton pikën hyrëse për aplikacionin e konsolës. #përfshi // bibliotekë për formatimin e informacionit të shfaqur në ekran #include duke përdorur hapësirën e emrave std; fibonacci i gjatë i panënshkruar (i gjatë i panënshkruar); // prototipi i funksionit rekurziv për gjetjen e numrave nga seria Fibonacci int kryesore (int argc, char * argv) (numri_i panënshkruar i gjatë; cout<< "Enter number from the Fibonacci series: "; cin >> numri_i futur; për (int counter = 1; counter<= entered_number; counter++) cout << setw(2) <
Supozoni se është e nevojshme të lëvizni tre disqe nga shufra e parë në të tretën, që do të thotë se shufra e dytë është ndihmëse. Zgjidhja vizuale për këtë problem është implementuar në Flash. Klikoni në butonin e fillimit për të filluar animacionin, butonin e ndalimit për të ndaluar.

Programi duhet të shkruhet për numrin e n-të të disqeve. Meqenëse këtë problem e zgjidhim në mënyrë rekursive, së pari duhet të gjejmë raste të veçanta të zgjidhjes. Në këtë problem, ekziston vetëm një rast i veçantë - kjo është kur është e nevojshme të lëvizni vetëm një disk, dhe në këtë rast as një shufër ndihmëse nuk nevojitet, por ne thjesht nuk i kushtojmë vëmendje kësaj. Tani ju duhet të organizoni një zgjidhje rekursive nëse numri i disqeve është më shumë se një. Le të prezantojmë disa shënime për të mos shkruar shumë:

<Б> - shufra në të cilën fillimisht janë vendosur disqet (shkopi bazë);
<П> - shufra ndihmëse ose e ndërmjetme;
<Ф> - shufra përfundimtare - shufra në të cilën duhet të zhvendosen disqet.

Më tej, kur përshkruajmë algoritmin për zgjidhjen e problemit, ne do të përdorim këto emërtime. Për të zhvendosur tre disqe nga <Б> në <Ф> fillimisht duhet të zhvendosim dy disqe nga <Б> në <П> dhe më pas zhvendoseni diskun e tretë (më të madhin) në <Ф> , sepse <Ф> pa pagesë.

Për të lëvizur n disqe me <Б> në <Ф> ne duhet të lëvizim së pari n-1 disqe me <Б> në <П> dhe më pas zhvendoseni diskun e n-të (më të madhin) në <Ф> , sepse <Ф> pa pagesë. Pas kësaj, ju duhet të lëvizni n-1 disqe me <П> në <Ф> , gjatë përdorimit të shufrës <Б> si një ndihmës. Këta tre hapa janë i gjithë algoritmi rekurziv. I njëjti algoritëm pseudokod:
n-1 leviz ne <П>
n leviz ne <Ф>
n-1 lëvizin nga <П> në <Ф> , gjatë përdorimit <Б> si një ndihmës

// hanoi_tower.cpp: përcakton pikën hyrëse për aplikacionin e konsolës. // Një program që zgjidh në mënyrë rekursive problemin e Kullës së Hanoit #include "stdafx.h" #include #përfshi duke përdorur hapësirën e emrave std; kullë e zbrazët (int, int, int, int); // deklarimi i prototipit të funksionit rekurziv int count = 1; // variabla globale për numërimin e numrit të hapave int _tmain (int argc, _TCHAR * argv) (cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> numri; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> shufra_bazë; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> shufra_fundore; int help_rod; // bllok për përcaktimin e numrit të terminalit ndihmës, duke analizuar numrat e terminalit fillestar dhe përfundimtar nëse (basic_rod! = 2 && final_rod! = 2) help_rod = 2; ndryshe nëse (shkopi_bazë! = 1 && shufra_fundore! = 1) shufra_ndihme = 1; ndryshe nëse (shkopi_bazë! = 3 && shufra_fundore! = 3) shufra_ndihme = 3; kulla (// ekzekutoni një funksion rekurziv për zgjidhjen e problemit të numrit të Kullave të Hanoi, // një variabël që ruan numrin e disqeve që do të zhvendosen - bastic_rod, // një ndryshore që ruan numrin e bërthamës ku do të jenë disqet fillimisht e vendosur help_rod, // variabël që ruan numrin e bërthamës, i cili përdoret si një shufër_finale ndihmëse); // variabël që ruan numrin e pivotit në të cilin disqet duhet të zhvendosen sistemi ("pauzë"); kthimi 0; ) void tower (int count_disk, int baza, int help_baza, int new_baza) (if (count_disk == 1) // kusht për përfundimin e thirrjeve rekursive (cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// kodi Kodi :: Blloqe

// Kodi Dev-C ++

// hanoi_tower.cpp: përcakton pikën hyrëse për aplikacionin e konsolës. // Një program që zgjidh në mënyrë rekursive problemin e Kullës së Hanoi #include #përfshi duke përdorur hapësirën e emrave std; kullë e zbrazët (int, int, int, int); // deklarimi i prototipit të funksionit rekurziv int count = 1; // variabël globale për numërimin e numrit të hapave në main () (cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> numri; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> shufra_bazë; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> shufra_fundore; int help_rod; // bllok për përcaktimin e numrit të terminalit ndihmës, duke analizuar numrat e terminalit fillestar dhe përfundimtar nëse (basic_rod! = 2 && final_rod! = 2) help_rod = 2; ndryshe nëse (shkopi_bazë! = 1 && shufra_fundore! = 1) shufra_ndihme = 1; ndryshe nëse (shkopi_bazë! = 3 && shufra_fundore! = 3) shufra_ndihme = 3; kulla (// ekzekutoni një funksion rekurziv për zgjidhjen e problemit të numrit të Kullave të Hanoi, // një variabël që ruan numrin e disqeve që do të zhvendosen - bastic_rod, // një ndryshore që ruan numrin e bërthamës ku do të jenë disqet fillimisht e vendosur help_rod, // variabël që ruan numrin e bërthamës, i cili përdoret si një shufër_finale ndihmëse); // variabli që ruan numrin e shiritit në të cilin duhet të zhvendosen disqet kthen 0; ) void tower (int count_disk, int baza, int help_baza, int new_baza) (if (count_disk == 1) // kusht për përfundimin e thirrjeve rekursive (cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

Figura 5 tregon një shembull se si funksionon programi rekurziv Tower of Hanoi. Së pari, futëm numrin e disqeve të barabartë me tre, më pas futëm shufrën bazë (së pari) dhe caktuam shufrën përfundimtare (të tretë). Automatikisht shufra e dytë u bë ndihmëse. Programi prodhoi një rezultat të tillë që përkon plotësisht me zgjidhjen e animacionit për këtë problem.

Futni numrat e disqeve: 3 Futni numrin e shufrës bazë: 1 Futni numrin e shufrës përfundimtare: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

Figura 5 - Rekursioni në C ++

Nga figura shihet se së pari disku lëviz nga shufra një në shufrën tre, pastaj nga shufra një në shufrën dy, nga shufra tre në shufrën.dy, etj. Kjo do të thotë, programi jep vetëm sekuencën e lëvizjeve të disqeve dhe numrin minimal të hapave në të cilët do të zhvendosen të gjithë disqet.

Të gjitha këto detyra mund të zgjidhen në mënyrë të përsëritur. Shtrohet pyetja: "Cila është zgjidhja më e mirë, në mënyrë përsëritëse apo rekursive?" Përgjigja ime është: “Dizavantazhi i rekursionit është se ai konsumon dukshëm më shumë burime kompjuterike sesa përsëritja. Kjo përkthehet në një ngarkesë të madhe si në RAM ashtu edhe në procesor. Nëse zgjidhja e një problemi të caktuar është e dukshme në një mënyrë përsëritëse, atëherë duhet të përdoret ndryshe, përdorni rekursion! Në varësi të problemit që zgjidhet, kompleksiteti i shkrimit të programeve ndryshon kur përdoret një ose një metodë tjetër zgjidhjeje. Por më shpesh problemi i zgjidhur me metodën rekursive nga pikëpamja e lexueshmërisë së kodit është shumë më i qartë dhe më i shkurtër.

Rekursionet janë ngjarje interesante në vetvete, por në programim ato kanë një rëndësi të veçantë në raste individuale. Kur përballen me to për herë të parë, një numër mjaft i konsiderueshëm njerëzish kanë probleme për t'i kuptuar ato. Kjo është për shkak të fushës së madhe të përdorimit potencial të vetë termit, në varësi të kontekstit në të cilin përdoret "rekursioni". Por shpresohet që ky artikull të ndihmojë në shmangien e keqkuptimeve ose keqkuptimeve të mundshme.
Çfarë është "rekursion" gjithsesi?
Fjala "rekursion" ka një sërë kuptimesh në varësi të zonës në të cilën përdoret. Shënimi i përgjithshëm është ky: rekursionet janë përkufizime, imazhe, përshkrime të objekteve ose proceseve në vetë objektet. Ato janë të mundshme vetëm në ato raste kur objekti është pjesë e vetvetes. Matematika, fizika, programimi dhe një sërë disiplinash të tjera shkencore e përcaktojnë rekursionin në mënyrën e tyre. Ajo gjeti zbatim praktik në punën e sistemeve të informacionit dhe eksperimenteve fizike.
Çfarë nënkuptohet me rekursion në programim?
Situatat rekursive, ose rekursioni në programim, janë momentet kur një procedurë ose funksion në një program thërret vetveten. Sado e çuditshme që tingëllon për ata që filluan të mësojnë programim, nuk ka asgjë të çuditshme këtu. Mos harroni se rekursionet nuk janë të vështira, dhe në disa raste ato zëvendësojnë sythe. Nëse kompjuteri e vendos saktë thirrjen në një procedurë ose funksion, ai thjesht do të fillojë ta ekzekutojë atë.
Rekursioni mund të jetë i fundëm ose i pafund. Në mënyrë që i pari të ndalojë së thirruri veten, ai duhet të përmbajë edhe kushtet për përfundimin. Kjo mund të jetë një ulje e vlerës së një ndryshoreje dhe kur arrihet një vlerë e caktuar, thirrja ndalet dhe programi përfundon / kalohet në kodin tjetër, në varësi të nevojave për të arritur qëllime të caktuara. Rekursioni i pafund do të thotë që do të thirret për sa kohë që kompjuteri ose programi në të cilin po ekzekutohet është duke u ekzekutuar.
Është gjithashtu e mundur të organizohet rekursion kompleks duke përdorur dy funksione. Le të themi se ka A dhe B. Funksioni A ka një thirrje për B në kodin e tij, dhe B, nga ana tjetër, i tregon kompjuterit nevojën për të ekzekutuar A. Rekursionet komplekse janë një rrugëdalje nga një sërë situatash komplekse logjike për kompjuterin logjikës.
Nëse lexuesi i këtyre rreshtave ka studiuar unazat e programit, atëherë ai me siguri tashmë ka vënë re ngjashmërinë midis tyre dhe rekursionit. Në përgjithësi, ata me të vërtetë mund të kryejnë detyra të ngjashme ose identike. Është i përshtatshëm të përdoret rekursioni për të simuluar një lak. Kjo është veçanërisht e dobishme kur vetë sythe nuk janë shumë të përshtatshme për t'u përdorur. Skema e zbatimit të softuerit nuk ndryshon shumë midis gjuhëve të ndryshme të programimit të nivelit të lartë. Megjithatë, rekursioni në Pascal dhe rekursioni në C ose një gjuhë tjetër kanë veçoritë e tyre. Mund të zbatohet me sukses në gjuhë të nivelit të ulët si Assembler, por kjo është më problematike dhe kërkon kohë.
Pemë rekursioni
Çfarë është një "pemë" në programim? Ky është një grup i kufizuar i përbërë nga të paktën një nyje, e cila:
1. Ajo ka një nyje të veçantë fillestare, e cila quhet rrënja e të gjithë pemës.
2. Pjesa tjetër e nyjeve janë në një numër jozero nënbashkësish të shkëputura në çift, dhe ato janë gjithashtu një pemë. Të gjitha format e tilla të organizimit quhen nënpemë të pemës kryesore.
Me fjalë të tjera: pemët përmbajnë nënpemë, të cilat përmbajnë më shumë pemë, por në numër më të vogël se pema e mëparshme. Kjo vazhdon derisa në një nga nyjet të mos ketë mundësi për të lëvizur më tej, dhe kjo do të shënojë fundin e rekursionit. Ekziston një nuancë tjetër në lidhje me vizatimin skematik: pemët e zakonshme rriten nga poshtë lart, por në programim ato vizatohen anasjelltas. Nyjet që nuk kanë vazhdim quhen nyje fundore. Për lehtësinë e përcaktimit dhe për lehtësi, përdoret terminologjia gjenealogjike (paraardhësit, fëmijët).
Pse përdoret në programim?
Rekursioni ka gjetur aplikimin e tij në programim në zgjidhjen e një sërë problemesh komplekse. Nëse duhet të bëni vetëm një thirrje, atëherë është më e lehtë të përdorni një cikël integrimi, por me dy ose më shumë përsëritje, për të shmangur ndërtimin e një zinxhiri dhe për t'i bërë ato të ekzekutohen në formën e një peme, aplikohen situata rekursive. Për një klasë të gjerë problemesh, organizimi i procesit llogaritës në këtë mënyrë është më optimali nga pikëpamja e konsumit të burimeve. Pra, rekursioni në Pascal ose në ndonjë gjuhë tjetër programimi të nivelit të lartë është një thirrje për një funksion ose procedurë përpara se të plotësohen kushtet, pavarësisht nga numri i thirrjeve të jashtme. Me fjalë të tjera, mund të ketë vetëm një thirrje në një nënprogram në program, por ajo do të ndodhë deri në një moment të paracaktuar. Në një farë mënyre, ky është një analog i një cikli me përdorimin e tij specifik.
Dallimet midis rekursionit në gjuhë të ndryshme programimi
Pavarësisht nga skema e përgjithshme e zbatimit dhe aplikimi specifik në çdo rast individual, rekursioni në programim ka karakteristikat e veta. Kjo mund ta bëjë të vështirë gjetjen e materialit të kërkuar. Por duhet të mbani mend gjithmonë: nëse një gjuhë programimi thërret funksione ose procedura, atëherë thirrja e rekursionit është e realizueshme. Por dallimet e tij më të rëndësishme shfaqen kur përdorni gjuhë programimi të ulëta dhe të larta. Kjo është veçanërisht e vërtetë për mundësitë e zbatimit të softuerit. Ekzekutimi në fund të fundit varet nga ajo detyrë që shtrohet, dhe rekursioni shkruhet në përputhje me të. Funksionet dhe procedurat përdoren ndryshe, por qëllimi i tyre është gjithmonë i njëjtë - të detyrojnë thirrjen për veten e tyre.
Rekursioni është i lehtë. Sa e lehtë është të kujtosh përmbajtjen e një artikulli?
Për fillestarët, mund të jetë e vështirë për t'u kuptuar në fillim, kështu që nevojiten shembuj të rekursionit ose të paktën një. Prandaj, duhet cituar një shembull i vogël nga jeta e përditshme, i cili do të ndihmojë për të kuptuar thelbin e këtij mekanizmi për arritjen e qëllimeve në programim. Merrni dy ose më shumë pasqyra, vendosini në mënyrë që të gjitha të tjerat të shfaqen në një. Pasqyrat mund të shihen të reflektojnë veten shumë herë, duke krijuar një efekt pafundësie. Këtu rekursionet janë, në mënyrë figurative, reflektime (do të ketë shumë prej tyre). Siç mund ta shihni, nuk është e vështirë të kuptohet, do të kishte një dëshirë. Dhe duke studiuar materiale programimi, atëherë mund të kuptoni se rekursioni është gjithashtu një detyrë shumë e lehtë.