Rekursioni dhe algoritmet rekursive. Çfarë është rekursioni

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 infinit, 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) (kthimi 1;) tjetër (intvali 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 faqja B është e lidhur me faqen A derisa të kemi llogaritur se sa PageRank Faqja B ka marrë 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 .

Përshëndetje Habrahabr!

Ky artikull do të diskutojë problemet e rekursionit dhe si t'i zgjidhni ato.

Shkurtimisht rreth rekursionit

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. Një nga opsionet për të parë rekursionin është të drejtoni kamerën në ekranin e kompjuterit, natyrisht, pasi ta ndizni. 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 (metodë) 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).

Është thënë shumë për rekursionin. Këtu janë disa burime të mira:

• Detyrat rekursive dhe rekursive. Fushat e zbatimit të rekursionit

Supozohet se lexuesi është teorikisht i njohur me rekursionin dhe e di se çfarë është. Në këtë artikull, ne do t'i kushtojmë më shumë vëmendje problemeve të rekursionit.

Detyrat

Kur mësoni rekursionin, mënyra më efikase për të kuptuar rekursionin është zgjidhja e problemeve.

Si të zgjidhen problemet e rekursionit?

Para së gjithash, duhet të kuptoni se rekursioni është një lloj force brutale. 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.

nga rrjeta

Çdo algoritëm i zbatuar në një formë rekursive mund të rishkruhet në një formë përsëritëse dhe anasjelltas. Mbetet pyetja nëse kjo është e nevojshme dhe sa efektive do të jetë.

Argumentet e mëposhtme mund të përdoren për të justifikuar këtë.

Për një fillim, mbani mend përkufizimin e rekursionit dhe përsëritjes. Rekursioni është një mënyrë e organizimit të përpunimit të të dhënave në të cilën një program thërret veten drejtpërdrejt, ose me ndihmën e programeve të tjera. Përsëritja është një mënyrë e organizimit të përpunimit të të dhënave në të cilën veprime të caktuara përsëriten shumë herë pa çuar në thirrje programore rekursive.

Pas kësaj, mund të konkludojmë se ato janë reciprokisht të këmbyeshme, por jo gjithmonë me të njëjtat kosto burimesh dhe shpejtësie. Për arsyetim, mund të jepni shembullin e mëposhtëm: ekziston një funksion në të cilin, për të organizuar një algoritëm të caktuar, ekziston një cikël që kryen një sekuencë veprimesh në varësi të vlerës aktuale të numëruesit (mund të mos varet prej tij). Pasi ka një cikël, do të thotë që një sekuencë veprimesh përsëriten në trup - përsëritje të ciklit. Ju mund t'i zhvendosni operacionet në një nënprogram të veçantë dhe t'ia kaloni vlerën e numëruesit, nëse ka. Pas përfundimit të ekzekutimit të nënprogramit, kontrollojmë kushtet për ekzekutimin e ciklit dhe nëse është e vërtetë, kalojmë në një thirrje të re të nënprogramit, nëse është e gabuar, e ndërpresim ekzekutimin. Sepse Ne e vendosëm të gjithë përmbajtjen e ciklit në një nënprogram, që do të thotë se kushti për ekzekutimin e ciklit vendoset edhe në një nënprogram dhe mund të merret përmes vlerës së kthyer të funksionit, parametrave të përcjellë me referencë ose tregues në nënprogramin, si dhe variablat globale. Më tej, është e lehtë të tregohet se thirrja e kësaj nënprograme nga cikli mund të konvertohet lehtësisht në një thirrje, ose jo një thirrje (kthimi i një vlere ose thjesht përfundimi i punës) i një nënprogrami nga vetvetja, e udhëhequr nga disa kushte ( ato që më parë ishin në gjendje loop). Tani, nëse shikoni programin tonë abstrakt, duket diçka si kalimi i vlerave në një nënprogram dhe përdorimi i tyre, të cilat nënprogrami do të ndryshojë pas përfundimit, d.m.th. ne zëvendësuam ciklin iterativ me një thirrje rekursive nënrutinë për të zgjidhur këtë algoritëm.

Detyra e konvertimit të rekursionit në një qasje përsëritëse është simetrike.

Duke përmbledhur, mund të shprehim mendimet e mëposhtme: për secilën qasje ekziston një klasë problemesh, e cila përcaktohet nga kërkesat specifike për një problem specifik.

Ju mund të njiheni me këtë në më shumë detaje.

Ashtu si përsëritja (laku), rekursioni duhet të ketë një kusht ndalimi - Rasti bazë (përndryshe, ashtu si një lak, rekursioni do të funksionojë përgjithmonë - i pafund). Ky kusht është rasti në të cilin shkon rekursioni (hapi i rekursionit). Në çdo hap, funksioni rekurziv thirret derisa thirrja tjetër të aktivizojë kushtin bazë dhe të ndalojë rekursionin (ose më mirë, të kthehet në thirrjen e fundit të funksionit). E gjithë zgjidhja zbret në zgjidhjen e rastit bazë. 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ë.

Pra, funksioni rekurziv përbëhet nga

• Gjendja e ndalimit ose rasti bazë
• Kushti i vazhdimit ose hapi i rekursionit është një mënyrë për të reduktuar një detyrë në ato më të thjeshta.

Le ta shqyrtojmë këtë duke përdorur shembullin e gjetjes së faktorialit:

