Mūsdienu izpratne par rekursiju: funkcionalitātes definīcija un piekļuve tai no ārpuses un no šīs funkcionalitātes. Tiek uzskatīts, ka rekursiju radījuši matemātiķi: faktoru aprēķins, bezgalīgas rindas, fraktāļi, turpinātas daļskaitļi … Tomēr rekursiju var atrast visur. Objektīvie dabas likumi rekursiju “uzskata” par savu galveno algoritmu un izteiksmes (esamības) formu ne tik daudz materiālās pasaules objektu, bet kopumā galveno kustības algoritmu.
Dažādu specialitāšu cilvēki dažādās zinātnes un tehnikas jomās izmanto rekursīvo algoritmu f (x), kur "x ~/=f (x)". Funkcija, kas izsauc sevi, ir spēcīgs risinājums, taču šī risinājuma izveide un izpratne vairumā gadījumu ir ļoti sarežģīts uzdevums.
Senos laikos pils telpas palielināšanai izmantoja rekursiju. Izmantojot spoguļu sistēmu, kas vērsti viens pret otru, varat izveidot satriecošus trīsdimensiju telpiskus efektus. Bet vai ir tik viegli saprast, kāregulēt šos spoguļus? Ir vēl grūtāk noteikt, kur atrodas kosmosa punkts, kas atspoguļots caur vairākiem spoguļiem.
Rekursija, rekursīvie algoritmi: nozīme un sintakse
Problēmu, kas formulēta, atkārtojot darbību secību, var atrisināt rekursīvi. Vienkāršam algoritmam (kvadrātvienādojuma aprēķināšana, skripts tīmekļa lapas aizpildīšanai ar informāciju, faila lasīšana, ziņojuma nosūtīšana…) nav nepieciešama rekursija.
Galvenās atšķirības algoritmā, kas pieļauj rekursīvu risinājumu:
- ir algoritms, kas jāizpilda vairākas reizes;
- algoritmam nepieciešami dati, kas mainās katru reizi;
- algoritmam nav jāmaina katru reizi;
- ir pēdējais nosacījums: algoritms ir rekursīvs - nav bezgalīgs.
Kopumā nevar apgalvot, ka vienreizēja izpilde ir nepieciešams nosacījums, lai nebūtu rekursijas iemesla. Jūs arī nevarat pieprasīt obligātu beigu nosacījumu: bezgalīgām rekursijām ir savs apjoms.
Algoritms ir rekursīvs: kad darbību secība tiek veikta atkārtoti, datiem, kas katru reizi mainās un katru reizi dod jaunu rezultātu.
Rekursijas formula
Matemātiskā izpratne par rekursiju un tās analogu programmēšanā ir atšķirīga. Matemātika, lai arī ir programmēšanas pazīmes, bet programmēšana ir daudz augstāka līmeņa matemātika.
Labi uzrakstīts algoritms ir kā tā autora intelekta spogulis. Ģenerālisrekursijas formula programmēšanā ir "f(x)", kur "x ~/=f(x)" ir vismaz divas interpretācijas. Šeit "~" ir rezultāta līdzība vai neesamība, un "=" ir funkcijas rezultāta klātbūtne.
Pirmā iespēja: datu dinamika.
- funkcijai "f(x)" ir rekursīvs un nemainīgs algoritms;
- "x" un rezultātam "f(x)" katru reizi ir jaunas vērtības, rezultāts "f(x)" ir šīs funkcijas jaunais "x" parametrs.
Otrā iespēja: koda dinamika.
- funkcijai "f(x)" ir vairāki algoritmi, kas precizē (analizē) datus;
- datu analīze - viena koda daļa un rekursīvo algoritmu ieviešana, kas veic vēlamo darbību - koda otrā daļa;
- funkcijas "f(x)" rezultāts nav.
Neviens rezultāts nav normāls. Programmēšana nav matemātika, šeit rezultātam nav jābūt skaidri redzamam. Rekursīvā funkcija var vienkārši parsēt vietnes un aizpildīt datu bāzi vai ģenerēt objektus atbilstoši ienākošajai ievadei.
Dati un rekursija
Rekursīvo algoritmu programmēšana nav saistīta ar faktoriāla aprēķināšanu, kurā funkcija katru reizi saņem noteiktu vērtību, kas ir viena lielāka vai mazāka par vienu - ieviešanas iespēja ir atkarīga no izstrādātāja izvēles.
Nav svarīgi, kā faktoriāls "8!",algoritms, kas stingri ievēro šo formulu.
Informācijas apstrāde ir "matemātika" pavisam citā secībā. Rekursīvās funkcijas un algoritmi šeit darbojas ar burtiem, vārdiem, frāzēm, teikumiem un rindkopām. Katrs nākamais līmenis izmanto iepriekšējo.
Ievades datu straume tiek analizēta plašā apstākļu diapazonā, taču analīzes process parasti ir rekursīvs. Nav jēgas rakstīt unikālus algoritmus visiem ievades straumes variantiem. Jābūt vienai funkcionalitātei. Šeit rekursīvie algoritmi ir piemēri, kā izveidot izvades straumi, kas ir piemērota ievadei. Tas nav rekursīvā algoritma izvade, bet tas ir vēlamais un nepieciešamais risinājums.
Abstrakcija, rekursija un OOP
Objektorientētā programmēšana (OOP) un rekursija ir būtiski atšķirīgas vienības, taču tās lieliski papildina viena otru. Abstrakcijai nav nekāda sakara ar rekursiju, bet caur OOP objektīvu tā rada iespēju īstenot kontekstuālo rekursiju.
Piemēram, informācija tiek parsēta un burti, vārdi, frāzes, teikumi un rindkopas tiek izcelti atsevišķi. Acīmredzot izstrādātājs nodrošinās šo piecu veidu objektu gadījumu izveidi un piedāvās rekursīvo algoritmu risinājumu katrā līmenī.
Tikmēr, ja burtu līmenī “nav jēgas meklēt”, tad semantika parādās vārdu līmenī. Var dalīt vārdus darbības vārdos, lietvārdos, apstākļa vārdos, prievārdos… Varat iet tālāk un definēt gadījumus.
Frāžu līmenī semantiku papildina pieturzīmes un loģikavārdu savienojumi. Teikumu līmenī tiek atrasts pilnīgāks semantikas līmenis, un rindkopu var uzskatīt par pilnīgu domu.
Objektorientētā attīstība iepriekš nosaka īpašību un metožu pārmantošanu un ierosina objektu hierarhiju sākt ar pilnīgi abstrakta priekšteča izveidi. Tajā pašā laikā, bez šaubām, katra pēcnācēja analīze būs rekursīva un tehniskā līmenī pārāk daudz neatšķirsies daudzās pozīcijās (burti, vārdi, frāzes un teikumi). Rindkopas, tāpat kā pilnīgas domas, var izcelties no šī saraksta, taču tās nav būtība.
Ir svarīgi, lai lielāko daļu algoritma varētu formulēt abstraktā priekšteča līmenī, precizējot to katra pēcnācēja līmenī ar datiem un metodēm, kas izsauktas no abstraktā līmeņa. Šajā kontekstā abstrakcija paver jaunus apvāršņus rekursijai.
OOP vēsturiskās iezīmes
OOP programmatūras pasaulē ir ienācis divas reizes, lai gan daži eksperti kā jaunu IT tehnoloģiju attīstības kārtu var izcelt mākoņdatošanas un modernu ideju par objektiem un klasēm rašanos.
Jēdzieni "objekts" un "objektīvs" mūsdienu OOP kontekstā parasti tiek attiecināti uz pagājušā gadsimta 50. un 60. gadiem, taču tie ir saistīti ar 1965. gadu un Simula, Lisp, Algol, Smalltalk rašanos..
Tajos laikos programmēšana nebija īpaši attīstīta un nevarēja adekvāti reaģēt uz revolucionārajām koncepcijām. Ideju un programmēšanas stilu cīņa (C / C ++ un Pascal - galvenokārt) vēl bija tālu, un datu bāzes joprojām tika konceptuāli veidotas.
80. gadu beigās un 90. gadu sākumā Paskālā parādījās objekti, un visi atcerējās C / C ++ klases - tas iezīmēja jaunu intereses kārtu par OOP, un tieši tad rīki, galvenokārt programmēšanas valodas, vairs netika izmantoti. atbalsta tikai objektorientētas idejas, bet attiecīgi attīstās.
Protams, ja agrāk rekursīvie algoritmi bija tikai funkcijas, ko izmantoja programmas vispārīgajā kodā, tad tagad rekursija varēja kļūt par objekta (klases) īpašību daļu, kas sniedza interesantas iespējas mantojuma kontekstā.
Mūsdienu OOP iezīme
OOP izstrāde sākotnēji deklarēja objektus (klases) kā datu un īpašību (metožu) kolekcijas. Patiesībā tas bija par datiem, kuriem ir sintakse un nozīme. Taču tad OOP nebija iespējams pasniegt kā reālu objektu pārvaldības rīku.
OOP ir kļuvis par "datordabas" objektu pārvaldības rīku. Skripts, poga, izvēlnes vienums, izvēlnes josla, tags pārlūkprogrammas logā ir objekts. Bet ne mašīna, pārtikas produkts, vārds vai teikums. Reāli objekti ir palikuši ārpus objektorientētās programmēšanas, un datorrīki ir ieguvuši jaunu iemiesojumu.
Populāro programmēšanas valodu atšķirību dēļ ir radušies daudzi OOP dialekti. Semantikas ziņā tie ir praktiski līdzvērtīgi, un to koncentrēšanās uz instrumentālo, nevis lietišķo sfēru ļauj reālu objektu aprakstu iziet tālāk.algoritmus un nodrošināt to starpplatformu un starpvalodu "pastāvēšanu".
Stecks un funkciju izsaukšanas mehānismi
Funkciju (procedūru, algoritmu) izsaukšanas mehānismiem ir nepieciešams nodot datus (parametrus), atgriezt rezultātu un atcerēties operatora adresi, kuram jāsaņem kontrole pēc funkcijas (procedūras) pabeigšanas.
Parasti šim nolūkam tiek izmantots steks, lai gan programmēšanas valodas vai pats izstrādātājs var nodrošināt dažādas vadības nodošanas iespējas. Mūsdienu programmēšana atzīst, ka funkcijas nosaukums var būt ne tikai parametrs: to var izveidot algoritma izpildes laikā. Algoritmu var izveidot arī, izpildot citu algoritmu.
Rekursīvo algoritmu jēdziens, kad uzdevuma veidošanas laikā (izvēloties vēlamo algoritmu) var noteikt to nosaukumus un korpusus, paplašina rekursivitāti ne tikai uz to, kā kaut ko darīt, bet arī uz to, kam tieši tas jādara. dari to. Algoritma izvēle pēc tā "jēgpilnā" nosaukuma ir daudzsološa, taču rada grūtības.
Funkciju kopas rekursivitāte
Nevarētu teikt, ka algoritms ir rekursīvs, kad tas izsauc sevi, un viss. Programmēšana nav dogma, un rekursivitātes jēdziens nav ekskluzīva prasība, lai izsauktu sevi no sava algoritma struktūras.
Praktiskas pielietošanas iespējas ne vienmēr nodrošina tīru risinājumu. Bieži ir jāsagatavo sākotnējie dati un jāanalizē rekursīvā izsaukuma rezultāts visas problēmas (visa algoritma) kontekstā.kopumā.
Patiesībā ne tikai pirms rekursīvās funkcijas izsaukšanas, bet arī pēc tās pabeigšanas var vai vajadzētu izsaukt citu programmu. Ja ar izsaukumu nav īpašu problēmu: rekursīvā funkcija A() izsauc funkciju B(), kas kaut ko dara un izsauc A(), tad uzreiz rodas problēmas ar kontroles atgriešanu. Pabeidzot rekursīvo zvanu, funkcijai A() ir jāsaņem kontrole, lai atkārtoti izsauktu B(), kas to izsauks vēlreiz. Vadības atgriešana, kā tai vajadzētu būt, atpakaļ uz B() ir nepareizs risinājums.
Programmētājs nav ierobežots parametru izvēlē un var tos papildināt ar funkciju nosaukumiem. Citiem vārdiem sakot, ideāls risinājums ir nodot B() nosaukumu uz A() un ļaut pašam A() izsaukt B(). Šajā gadījumā nebūs problēmu ar kontroles atgriešanu, un rekursīvā algoritma ieviešana būs pārskatāmāka.
Izpratne un rekursijas līmenis
Rekursīvo algoritmu izstrādes problēma ir tāda, ka jums ir jāsaprot procesa dinamika. Lietojot rekursiju objektu metodēs, it īpaši abstrakta priekšteča līmenī, rodas problēmas saprast savu algoritmu tā izpildes laika kontekstā.
Šobrīd nav ierobežojumu funkciju ligzdošanas līmenim un steka ietilpībai izsaukuma mehānismos, taču ir izpratnes problēma: kurā brīdī kuru datu līmeni vai vietu vispārējā algoritmā sauc par rekursīvo. funkcija un cik zvana viņa pati.
Esošie atkļūdošanas rīki bieži ir bezspēcīgipastāstiet programmētājam pareizo risinājumu.
Cilpas un rekursija
Tiek uzskatīts, ka cikliskā izpilde ir līdzvērtīga rekursijai. Patiešām, dažos gadījumos rekursīvo algoritmu var ieviest nosacījumu un ciklisko konstrukciju sintaksē.
Tomēr, ja ir skaidra izpratne, ka konkrēta funkcija jārealizē, izmantojot rekursīvu algoritmu, ir jāatsakās no jebkādas cilpas vai nosacījumu priekšrakstu ārējas izmantošanas.
Šeit ir nozīme, ka rekursīvs risinājums funkcijas veidā, kas izmanto sevi, būs pilnīgs, funkcionāli pilnīgs algoritms. Šim algoritmam programmētājam tas būs jāizveido ar piepūli, izprotot algoritma dinamiku, taču tas būs gala risinājums, kuram nav nepieciešama ārēja kontrole.
Jebkāda ārējo nosacījumu un ciklisko operatoru kombinācija neļaus mums attēlot rekursīvo algoritmu kā pilnīgu funkciju.
Recursion Consensus un OOP
Gandrīz visos rekursīvā algoritma izstrādes variantos rodas plāns izstrādāt divus algoritmus. Pirmais algoritms ģenerē nākotnes objektu (instanču) sarakstu, bet otrais algoritms faktiski ir rekursīva funkcija.
Labākais risinājums būtu sakārtot rekursiju kā vienu īpašību (metodi), kas faktiski satur rekursīvo algoritmu, un visu sagatavošanās darbu ievietot objekta konstruktorā.
Rekursīvs algoritms būs pareizais risinājums tikai tad, kad tas darbosiestikai pats, bez ārējas kontroles un vadības. Ārējais algoritms var dot tikai signālu darbam. Šī darba rezultātam vajadzētu būt gaidītajam risinājumam bez ārēja atbalsta.
Rekursijai vienmēr jābūt pilnīgam atsevišķam risinājumam.
Intuitīva izpratne un funkcionālā pilnība
Kad objektorientētā programmēšana kļuva par de facto standartu, kļuva skaidrs, ka, lai kodētu efektīvi, ir jāmaina sava domāšana. Programmētājam algoritma izpildes laikā ir jāpāriet no valodas sintakses un semantikas uz semantikas dinamiku.
Rekursijai raksturīga: to var attiecināt uz visu:
- tīmekļa nokasīšana;
- meklēšanas operācijas;
- teksta informācijas parsēšana;
- MS Word dokumentu lasīšana vai veidošana;
- atzīmju iztveršana vai analīze…
OOP raksturīgs: tas ļauj aprakstīt rekursīvu algoritmu abstrakta priekšteča līmenī, bet paredz, ka tas attiecas uz unikāliem pēcnācējiem, kuriem katram ir sava datu un īpašību palete.
Rekursija ir ideāla, jo prasa tās algoritma funkcionālo pilnīgumu. OOP uzlabo rekursīvā algoritma veiktspēju, nodrošinot tam piekļuvi visiem unikālajiem bērniem.
