Kuptimi modern i rekursionit: përcaktimi i funksionalitetit dhe aksesi në të nga jashtë dhe nga ky funksionalitet. Besohet se rekursioni ka lindur nga matematikanët: llogaritja faktoriale, seritë e pafundme, fraktale, thyesat e vazhdueshme … Megjithatë, rekursioni mund të gjendet kudo. Ligjet objektive të natyrës "e konsiderojnë" rekursionin si algoritmin e tyre kryesor dhe formën e shprehjes (ekzistencës) jo aq shumë të objekteve të botës materiale, por në përgjithësi algoritmin kryesor të lëvizjes.
Njerëz të specialiteteve të ndryshme në fusha të ndryshme të shkencës dhe teknologjisë përdorin algoritmin rekurziv f (x), ku "x ~/=f (x)". Një funksion që e quan veten është një zgjidhje e fortë, por formimi dhe kuptimi i kësaj zgjidhjeje është, në shumicën e rasteve, një detyrë shumë e vështirë.
Në kohët e lashta, rekursioni përdorej për të rritur hapësirën e pallatit. Nëpërmjet një sistemi pasqyrash të drejtuara nga njëra-tjetra, ju mund të krijoni efekte hapësinore tredimensionale mahnitëse. Por a është kaq e lehtë të kuptosh se sirregulloni këto pasqyra? Është edhe më e vështirë të përcaktohet se ku ndodhet një pikë në hapësirë, e reflektuar përmes disa pasqyrave.
Rekursion, algoritme rekursive: kuptimi dhe sintaksa
Problemi, i cili formulohet duke përsëritur një sekuencë veprimesh, mund të zgjidhet në mënyrë rekursive. Një algoritëm i thjeshtë (llogaritja e një ekuacioni kuadratik, një skript për të mbushur një faqe interneti me informacion, leximi i një skedari, dërgimi i një mesazhi…) nuk kërkon rekursion.
Dallimet kryesore të algoritmit që lejon një zgjidhje rekursive:
- ekziston një algoritëm që duhet të ekzekutohet disa herë;
- algoritmi ka nevojë për të dhëna që ndryshojnë çdo herë;
- algoritmi nuk duhet të ndryshojë çdo herë;
- ekziston një kusht përfundimtar: algoritmi është rekursiv - jo i pafund.
Në përgjithësi, nuk mund të argumentohet se ekzekutimi një herë është një kusht i domosdoshëm për mungesën e një arsyeje për rekursion. Ju gjithashtu nuk mund të kërkoni një kusht përfundimtar të detyrueshëm: rekursionet e pafundme kanë shtrirjen e tyre.
Algoritmi është rekurziv: kur një sekuencë operacionesh kryhet në mënyrë të përsëritur, në të dhëna që ndryshojnë çdo herë dhe japin një rezultat të ri çdo herë.
Formula e rekursionit
Kuptimi matematik i rekursionit dhe analogu i tij në programim janë të ndryshëm. Matematika, edhe pse ka shenja programimi, por programimi është matematikë e rendit shumë më të lartë.
Një algoritëm i shkruar mirë është si një pasqyrë e intelektit të autorit të tij. Gjeneralformula e rekursionit në programim është "f(x)", ku "x ~/=f(x)" ka të paktën dy interpretime. Këtu "~" është ngjashmëria ose mungesa e rezultatit, dhe "=" është prania e rezultatit të funksionit.
Opsioni i parë: dinamika e të dhënave.
- funksioni "f(x)" ka një algoritëm rekurziv dhe të pandryshueshëm;
- "x" dhe rezultati "f(x)" kanë vlera të reja çdo herë, rezultati "f(x)" është parametri i ri "x" i këtij funksioni.
Opsioni i dytë: dinamika e kodit.
- funksioni "f(x)" ka disa algoritme që rafinojnë (analizojnë) të dhënat;
- analiza e të dhënave - një pjesë e kodit dhe zbatimi i algoritmeve rekursive që kryejnë veprimin e dëshiruar - pjesa e dytë e kodit;
- rezultati i funksionit "f(x)" nuk është.
Asnjë rezultat nuk është normal. Programimi nuk është matematikë, këtu rezultati nuk duhet të jetë i pranishëm në mënyrë eksplicite. Një funksion rekurziv thjesht mund të analizojë faqet dhe të mbushë bazën e të dhënave, ose të instantojë objektet sipas hyrjes hyrëse.
Të dhënat dhe rekursioni
Programimi i algoritmeve rekursive nuk ka të bëjë me llogaritjen e një faktoriali, në të cilin funksioni merr çdo herë një vlerë të caktuar që është një më shumë ose më pak se një - opsioni i zbatimit varet nga preferenca e zhvilluesit.
Nuk ka rëndësi se si faktoriali "8!",algoritmi që ndjek rreptësisht këtë formulë.
Përpunimi i informacionit është "matematikë" e një rendi krejtësisht të ndryshëm. Funksionet dhe algoritmet rekursive këtu funksionojnë me shkronja, fjalë, fraza, fjali dhe paragrafë. Çdo nivel tjetër përdor atë të mëparshëm.
Rrjedha e të dhënave hyrëse analizohet në një gamë të gjerë kushtesh, por procesi i analizës është përgjithësisht rekurziv. Nuk ka kuptim të shkruani algoritme unike për të gjitha variantet e rrymës hyrëse. Duhet të ketë një funksionalitet. Këtu, algoritmet rekursive janë shembuj se si të formohet një rrjedhë dalëse që është adekuate për hyrjen. Ky nuk është rezultati i algoritmit rekurziv, por është zgjidhja e dëshiruar dhe e nevojshme.
Abstraksioni, rekursioni dhe OOP
Programimi i orientuar nga objekti (OOP) dhe rekursioni janë entitete thelbësisht të ndryshme, por ato plotësojnë njëri-tjetrin në mënyrë të përsosur. Abstraksioni nuk ka të bëjë me rekursionin, por përmes thjerrëzës së OOP krijon mundësinë e zbatimit të rekursionit kontekstual.
Për shembull, informacioni po analizohet dhe shkronjat, fjalët, frazat, fjalitë dhe paragrafët theksohen veçmas. Natyrisht, zhvilluesi do të sigurojë krijimin e shembujve të objekteve të këtyre pesë llojeve dhe do të ofrojë një zgjidhje të algoritmeve rekursive në çdo nivel.
Ndërkohë, nëse në nivelin e shkronjave "nuk ka kuptim të kërkosh kuptim", atëherë semantika shfaqet në nivelin e fjalëve. Ju mund t'i ndani fjalët në folje, emra, ndajfolje, parafjalë… Mund të shkoni më tej dhe të përcaktoni rastet.
Në nivelin e frazës, semantika plotësohet nga shenjat e pikësimit dhe logjikakombinime fjalësh. Në nivelin e fjalive, gjendet një nivel më i përsosur i semantikës dhe një paragraf mund të konsiderohet si një mendim i plotë.
Zhvillimi i orientuar nga objekti paracakton trashëgiminë e vetive dhe metodave dhe propozon fillimin e hierarkisë së objekteve me krijimin e një paraardhësi plotësisht abstrakt. Në të njëjtën kohë, pa dyshim, analiza e secilit pasardhës do të jetë rekursive dhe nuk do të ndryshojë shumë në nivel teknik në shumë pozicione (shkronja, fjalë, fraza dhe fjali). Paragrafët, si mendimet e plota, mund të dalin nga kjo listë, por nuk janë thelbi.
Është e rëndësishme që pjesa dërrmuese e algoritmit të mund të formulohet në nivelin abstrakt të paraardhësve, duke e rafinuar atë në nivelin e secilit pasardhës me të dhëna dhe metoda të thirrura nga niveli abstrakt. Në këtë kontekst, abstraksioni hap horizonte të reja për rekursion.
Veçoritë historike të OOP
OOP ka ardhur në botën e softuerëve dy herë, megjithëse disa ekspertë mund të veçojnë shfaqjen e kompjuterit cloud dhe ideve moderne rreth objekteve dhe klasave si një raund i ri në zhvillimin e teknologjive të IT.
Termat "objekt" dhe "objektiv" në kontekstin modern të OOP zakonisht i atribuohen viteve 50 dhe 60 të shekullit të kaluar, por ato lidhen me vitin 1965 dhe shfaqjen e Simula, Lisp, Algol, Smalltalk..
Në ato ditë, programimi nuk ishte veçanërisht i zhvilluar dhe nuk mund t'i përgjigjej në mënyrë adekuate koncepteve revolucionare. Lufta e ideve dhe stileve të programimit (C / C ++ dhe Pascal - kryesisht) ishte ende larg, dhe bazat e të dhënave ishin ende të formuara konceptualisht.
Në fund të viteve '80 dhe në fillim të viteve '90, objektet u shfaqën në Pascal dhe të gjithë kujtuan klasat në C / C ++ - kjo shënoi një raund të ri interesi për OOP dhe ishte atëherë që mjetet, kryesisht gjuhët e programimit, u bënë jo mbështesin vetëm idetë e orientuara nga objekti, por evoluojnë në përputhje me rrethanat.
Sigurisht, nëse algoritmet e mëparshme rekursive ishin vetëm funksione të përdorura në kodin e përgjithshëm të programit, tani rekursioni mund të bëhet pjesë e vetive të një objekti (klase), i cili ofronte mundësi interesante në kontekstin e trashëgimisë.
Veçori e OOP moderne
Zhvillimi i OOP fillimisht i deklaroi objektet (klasat) si koleksione të dhënash dhe vetive (metoda). Në fakt, bëhej fjalë për të dhëna që kanë sintaksë dhe kuptim. Por atëherë nuk ishte e mundur të paraqitej OOP si një mjet për menaxhimin e objekteve reale.
OOP është bërë një mjet për menaxhimin e objekteve të "natyrës kompjuterike". Një skrip, një buton, një artikull i menysë, një shirit menuje, një etiketë në një dritare të shfletuesit është një objekt. Por jo një makinë, një produkt ushqimor, një fjalë apo një fjali. Objektet reale kanë mbetur jashtë programimit të orientuar nga objekti dhe mjetet kompjuterike kanë marrë një mishërim të ri.
Për shkak të dallimeve në gjuhët e njohura të programimit, shumë dialekte të OOP janë shfaqur. Për sa i përket semantikës, ato janë praktikisht ekuivalente, dhe fokusimi i tyre në sferën instrumentale dhe jo në atë të aplikuar, bën të mundur që përshkrimi i objekteve reale të merret përtej.algoritme dhe të sigurojë "ekzistencën" e tyre ndër-platformë dhe ndërgjuhëshe.
Rifte dhe mekanizma të thirrjeve funksionale
Mekanizmat për thirrjen e funksioneve (procedurat, algoritmet) kërkojnë kalimin e të dhënave (parametrave), kthimin e një rezultati dhe kujtimin e adresës së operatorit që duhet të marrë kontrollin pas përfundimit të funksionit (procedurës).
Zakonisht, grupi përdoret për këtë qëllim, megjithëse gjuhët e programimit ose vetë zhvilluesi mund të ofrojnë një sërë opsionesh për transferimin e kontrollit. Programimi modern pranon se emri i një funksioni mund të jetë jo vetëm një parametër: ai mund të formohet gjatë ekzekutimit të algoritmit. Një algoritëm mund të krijohet gjithashtu gjatë ekzekutimit të një algoritmi tjetër.
Koncepti i algoritmeve rekursive, kur emrat dhe trupat e tyre mund të përcaktohen në momentin e formimit të detyrës (zgjedhja e algoritmit të dëshiruar), shtrin rekurzivitetin jo vetëm për mënyrën se si të bëhet diçka, por edhe kush saktësisht duhet beje. Zgjedhja e një algoritmi me emrin e tij "kuptimplotë" është premtuese, por krijon vështirësi.
Rekurziviteti në një grup funksionesh
Nuk mund të thuash që një algoritëm është rekurziv kur e quan veten dhe kaq. Programimi nuk është një dogmë dhe koncepti i rekurzivitetit nuk është një kërkesë ekskluzive për të thirrur veten nga trupi i algoritmit tuaj.
Zbatimet praktike nuk japin gjithmonë një zgjidhje të pastër. Shpesh, të dhënat fillestare duhet të përgatiten dhe rezultati i thirrjes rekursive duhet të analizohet në kontekstin e të gjithë problemit (të gjithë algoritmit) nënë përgjithësi.
Në fakt, jo vetëm përpara se të thirret një funksion rekurziv, por edhe pasi të ketë përfunduar, një program tjetër mund ose duhet të thirret. Nëse nuk ka probleme të veçanta me thirrjen: funksioni rekurziv A() thërret funksionin B(), i cili bën diçka dhe thërret A(), atëherë menjëherë ka një problem me kthimin e kontrollit. Pasi të keni përfunduar thirrjen rekursive, funksioni A() duhet të marrë kontrollin në mënyrë që të ri-thirrni B(), i cili do ta thërrasë përsëri. Kthimi i kontrollit ashtu siç duhet të jetë në rradhë në grup në B() është zgjidhja e gabuar.
Programuesi nuk është i kufizuar në zgjedhjen e parametrave dhe mund t'i plotësojë ato me emrat e funksioneve. Me fjalë të tjera, zgjidhja ideale është kalimi i emrit të B() në A() dhe lëreni që vetë A() të thërrasë B(). Në këtë rast, nuk do të ketë probleme me kthimin e kontrollit dhe zbatimi i algoritmit rekurziv do të jetë më transparent.
Kuptimi dhe niveli i rekursionit
Problemi me zhvillimin e algoritmeve rekursive është se ju duhet të kuptoni dinamikën e procesit. Kur përdorni rekursionin në metodat e objektit, veçanërisht në nivelin e një paraardhësi abstrakt, ekziston një problem për të kuptuar algoritmin tuaj në kontekstin e kohës së ekzekutimit të tij.
Aktualisht, nuk ka kufizime në nivelin e foleve të funksioneve dhe kapacitetin e stivës në mekanizmat e thirrjes, por ekziston një problem i të kuptuarit: në cilën pikë kohore cili nivel i të dhënave ose cili vend në algoritmin e përgjithshëm quhet rekursiv funksioni dhe në çfarë numri telefonatash është ajo vetë.
Mjetet ekzistuese të korrigjimit janë shpesh të pafuqishëmtregoni programuesit zgjidhjen e duhur.
Syqe dhe rekursion
Konsiderohet se ekzekutimi ciklik është i barabartë me rekursionin. Në të vërtetë, në disa raste, algoritmi rekurziv mund të zbatohet në sintaksën e konstrukteve të kushtëzuara dhe ciklike.
Megjithatë, nëse ka një kuptim të qartë se një funksion i caktuar duhet të zbatohet nëpërmjet një algoritmi rekurziv, çdo përdorim i jashtëm i një cikli ose deklaratash të kushtëzuara duhet të braktiset.
Kuptimi këtu është se një zgjidhje rekursive në formën e një funksioni duke përdorur vetveten do të jetë një algoritëm i plotë, funksionalisht i plotë. Ky algoritëm do të kërkojë që programuesi ta krijojë me përpjekje, duke kuptuar dinamikën e algoritmit, por do të jetë zgjidhja përfundimtare që nuk kërkon kontroll të jashtëm.
Çdo kombinim i operatorëve të jashtëm të kushtëzuar dhe ciklik nuk do të na lejojë të përfaqësojmë algoritmin rekurziv si një funksion të plotë.
Konsensusi i rekursionit dhe OOP
Pothuajse në të gjitha variantet e zhvillimit të një algoritmi rekurziv, lind një plan për të zhvilluar dy algoritme. Algoritmi i parë gjeneron një listë të objekteve (instancave) të së ardhmes dhe algoritmi i dytë është në fakt një funksion rekurziv.
Zgjidhja më e mirë do të ishte rregullimi i rekursionit si një veti (metodë) e vetme që në fakt përmban algoritmin rekurziv dhe vendosja e të gjithë punës përgatitore në konstruktorin e objektit.
Një algoritëm rekurziv do të jetë zgjidhja e duhur vetëm kur të funksionojëvetëm nga ai vetë, pa kontroll dhe menaxhim të jashtëm. Një algoritëm i jashtëm mund të japë vetëm një sinjal për të punuar. Rezultati i kësaj pune duhet të jetë zgjidhja e pritur, pa mbështetje të jashtme.
Rekursioni duhet të jetë gjithmonë një zgjidhje e plotë e pavarur.
Kuptimi intuitiv dhe plotësia funksionale
Kur programimi i orientuar nga objekti u bë standardi de fakto, u bë e qartë se për të koduar në mënyrë efektive, ju duhet të ndryshoni të menduarit tuaj. Programuesi duhet të kalojë nga sintaksa dhe semantika e gjuhës në dinamikën e semantikës gjatë ekzekutimit të algoritmit.
Karakteristikë e rekursionit: mund të zbatohet për çdo gjë:
- gërvishtje ueb;
- operacionet e kërkimit;
- analizimi i informacionit të tekstit;
- leximi ose krijimi i dokumenteve MS Word;
- kampionimi ose analizimi i etiketave…
Karakteristikë e OOP: bën të mundur përshkrimin e një algoritmi rekurziv në nivelin e një paraardhësi abstrakt, por siguron që ai t'u referohet pasardhësve unikë, secila prej të cilëve ka paletën e vet të të dhënave dhe vetive.
Rekursioni është ideal sepse kërkon plotësinë funksionale të algoritmit të tij. OOP përmirëson performancën e një algoritmi rekurziv duke i dhënë akses të gjithë fëmijëve unikë.