Klasa publike Zgjidhje (rekursion publik statik int (int n) (// kushti i daljes // Rasti bazë // kur të ndalohet përsëritja e rekursionit? Nëse (n == 1) (kthimi 1;) // Hapi i rekursionit / kushti rekurziv rekursioni i kthimit ( n - 1) * n;) kryesore publike statike e zbrazët (Args vargje) (System.out.println (rekursion (5)); // thirrje funksioni rekurziv))

Këtu kushti bazë është kushti kur n = 1. Meqenëse ne e dimë se 1! = 1 dhe për të llogaritur 1! nuk kemi nevojë për asgjë. Për të llogaritur 2! ne mund të përdorim 1 !, d.m.th. 2! = 1! * 2. Për të llogaritur 3! na duhen 2! * 3 ... Për të llogaritur n! na duhet (n-1)!* n. Ky është hapi i rekursionit. Me fjalë të tjera, për të marrë vlerën e faktorialit nga numri n, mjafton të shumëzojmë vlerën e faktorialit nga numri i mëparshëm me n.

Etiketa:

• rekursion
• detyrat
• java

Shto etiketa

Rekursioni është kur një nënprogram thërret veten. Kur përballen për herë të parë me një ndërtim të tillë algoritmik, shumica e njerëzve përjetojnë vështirësi të caktuara, por pak praktikë dhe rekursion do të bëhet një mjet i kuptueshëm dhe shumë i dobishëm në arsenalin tuaj të programimit.

1. Thelbi i rekursionit

Një procedurë ose funksion mund të përmbajë thirrje për procedura ose funksione të tjera. Duke përfshirë procedurën mund të thërrasë veten. Këtu nuk ka asnjë paradoks - kompjuteri ekzekuton vetëm në mënyrë sekuenciale komandat që has në program, dhe nëse has në një thirrje procedura, thjesht fillon të ekzekutojë këtë procedurë. Nuk ka rëndësi se cila procedurë ka dhënë komandën për ta bërë atë.

Një shembull i një procedure rekursive:

Procedura Rec (a: numër i plotë); filloni nëse a>

Konsideroni se çfarë ndodh nëse një telefonatë vendoset në programin kryesor, për shembull, në formën Rec (3). Më poshtë është një bllok diagram që tregon sekuencën e ekzekutimit të deklaratave.

Oriz. 1. Blloku i procedurës rekursive.

Procedura Rec thirret me parametrin a = 3. Përmban thirrjen e procedurës Rec me parametrin a = 2. Thirrja e mëparshme nuk ka përfunduar ende, kështu që mund të imagjinoni që një procedurë tjetër po krijohet dhe e para nuk përfundon punën e tij para se të përfundojë punën e tij. Procesi i thirrjes përfundon kur parametri a = 0. Në këtë moment, 4 instanca të procedurës ekzekutohen njëkohësisht. Numri i procedurave të kryera njëkohësisht quhet thellësia e rekursionit.

Procedura e katërt e thirrur (Rec (0)) do të shtypë numrin 0 dhe do të përfundojë punën e saj. Pas kësaj, kontrolli kthehet në procedurën që e quajti (Rec (1)) dhe shtypet numri 1. E kështu me radhë derisa të përfundojnë të gjitha procedurat. Thirrja fillestare do të printojë katër numra: 0, 1, 2, 3.

Një tjetër imazh vizual i asaj që po ndodh është paraqitur në Fig. 2.

Oriz. 2. Ekzekutimi i procedurës Rec me parametrin 3 konsiston në ekzekutimin e procedurës Rec me parametrin 2 dhe shtypjen e numrit 3. Nga ana tjetër, ekzekutimi i procedurës Rec me parametrin 2 konsiston në ekzekutimin e procedurës Rec me parametrin 1 dhe printimin e numrit 2. Dhe kështu me radhë.

Si një ushtrim më vete, merrni parasysh atë që merrni kur telefononi Rec (4). Gjithashtu, mendoni se çfarë ndodh kur e quani procedurën Rec2 (4) të përshkruar më poshtë, ku pohimet shkëmbehen.

Procedura Rec2 (a: numër i plotë); filloni të shkruani (a); nëse a> 0 atëherë Rec2 (a-1); fundi;

Vini re se në shembujt e mësipërm, thirrja rekursive është brenda një deklarate të kushtëzuar. Ky është një parakusht që rekursioni të përfundojë një ditë. Vini re gjithashtu se procedura e quan veten me një parametër të ndryshëm nga ai me të cilin u thirr. Nëse procedura nuk përdor variabla globale, atëherë kjo është gjithashtu e nevojshme në mënyrë që rekursioni të mos vazhdojë pafundësisht.

Një skemë pak më komplekse është e mundur: funksioni A thërret funksionin B, dhe ai nga ana tjetër thërret A. Kjo quhet rekursion kompleks... Në këtë rast, rezulton se procedura e parë e përshkruar duhet të thërrasë atë që nuk është përshkruar ende. Që kjo të jetë e mundur, ju duhet të përdorni.

Procedura A (n: numër i plotë); (Përshkrimi përpara (titulli) i procedurës së parë) procedura B (n: numër i plotë); (Përshkrimi i përcjelljes së procedurës së dytë) procedura A (n: numër i plotë); (Përshkrimi i plotë i procedurës A) filloni të shkruani (n); B (n-1); fundi; procedura B (n: numër i plotë); (Përshkrimi i plotë i procedurës B) filloni të shkruani (n); nëse n

Përshkrimi i përparshëm i procedurës B lejon që ajo të thirret nga procedura A. Përshkrimi përpara i procedurës A nuk kërkohet në këtë shembull dhe është shtuar për arsye estetike.

Nëse një rekursion i zakonshëm mund të krahasohet me një Ouroboros (Fig. 3), atëherë imazhi i një rekursioni kompleks mund të nxirret nga një poezi e njohur për fëmijë, ku "Ujqërit nga një frikë, hëngrën njëri-tjetrin". Imagjinoni dy ujqër që hanë njëri-tjetrin, dhe ju e kuptoni rekursionin kompleks.

Oriz. 3. Ouroboros është një gjarpër që gllabëron bishtin e vet. Vizatim nga traktati alkimik "Synosius" i Theodore Pelekanos (1478).

Oriz. 4. Rekursioni kompleks.

3. Simulimi i një cikli duke përdorur rekursion

Nëse një procedurë e quan veten, atëherë, në fakt, kjo çon në ekzekutimin e përsëritur të udhëzimeve që përmbahen në të, gjë që është e ngjashme me punën e një lak. Disa gjuhë programimi nuk përmbajnë fare konstruksione looping, duke i lënë programuesit të organizojnë përsëritje duke përdorur rekursion (për shembull, Prolog, ku rekursioni është teknika kryesore e programimit).

Për shembull, le të simulojmë punën e ciklit for. Për ta bërë këtë, ne kemi nevojë për një variabël numërues hapash, i cili mund të zbatohet, për shembull, si një parametër i procedurës.

Shembulli 1.

Procedura LoopImitation (i, n: numër i plotë); (Parametri i parë është numëruesi i hapave, parametri i dytë është numri i përgjithshëm i hapave) filloni të shkruani ("Përshëndetje N", i); // Këtu janë çdo udhëzim që do të përsëritet nëse i

Rezultati i një thirrjeje si LoopImitation (1, 10) do të ekzekutojë udhëzimet dhjetë herë me numëruesin që ndryshon nga 1 në 10. Në këtë rast, ai do të printojë:

Përshëndetje N 1
Përshëndetje N 2
…
Përshëndetje N 10

Në përgjithësi, nuk është e vështirë të shihet se parametrat e procedurës janë kufijtë e ndryshimit të vlerave të numëruesit.

Ju mund të ndërroni thirrjen rekursive dhe deklaratat që do të përsëriten, si në shembullin e mëposhtëm.

Shembulli 2.

Procedura LoopImitation2 (i, n: numër i plotë); fillojë nëse i

Në këtë rast, procedura do të thirret në mënyrë rekursive përpara se udhëzimet të fillojnë të ekzekutohen. Një shembull i ri i procedurës gjithashtu, para së gjithash, do të thërrasë një shembull tjetër, dhe kështu me radhë, derisa të arrijmë vlerën maksimale të numëruesit. Vetëm pas kësaj e fundit nga procedurat e thirrura do të ekzekutojë instruksionet e saj, pastaj e parafundit do të ekzekutojë instruksionet e saj, etj. Thirrja e LoopImitation2 (1, 10) do të printojë përshëndetjet në rend të kundërt:

Përshëndetje N 10
…
Përshëndetje N 1

Nëse imagjinojmë një zinxhir procedurash të quajtura në mënyrë rekursive, atëherë në shembullin 1 kalojmë përmes tij nga procedurat e quajtura më parë në ato të mëvonshme. Në shembullin 2, anasjelltas, nga më vonë në fillim.

Së fundi, një thirrje rekursive mund të vendoset midis dy blloqeve të udhëzimeve. Për shembull:

Procedura LoopImitation3 (i, n: numër i plotë); filloni të shkruani ("Përshëndetje N", i); (Blloku i parë i udhëzimeve mund të gjendet këtu) nëse i

Këtu, së pari, udhëzimet nga blloku i parë ekzekutohen në mënyrë sekuenciale, pastaj në mënyrë të kundërt, udhëzimet nga blloku i dytë. Kur thërrasim LoopImitation3 (1, 10), marrim:

Përshëndetje N 1
…
Përshëndetje N 10
Përshëndetje N 10
…
Përshëndetje N 1

Do të duheshin dy sythe njëherësh për të bërë të njëjtën gjë pa rekursion.

Mund të përdoret fakti që ekzekutimi i pjesëve të së njëjtës procedurë është i ndarë në kohë. Për shembull:

Shembulli 3: Shndërrimi i një numri në sistemin binar.

Siç e dini, marrja e shifrave të një numri binar ndodh duke pjesëtuar me një mbetje me bazën e sistemit të numrave 2. Nëse ka një numër, atëherë shifra e tij e fundit në paraqitjen e tij binar është

Marrja e të gjithë pjesës nga pjesëtimi me 2:

marrim një numër që ka të njëjtin paraqitje binar, por pa shifrën e fundit. Kështu, mjafton të përsërisim dy veprimet e mësipërme derisa në fushën e ndarjes tjetër të marrim pjesën e plotë të barabartë me 0. Pa rekursion, do të duket kështu:

Ndërsa x> 0 fillon c: = x mod 2; x: = x div 2; shkruani (c); fundi;

Problemi këtu është se shifrat e paraqitjes binare llogariten në rend të kundërt (të fundit të parat). Për të printuar një numër në formë normale, do t'ju duhet të mbani mend të gjithë numrat në elementët e grupit dhe t'i shfaqni ato në një lak të veçantë.

Rekursioni e bën të lehtë marrjen e prodhimit në rendin e duhur pa grupin dhe ciklin e dytë. Gjegjësisht:

Procedura e Paraqitjes Binare (x: numër i plotë); var c, x: numër i plotë; start (Blloku i parë. Ekzekutohet sipas renditjes së thirrjeve të procedurës) c: = x mod 2; x: = x div 2; (Thirrje rekursive) nëse x> 0 atëherë Paraqitja Binare (x); (Blloku i dytë. Ekzekutohet në mënyrë të kundërt) shkruani (c); fundi;

Në përgjithësi, ne nuk morëm asnjë fitim. Numrat e paraqitjes binare ruhen në variabla lokale, të cilat janë të ndryshme për çdo shembull ekzekutues të procedurës rekursive. Kjo do të thotë, nuk ishte e mundur të ruhej kujtesa. Përkundrazi, ne harxhojmë memorie shtesë duke ruajtur shumë variabla lokale x. Sidoqoftë, një zgjidhje e tillë më duket e bukur.

4. Marrëdhëniet e përsëritjes. Rekursioni dhe përsëritja

Ata thonë se një sekuencë vektorësh jepet nga një relacion përsëritjeje nëse jepet një vektor fillestar dhe një varësi funksionale e vektorit të ardhshëm nga ai i mëparshmi.

Një shembull i thjeshtë i një sasie të llogaritur duke përdorur marrëdhëniet e përsëritjes është faktoriali

Faktoriali tjetër mund të llogaritet nga ai i mëparshmi si:

Pasi kemi futur përcaktimin, marrim raportin:

Vektorët nga formula (1) mund të interpretohen si grupe vlerash të ndryshueshme. Pastaj llogaritja e elementit të kërkuar të sekuencës do të konsistojë në përditësimin e përsëritur të vlerave të tyre. Konkretisht për faktorialin:

X: = 1; për i: = 2 deri në n bëj x: = x * i; shkruani (x);

Çdo përditësim i tillë (x: = x * i) thirret përsëritje, dhe procesi i përsëritjes është duke u përsëritur.

Vini re, megjithatë, se relacioni (1) është një përkufizim thjesht rekurziv i një sekuence dhe llogaritja e elementit të n-të është në fakt marrja e shumëfishtë e funksionit f nga vetvetja:

Në veçanti, për faktorialin, mund të shkruani:

Funksioni Faktorial (n: numër i plotë): numër i plotë; fillojnë nëse n> 1 atëherë Faktorial: = n * Faktorial (n-1) tjetër Faktorial: = 1; fundi;

Duhet të kuptohet se thirrja e funksioneve përfshin disa shpenzime shtesë, kështu që opsioni i parë për llogaritjen e faktorialit do të jetë disi më i shpejtë. Në përgjithësi, zgjidhjet përsëritëse funksionojnë më shpejt se zgjidhjet rekursive.

Përpara se të kaloni në situata ku rekursioni është i dobishëm, merrni parasysh një shembull tjetër ku nuk duhet ta përdorni.

Konsideroni një rast të veçantë të marrëdhënieve të përsëritjes, kur vlera tjetër në sekuencë nuk varet nga një, por nga disa vlera të mëparshme menjëherë. Një shembull është sekuenca e mirënjohur Fibonacci, në të cilën çdo element tjetër është shuma e dy të mëparshmeve:

Me një qasje "me kokë", mund të shkruani:

Funksioni Fib (n: numër i plotë): numër i plotë; filloni nëse n> 1 atëherë Fib: = Fib (n-1) + Fib (n-2) tjetër Fib: = 1; fundi;

Çdo thirrje Fib krijon dy kopje të vetvetes menjëherë, secila prej kopjeve krijon dy të tjera, etj. Numri i transaksioneve rritet me numrin n në mënyrë eksponenciale, edhe pse me një zgjidhje përsëritëse, një lineare in n numri i operacioneve.

Në fakt, shembulli i mësipërm na mëson të mos e bëjmë këtë KUR rekursioni nuk duhet të përdoret, dhe se SI nuk duhet të përdoret. Në fund të fundit, nëse ka një zgjidhje të shpejtë përsëritëse (të bazuar në ciklin), atëherë i njëjti cikli mund të zbatohet duke përdorur një procedurë ose funksion rekurziv. Për shembull:

// x1, x2 - kushtet fillestare (1, 1) // n - numri i funksionit të kërkuar të numrit të Fibonaçit Fib (x1, x2, n: numër i plotë): numër i plotë; var x3: numër i plotë; filloni nëse n> 1 atëherë filloni x3: = x2 + x1; x1: = x2; x2: = x3; Fib: = Fib (x1, x2, n-1); fundi tjetër Fib: = x2; fundi;

Megjithatë, zgjidhjet përsëritëse janë të preferuara. Pyetja është, kur, në këtë rast, duhet të përdorni rekursion?

Çdo procedurë dhe funksion rekurziv që përmban vetëm një thirrje rekursive për veten e tyre mund të zëvendësohet lehtësisht me sythe përsëritëse. Për të marrë diçka që nuk ka një analog të thjeshtë jo-rekurziv, duhet t'i referoheni procedurave dhe funksioneve që e quajnë veten dy ose më shumë herë. Në këtë rast, grupi i procedurave të thirrura nuk formon më një zinxhir, si në Fig. 1, por një pemë e tërë. Ekzistojnë klasa të gjera problemesh kur procesi llogaritës duhet të organizohet në këtë mënyrë. Për ta, rekursioni do të jetë mënyra më e lehtë dhe më e natyrshme për ta zgjidhur atë.

5. Pemët

Baza teorike për funksionet rekursive që e quajnë veten më shumë se një herë është dega e matematikës diskrete që studion pemët.

5.1. Përkufizimet bazë. Mënyrat për të përfaqësuar pemët

Përkufizimi: grupi i fundëm T i përbërë nga një ose më shumë nyje të tilla që:
a) Ekziston një nyje e veçantë që quhet rrënja e kësaj peme.
b) Pjesa tjetër e nyjeve (duke përjashtuar rrënjën) përmbahen në nënbashkësi të shkëputura në çift, secila prej të cilave, nga ana tjetër, është një pemë. Pemët quhen nënpemë kjo pemë.

Ky përkufizim është rekurziv. Me pak fjalë, një pemë është një grup i përbërë nga një rrënjë dhe nënpemë të lidhura me të, të cilat janë gjithashtu pemë. Pema përcaktohet përmes vetvetes. Megjithatë, ky përkufizim ka kuptim, pasi rekursioni është i kufizuar. Çdo nënpemë përmban më pak nyje se pema që përmban. Në fund, arrijmë te nënpemët që përmbajnë vetëm një nyje, dhe kjo tashmë është e qartë se çfarë është.

Oriz. 3. Druri.

Në fig. 3 tregon një pemë me shtatë nyje. Edhe pse pemët e zakonshme rriten nga poshtë lart, është e zakonshme t'i vizatoni ato anasjelltas. Kur vizatoni një diagram me dorë, kjo metodë është padyshim më e përshtatshme. Për shkak të kësaj mospërputhje, ndonjëherë lind konfuzioni kur thuhet se njëra nga nyjet është mbi ose poshtë tjetrës. Për këtë arsye, është më i përshtatshëm të përdoret terminologjia e përdorur kur përshkruhen pemët familjare, duke i quajtur nyjet më afër paraardhësve rrënjë dhe pasardhës më të largët.

Pema mund të paraqitet grafikisht në disa mënyra të tjera. Disa prej tyre janë paraqitur në Fig. 4. Sipas përkufizimit, një pemë është një sistem grupesh të mbivendosura, ku këto grupe ose nuk kryqëzohen ose përfshihen plotësisht në njëra-tjetrën. Komplete të tilla mund të përshkruhen si zona në një plan (Fig. 4a). Në fig. 4b, grupet e mbivendosura nuk janë të vendosura në një aeroplan, por shtrihen në një rresht. Oriz. 4b mund të konsiderohet gjithashtu si një diagram i ndonjë formule algjebrike që përmban kllapa të ndërthurura. Oriz. 4c ofron një mënyrë tjetër popullore për të përshkruar një strukturë peme si një parvaz.

Oriz. 4. Mënyra të tjera për të përshkruar strukturat e pemëve: (a) grupe të folezuara; (b) kllapa të vendosura; (c) listën e koncesionit.

Lista kongruente ka ngjashmëri të dukshme me mënyrën se si është formatuar kodi i programit. Në të vërtetë, një program i shkruar në kuadrin e paradigmës së programimit të strukturuar mund të përfaqësohet si një pemë e përbërë nga konstruksione të mbivendosur.

Ju gjithashtu mund të bëni një analogji midis listës tabelare dhe paraqitjes së tabelave të përmbajtjes në libra, ku seksionet përmbajnë nënseksione, ato nga ana e tyre përmbajnë nënseksione, etj. Mënyra tradicionale e numërimit të seksioneve të tilla (seksioni 1, nënseksionet 1.1 dhe 1.2, nënseksioni 1.1.2, etj.) quhet sistemi dhjetor Dewey. Aplikuar në pemën në Fig. 3 dhe 4 ky sistem do të japë:

1. A; 1.1 B; 1,2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Pemë që kalojnë

Në të gjitha algoritmet që lidhen me strukturat e pemëve, një ide e njëjtë ndodh pa ndryshim, domethënë ideja duke kaluar ose kalimi i pemës... Kjo është një mënyrë për të vizituar nyjet e pemës, në të cilën çdo nyje përshkohet saktësisht një herë. Kjo rezulton në një rregullim linear të nyjeve të pemëve. Në veçanti, ekzistojnë tre mënyra: ju mund të kaloni nëpër nyjet në rendin përpara, të kundërt dhe në fund.

Algoritmi i kalimit përpara:

• Shkoni në rrënjë,
• Kaloni të gjitha nënpemët nga e majta në të djathtë në rend të drejtpërdrejtë.

Ky algoritëm është rekurziv, pasi përshkimi i një peme përmban nënpemë përshkuese, të cilat, nga ana tjetër, përshkohen sipas të njëjtit algoritëm.

Në veçanti, për pemën në Fig. 3 dhe 4, kalimi i drejtpërdrejtë jep një sekuencë nyjesh: A, B, C, D, E, F, G.

Sekuenca që rezulton korrespondon me një numërim vijues majtas-djathtas të nyjeve kur pema përfaqësohet duke përdorur kllapa të mbivendosur dhe në sistemin dhjetor Dewey, si dhe duke shkuar nga lart poshtë kur paraqitet si një listë parvazësh.

Kur ky algoritëm zbatohet në një gjuhë programimi, goditja e rrënjës korrespondon me ekzekutimin e veprimeve të caktuara nga një procedurë ose funksion, dhe kalimi i nënpemëve korrespondon me thirrjet rekursive ndaj vetvetes. Në veçanti, për një pemë binare (ku jo më shumë se dy nënpemë burojnë nga çdo nyje), procedura përkatëse do të duket kështu:

// Preorder Traversal është emri në anglisht për procedurën e porosisë direkte PreorderTraversal ((Argumentet)); filloni // Ecni nëpër rrënjë DoSomething ((Argumente)); // Kaloni nënpemën e majtë nëse (Nënpema e majtë ekziston) atëherë PreorderTransversal ((Argumentet 2)); // Përshkoni nënpemën e djathtë nëse (Ka nënpemë të djathtë) atëherë PreorderTransversal ((Argumentet 3)); fundi;

Kjo është, së pari, procedura kryen të gjitha veprimet, dhe vetëm atëherë ndodhin të gjitha thirrjet rekursive.

Algoritmi i kalimit të kundërt:

• Përshkoni nënpemën e majtë,
• Shkoni në rrënjë,
• Kaloni nënpemën tjetër në të majtë.
• Shkoni në rrënjë,
• dhe kështu me radhë derisa të përshkohet nënpema më e djathtë.

Kjo do të thotë, të gjitha nënpemët përshkohen nga e majta në të djathtë dhe kthimi në rrënjë ndodhet midis këtyre kalimeve. Për pemën në Fig. 3 dhe 4 kjo jep një sekuencë nyjesh: B, A, D, C, E, G, F.

Në procedurën rekursive përkatëse, veprimet do të vendosen ndërmjet thirrjeve rekursive. Në mënyrë të veçantë për një pemë binare:

// Inorder Traversal është emri në anglisht për procedurën e rendit të kundërt InorderTraversal ((Argumente)); Fillim // Përshkoni nënpemën e majtë nëse (Nënpema e majtë ekziston) atëherë InorderTraversal ((Argumentet 2)); // Ecni nëpër rrënjë DoSomething ((Argumente)); // Përshkoni nënpemën e djathtë nëse (Ka nënpemë të djathtë) atëherë InorderTraversal ((Argumentet 3)); fundi;

Algoritmi i kalimit nga fundi në fund:

• Kaloni të gjitha nënpemët nga e majta në të djathtë,
• Shkoni në rrënjë.

Për pemën në Fig. 3 dhe 4 kjo do të japë një sekuencë nyjesh: B, D, E, G, F, C, A.

Në procedurën përkatëse rekursive, veprimet do të shfaqen pas thirrjeve rekursive. Në mënyrë të veçantë për një pemë binare:

// Postorder Traversal është emri në anglisht për procedurën e porosisë në fund PostorderTraversal ((Argumente)); Fillim // Përshkoni nënpemën e majtë nëse (Nënpema e majtë ekziston) atëherë PostorderTraversal ((Argumentet 2)); // Përshkoni nënpemën e djathtë nëse (Ka nënpemë të djathtë) atëherë PostorderTraversal ((Argumentet 3)); // Ecni nëpër rrënjë DoSomething ((Argumente)); fundi;

5.3. Pamja e pemës në kujtesën e kompjuterit

Nëse disa informacione gjenden në nyjet e pemës, atëherë për ta ruajtur atë, mund të përdorni strukturën e duhur të të dhënave dinamike. Në Pascal, kjo bëhet duke përdorur një variabël të tipit rekord (rekord), që përmban tregues për nënpemë të të njëjtit lloj. Për shembull, një pemë binare ku çdo nyje përmban një numër të plotë mund të ruhet duke përdorur një ndryshore të tipit PTree, e cila përshkruhet më poshtë:

Lloji PTree = ^ TTree; TTree = rekord Inf: integer; LeftSubTree, RightSubTree: PTree; fundi;

Çdo nyje është e tipit PTree. Ky është një tregues, domethënë secila nyje duhet të krijohet duke thirrur procedurën New në të. Nëse nyja është fletë, atëherë fushat e saj LeftSubTree dhe RightSubTree u caktohet vlera zero... Përndryshe, nyjet LeftSubTree dhe RightSubTree krijohen gjithashtu me procedurën New.

Një regjistrim i tillë është paraqitur skematikisht në Fig. 5.

Oriz. 5. Paraqitja skematike e një regjistrimi TTree. Një rekord ka tre fusha: Inf - disa numra, LeftSubTree dhe RightSubTree - tregues për të dhënat e të njëjtit lloj TTree.

Një shembull i një peme të përbërë nga të dhëna të tilla është paraqitur në Figurën 6.

Oriz. 6. Një pemë e përbërë nga regjistrime TTree. Çdo rekord ruan një numër dhe dy tregues, të cilët mund të përmbajnë secilin prej tyre zero, ose adresat e regjistrimeve të tjera të të njëjtit lloj.

Nëse nuk keni punuar më parë me struktura që përbëhen nga regjistrime që përmbajnë lidhje me regjistrime të të njëjtit lloj, atëherë ju rekomandojmë që të njiheni me materialin rreth.

6. Shembuj të algoritmeve rekursive

6.1. Vizatimi i një peme

Konsideroni algoritmin për vizatimin e një peme të paraqitur në Fig. 6. Nëse çdo rresht konsiderohet një nyje, atëherë ky imazh plotëson mjaft përkufizimin e një peme të dhënë në seksionin e mëparshëm.

Oriz. 6. Pemë e vogël.

Procedura rekursive duhet të vizatojë padyshim një vijë (trungu përpara pirunit të parë) dhe më pas të thërrasë veten për të vizatuar dy nënpemë. Nënpemët ndryshojnë nga pema që i përmban në koordinatat e pikës fillestare, këndin e rrotullimit, gjatësinë e trungut dhe numrin e degëve që përmbajnë (një më pak). Të gjitha këto dallime duhet të bëhen nga parametrat e procedurës rekursive.

Një shembull i një procedure të tillë, i shkruar në Delphi, është paraqitur më poshtë:

Pema e procedurës (kanavacë: TCanvas; // Kanavacë në të cilën do të vizatohet pema x, y: e zgjeruar; // Koordinatat e rrënjës Këndi: i zgjeruar; // Këndi në të cilin rritet pema. Gjatësia e trungut: e zgjeruar; // Gjatësia e trungut n: numër i plotë / / Numri i pirunëve (sa // thirrje rekursive ende nuk do të thirren)); var x2, y2: e zgjeruar; // Fundi i trungut (pika e degës) fillon x2: = x + TrunkLength * cos (Këndi); y2: = y - Gjatësia e trungut * sin (Këndi); Canvas.MoveTo (round (x), rrumbullakët (y)); Canvas.LineTo (rrumbullakët (x2), rrumbullakët (y2)); nëse n> 1, atëherë filloni Pema (Canvas, x2, y2, Angle + Pi / 4, 0.55 * TrunkLength, n-1); Pema (Canvas, x2, y2, Angle-Pi / 4, 0.55 * Trunk Length, n-1); fundi; fundi;

Për të marrë fig. 6 kjo rutinë u thirr me parametrat e mëposhtëm:

Pema (Image1. Canvas, 175, 325, Pi / 2, 120, 15);

Vini re se vizatimi bëhet para thirrjeve rekursive, domethënë, pema vizatohet në rend të drejtpërdrejtë.

6.2. Kullat e Hanoi

Sipas legjendës, në tempullin e madh të Benarasit, nën katedralen që shënon mesin e botës, ndodhet një disk bronzi, në të cilin janë fiksuar tre shufra diamanti, një kubit të lartë dhe të trashë si bleta. Shumë kohë më parë, në fillimet e kohës, murgjit e këtij manastiri ishin fajtorë para zotit Brahma. I tërbuar, Brahma ngriti tre shufra të larta dhe vendosi 64 disqe prej ari të pastër mbi njërën prej tyre, dhe në mënyrë që çdo disk më i vogël të qëndronte mbi atë më të madhin. Sapo të 64 disqet të transferohen nga shufra, mbi të cilën Zoti Brahma i vendosi kur krijoi botën, në një shufër tjetër, kulla së bashku me tempullin do të shndërrohen në pluhur dhe bota do të zhduket nën rrotullat e bubullimës.
Procesi kërkon që disku më i madh të mos e tejkalojë kurrë diskun më të vogël. Murgjit janë në vështirësi, me çfarë radhe duhet të bëhen transpozimet? Kërkohet pajisja e tyre me softuer për të llogaritur këtë sekuencë.

Pavarësisht nga Brahma, kjo enigmë në fund të shekullit të 19-të u propozua nga matematikani francez Edouard Lucas. Versioni i shitur zakonisht përdorte 7-8 disqe (Fig. 7).

Oriz. 7. Puzzle "Kullat e Hanoi".

Supozoni se ka një zgjidhje për n- 1 disk. Pastaj për ndërrim n disqe, veproni si më poshtë:

1) Zhvendosja n- 1 disk.
2) Zhvendosja n disku në kutinë e mbetur të lirë.
3) Ne zhvendosim pirgun e n-1 disk i marrë në hapin (1) mbi n th disku.

Që për rastin n= 1, algoritmi i zhvendosjes është i dukshëm, atëherë me induksion duke përdorur veprimet (1) - (3) mund të zhvendosim një numër arbitrar disqesh.

Le të krijojmë një procedurë rekursive që printon të gjithë sekuencën e transferimeve për një numër të caktuar disqesh. Një procedurë e tillë me secilën thirrje të saj duhet të printojë informacion për një transferim (nga pika 2 e algoritmit). Për transferimet nga pikat (1) dhe (3), procedura do të thirret vetë me numrin e disqeve të reduktuar me një.

// n - numri i disqeve // ​​a, b, c - numrat e pin. Transferimi kryhet nga kunja a, // te kunja b me kunjën ndihmëse c. procedura Hanoi (n, a, b, c: numër i plotë); filloni nëse n> 1 atëherë filloni Hanoi (n-1, a, c, b); shkruani (a, "->", b); Hanoi (n-1, c, b, a); fundi tjetër shkruani (a, "->", b); fundi;

Vini re se grupi i procedurave të quajtura në mënyrë rekursive në këtë rast formon një pemë të përshkuar në rend të kundërt.

6.3. Analizimi i shprehjeve aritmetike

Detyra e analizës është të llogarisë vlerën e shprehjes duke përdorur vargun ekzistues që përmban shprehjen aritmetike dhe vlerat e njohura të ndryshoreve të përfshira në të.

Procesi i llogaritjes së shprehjeve aritmetike mund të paraqitet si një pemë binare. Në të vërtetë, secili prej operatorëve aritmetikë (+, -, *, /) kërkon dy operandë, të cilët gjithashtu do të jenë shprehje aritmetike dhe, në përputhje me rrethanat, mund të konsiderohen si nënpemë. Oriz. 8 tregon një shembull të një peme që përputhet me shprehjen:

Oriz. 8. Pema sintaksore që i përgjigjet shprehjes aritmetike (6).

Në një pemë të tillë, nyjet fundore do të jenë gjithmonë variabla (këtu x) ose konstante numerike, dhe të gjitha nyjet e brendshme do të përmbajnë operatorë aritmetikë. Për të ekzekutuar një operator, së pari duhet të vlerësoni operandët e tij. Kështu, pema në figurë duhet të përshkohet sipas rendit fundor. Sekuenca përkatëse e nyjeve

thirrur shënimi i kundërt i polonishtes shprehje aritmetike.

Kur ndërtoni një pemë sintaksore, duhet t'i kushtoni vëmendje veçorisë së mëposhtme. Nëse ekziston, për shembull, shprehja

dhe do të lexojmë veprimet e mbledhjes dhe zbritjes nga e majta në të djathtë, atëherë pema e saktë sintaksore do të përmbajë një minus në vend të një plus (Fig. 9a). Në fakt kjo pemë i përgjigjet shprehjes.Është e mundur të lehtësohet ndërtimi i pemës nëse shprehja (8) analizohet përkundrazi, nga e djathta në të majtë. Në këtë rast, një pemë me fig. 9b, e cila është ekuivalente me pemën 8a, por nuk kërkon zëvendësim të karaktereve.

Në mënyrë të ngjashme, nga e djathta në të majtë, ju duhet të analizoni shprehjet që përmbajnë operatorë të shumëzimit dhe ndarjes.

Oriz. 9. Pemë sintaksore për shprehje a – b + c kur lexoni nga e majta në të djathtë (a) dhe nga e djathta në të majtë (b).

Kjo qasje nuk e eliminon plotësisht rekursionin. Megjithatë, ju lejon të kufizoni veten në vetëm një thirrje në procedurën rekursive, e cila mund të jetë e mjaftueshme nëse motivi është të shqetësoheni për performancën maksimale.

7.3. Përcaktimi i një nyje peme nga numri i saj

Ideja pas kësaj qasjeje është të zëvendësohen thirrjet rekursive me një lak të thjeshtë që do të ekzekutojë aq herë sa ka nyje në pemë të formuara nga procedurat rekursive. Çfarë saktësisht do të bëhet në çdo hap duhet të përcaktohet nga numri i hapit. Krahasimi i numrit të hapit dhe veprimeve të nevojshme nuk është një detyrë e parëndësishme dhe në secilin rast do të duhet të zgjidhet veçmas.

Për shembull, supozoni se dëshironi të ekzekutoni k sythe mbivendosur mbi n hapat në secilën:

Për i1: = 0 deri në n-1 bëni për i2: = 0 deri në n-1 bëni për i3: = 0 deri në n-1 bëni ...

Nëse k nuk dihet paraprakisht, atëherë është e pamundur t'i shkruani ato në mënyrë eksplicite, siç tregohet më sipër. Duke përdorur teknikën e demonstruar në seksionin 6.5, mund të merrni numrin e kërkuar të sytheve të mbivendosur duke përdorur një procedurë rekursive:

Procedura NestedCycles (Indekset: grup i numrave të plotë; n, k, thellësia: numër i plotë); var i: numër i plotë; fillojë nëse thellësia

Për të hequr qafe rekursionin dhe për të zvogëluar gjithçka në një lak, vini re se nëse numëroni hapat në bazë n, atëherë çdo hap ka një numër të përbërë nga shifra i1, i2, i3, ... ose vlerat përkatëse nga grupi i Indekseve. Kjo do të thotë, numrat korrespondojnë me vlerat e numëruesve të ciklit. Numri i hapit në sistemin e zakonshëm dhjetor:

Gjithsej hapat do të jenë n k... Duke kaluar nëpër numrat e tyre në sistemin e shënimeve dhjetore dhe duke e përkthyer secilin prej tyre në një sistem me një rrënjë n, marrim vlerat e indekseve:

M: = rrumbullakët (IntPower (n, k)); për i: = 0 deri në M-1 filloni Numri: = i; për p: = 0 deri në k-1 do të fillojë Indekset: = Numri mod n; Numri: = Numri div n; fundi; DoSomething (Indekset); fundi;

Edhe një herë, vërejmë se metoda nuk është universale dhe do t'ju duhet të gjeni diçka tuajën për secilën detyrë.

Pyetje kontrolli

1. Përcaktoni se çfarë do të bëjnë procedurat dhe funksionet e mëposhtme rekursive.

(a) Çfarë do të printojë procedura e mëposhtme kur quhet Rec (4)?

Procedura Rec (a: numër i plotë); filloni të shkruani (a); nëse a> 0 atëherë Rec (a-1); shkruani (a); fundi;

(b) Sa do të jetë vlera e funksionit Nod (78, 26)?

Funksioni Nod (a, b: numër i plotë): numër i plotë; filloni nëse a> b atëherë Drekja: = Drekja (a - b, b) tjetër nëse b> a atëherë Drekja: = Drekja (a, b - a) tjetër Drekja: = a; fundi;

(c) Çfarë do të printojnë procedurat e mëposhtme kur telefononi A (1)?

Procedura A (n: numër i plotë); procedura B (n: numër i plotë); procedura A (n: numër i plotë); filloni të shkruani (n); B (n-1); fundi; procedura B (n: numër i plotë); filloni të shkruani (n); nëse n

(d) Çfarë do të printojë procedura e mëposhtme kur telefononi BT (0, 1, 3)?

Procedura BT (x: real; D, MaxD: numër i plotë); filloni nëse D = MaxD atëherë shkruani (x) tjetër fillon BT (x - 1, D + 1, MaxD); BT (x + 1, D + 1, MaxD); fundi; fundi;

2. Ouroboros - një gjarpër që gllabëron bishtin e vet (Fig. 14) kur shpaloset ka një gjatësi L, diametri afër kokës D, trashësia e murit të barkut d... Përcaktoni sa bisht mund të futet në vetvete dhe në sa shtresa do të vendoset bishti pas kësaj?

Oriz. 14. Uoboros i shpalosur.

3. Për pemën në fig. 10a tregon sekuencën e nyjeve të vizituara për renditjen e kalimit përpara, prapa dhe nga fundi në fund.

4. Vizatoni një paraqitje grafike të pemës, të përcaktuar duke përdorur kllapa të ndërthurura: (A (B (C, D), E), F, G).

5. Vizatoni pemën e sintaksës për shprehjen aritmetike të mëposhtme:

Shkruajeni këtë shprehje me shënimin e kundërt polak.

6. Për grafikun e mëposhtëm (Figura 15), shkruani matricën e afërsisë dhe matricën e incidencës.

Detyrat

1. Pasi të keni llogaritur faktorialin një numër mjaft të madh herë (një milion ose më shumë), krahasoni efikasitetin e algoritmeve rekursive dhe iterative. Sa herë do të ndryshojë koha e ekzekutimit dhe si do të varet ky raport nga numri, faktoriali i të cilit llogaritet?

2. Shkruani një funksion rekurziv që kontrollon kllapat e sakta në një varg. Me vendosjen e duhur, plotësohen kushtet e mëposhtme:

(a) numri i kllapave hapëse dhe mbyllëse është i barabartë.
(b) brenda çdo çifti të kllapave hapëse - mbyllëse korresponduese, kllapat vendosen saktë.

Shembuj të vendosjes së gabuar:) (, ()) (, ()) ((), etj.

3. Rreshti mund të përmbajë kllapa, si kllapa ashtu edhe kllapa katrore. Çdo kllapa e hapur korrespondon me një mbyllëse të të njëjtit lloj (rrumbullak - rrumbullak, katror - katror). Shkruani një funksion rekurziv për të kontrolluar nëse kllapat janë të sakta në këtë rast.

Një shembull i një vendosjeje të gabuar: ([)].

4. Numri i strukturave të kllapave të sakta me gjatësi 6 është 5: () () (), (()) (), () (()), ((())), (() ()).
Shkruani një program rekurziv për të gjeneruar të gjitha strukturat e sakta të kllapave me gjatësi 2 n.

Indikacion: Struktura e saktë e kllapave me gjatësi minimale "()". Strukturat më të gjata merren nga strukturat më të shkurtra në dy mënyra:

(a) nëse struktura më e vogël është e mbyllur në kllapa,
(b) nëse dy struktura më të vogla shkruhen në mënyrë sekuenciale.

5. Krijo një rutinë që printon të gjitha permutacionet e mundshme për numrat e plotë nga 1 në N.

6. Krijoni një procedurë që printon të gjitha nëngrupet e grupit (1, 2,…, N).

7. Krijo një procedurë që printon të gjitha paraqitjet e mundshme të numrit natyror N si shumë e numrave të tjerë natyrorë.

8. Krijoni një funksion që llogarit shumën e elementeve të grupit sipas algoritmit të mëposhtëm: vargu ndahet në gjysmë, numërohen dhe shtohen shumat e elementeve në secilën gjysmë. Shuma e elementeve në gjysmën e grupit llogaritet duke përdorur të njëjtin algoritëm, pra përsëri duke e ndarë në gjysmë. Ndarjet ndodhin derisa pjesët rezultuese të grupit të përmbajnë nga një element secila dhe llogaritja e shumës, përkatësisht, bëhet e parëndësishme.

Komentoni: Ky algoritëm është një alternativë. Në rastin e vargjeve me vlerë reale, zakonisht ju lejon të merrni gabime më të vogla rrumbullakimi.

10. Krijoni një procedurë që vizaton kurbën Koch (Fig. 12).

11. Riprodhoni fig. 16. Në figurë, në çdo përsëritje të radhës, rrethi është 2,5 herë më i vogël (ky koeficient mund të bëhet si parametër).

Letërsia

1.D. Knut. Arti i programimit kompjuterik. v. 1. (Seksioni 2.3. "Pemët").
2. N. Virt. Algoritmet dhe strukturat e të dhënave.

Funksione: dhënë në mënyrë rekursive funksioni në përkufizimin e tij përmban vetveten, në veçanti, funksioni i përcaktuar nga formula rekursive është rekurziv. Kështu, një shprehje mund të japë një grup të pafund metodash për llogaritjen e një funksioni, të përcaktojë një grup objektesh përmes vetes duke përdorur përkufizime private të dhëna më parë.

Të dhënat

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

Një strukturë rekursive e të dhënave shpesh dikton përdorimin e rekursionit për të përpunuar ato të dhëna.

në fizikë

Një shembull klasik i rekursionit të pafund janë dy pasqyra përballë njëra-tjetrës: në to formohen dy korridore të reflektimeve zvogëluese të pasqyrave.

Një shembull tjetër i rekursionit të pafund është efekti i vetë-ngacmimit (feedback pozitiv) i qarqeve të amplifikimit elektronik, ku një sinjal nga dalja hyn në hyrje, amplifikohet, rihyn në hyrjen e qarkut dhe amplifikohet përsëri. Përforcuesit për të cilët kjo mënyrë funksionimi është standard quhen oshilatorë.

Në gjuhësi

Aftësia e një gjuhe për të gjeneruar fjali dhe konstruksione të mbivendosura. Oferta bazë " macja hëngri miun"Mund të zgjatet me rekursion si Vanya mendoi se macja hëngri miun, pastaj si Katya e di që Vanya mendoi që macja hëngri miun etj. Rekursioni konsiderohet si një nga universalet gjuhësore, domethënë është karakteristik për çdo gjuhë natyrore. Sidoqoftë, kohët e fundit ka pasur një diskutim aktiv për mungesën e mundshme të rekursionit në një nga gjuhët e Amazonës - Piraha, e cila shënohet nga gjuhëtari Daniel Everett ( anglisht) .

Në kulturë

Shumica e shakave për rekursionin kanë të bëjnë me rekursionin e pafund, në të cilin nuk ka kusht daljeje, për shembull, dihet thënia: "për të kuptuar rekursionin, fillimisht duhet të kuptosh rekursionin".

Një shaka shumë e njohur për rekursionin, që të kujton një hyrje në fjalor:

Disa histori nga Stanislav Lem i kushtohen incidenteve (të mundshme) me rekursion të pafund:

• tregimi për Yon Tikhiy "Udhëtimi i katërmbëdhjetë" nga "The Star Diaries of Iyon the Tikhiy", në të cilin heroi kalon në mënyrë sekuenciale nga një artikull rreth sepulkit në një artikull për ndarjen, nga atje në një artikull për sepulcaria, në të cilin ka përsëri një referencë për artikullin "sepulka":

Kam gjetur informacionin e shkurtër të mëposhtëm:
“SEPULKI janë një element i rëndësishëm i qytetërimit ardrit (shih) nga planeti Enteropia (shih). Shih SEPULCARIA ".
E ndoqa këtë këshillë dhe lexova:
"SEPULKARIA - pajisje për ndarje (shih)".
Unë kërkova për Sepulenie; lexonte:
“SEPULENIE është pushtimi i ardritëve (shih) nga planeti Enteropia (shih). Shih SEPULKI”.

Lem S. “Ditarët e Yjeve të Iyon the Tikhiy. Udhëtimi i katërmbëdhjetë."

• Një histori nga "Cyberiada" për një makinë inteligjente që zotëronte inteligjencë dhe dembelizëm të mjaftueshëm për të ndërtuar një të ngjashme për të zgjidhur detyrën dhe për t'i besuar zgjidhjen asaj (rezultati ishte një rekursion i pafund, kur çdo makinë e re ndërtoi një të ngjashme dhe kaloi detyrë për të).
• Akronimet rekursive: GNU (GNU Jo Unix), PHP (PHP: Hypertext Preprocessor), etj.

Shiko gjithashtu

• Sekuenca e kundërt

Shënime (redakto)

Fondacioni Wikimedia. 2010.

• Video memorie
• Rrezatimi elektromagnetik

Shihni se çfarë është "Recursion" në fjalorë të tjerë:

rekursion- kthimi, përsëritja e Fjalorit të sinonimeve ruse. Emër rekursioni, numri i sinonimeve: 1 ... Fjalor sinonimik

rekursion- - [] rekursion Në një kuptim të përgjithshëm, llogaritja e një funksioni sipas një algoritmi të caktuar. Shembuj të algoritmeve të tilla janë formula të përsëritura që nxjerrin llogaritjen e një termi të caktuar ... ... Udhëzues teknik i përkthyesit

Rekursioni- në një kuptim të përgjithshëm, llogaritja e një funksioni sipas një algoritmi të caktuar. Shembuj të algoritmeve të tilla janë formula të përsëritura që nxjerrin llogaritjen e një anëtari të caktuar të sekuencës (më shpesh numerike) nga llogaritja e disa atyre të mëparshme ... Fjalori i ekonomisë dhe matematikës

Rekursioni- Një model terapeutik, kur një kusht ose kriter i formuluar në deklaratën origjinale merret dhe zbatohet në vetë deklaratën. Për shembull: Nuk kam kohë. Sa kohë ju është dashur të shpenzoni për t'u siguruar që keni pasur ... ... Enciklopedi e madhe psikologjike

REKURSION- një mënyrë për të përcaktuar funksionet, e cila është një objekt studimi në teorinë e algoritmeve dhe seksione të tjera të matematikës. logjikës. Kjo metodë është përdorur prej kohësh në aritmetikë për të përcaktuar sekuencat numerike (progresionet, numrat Fibonacci, etj.). ... ... Enciklopedia e matematikës

rekursion- (background.) (lat. recursio kthim). Një nga tre fazat e artikulimit të tingujve, dhëmbëzimi. Përkthimi i organeve të të folurit në një gjendje të qetë ose fillimi i artikulimit të tingullit tjetër. Në fjalën pushim, rekursioni (dhënia) kur artikulohet [t] mund të mbivendoset me ... ... Fjalor i termave gjuhësor T.V. Mëz

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 numrash, e dhënë nga një formulë rekursive, kur çdo term tjetër në seri llogaritet si rezultat i një funksioni prej n anëtarësh 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 të zbrazët, 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.