Moderno razumijevanje rekurzije: definicija funkcionalnosti i pristup njoj izvana i iz ove funkcionalnosti. Vjeruje se da su rekurziju rodili matematičari: faktorski izračun, beskonačni nizovi, fraktali, kontinuirani razlomci… Međutim, rekurzija se može naći posvuda. Objektivni prirodni zakoni "smatraju" rekurziju kao svoj glavni algoritam i oblik izražavanja (egzistencije) ne toliko objekata materijalnog svijeta, koliko općenito glavnim algoritmom kretanja.
Ljudi različitih specijalnosti u raznim područjima znanosti i tehnologije koriste rekurzivni algoritam f (x), gdje je "x ~/=f (x)". Funkcija koja sama sebe poziva je jako rješenje, ali formiranje i razumijevanje ovog rješenja je, u većini slučajeva, vrlo težak zadatak.
U davna vremena, rekurzija se koristila za povećanje prostora palače. Kroz sustav zrcala usmjerenih jedno na drugo, možete stvoriti zapanjujuće trodimenzionalne prostorne efekte. Ali je li tako lako razumjeti kakopodesiti ova ogledala? Još je teže odrediti gdje se nalazi točka u prostoru, reflektirana kroz nekoliko zrcala.
Rekurzivni, rekurzivni algoritmi: značenje i sintaksa
Problem, koji je formuliran ponavljanjem niza operacija, može se riješiti rekurzivno. Jednostavan algoritam (izračunavanje kvadratne jednadžbe, skripta za popunjavanje web stranice informacijama, čitanje datoteke, slanje poruke…) ne zahtijeva rekurziju.
Glavne razlike algoritma koji omogućuje rekurzivno rješenje:
- postoji algoritam koji se mora izvršiti nekoliko puta;
- algoritam treba podatke koji se mijenjaju svaki put;
- algoritam se ne mora mijenjati svaki put;
- postoji konačni uvjet: algoritam je rekurzivan - nije beskonačan.
Općenito, ne može se tvrditi da je jednokratno izvršenje nužan uvjet za nepostojanje razloga za rekurziju. Također ne možete zahtijevati obvezni konačni uvjet: beskonačne rekurzije imaju svoj vlastiti opseg.
Algoritam je rekurzivan: kada se niz operacija izvodi uzastopno, na podacima koji se svaki put mijenjaju i svaki put daju novi rezultat.
Rekurzijska formula
Matematičko razumijevanje rekurzije i njezinog analoga u programiranju je različito. Matematika, iako postoje znakovi programiranja, ali programiranje je matematika puno višeg reda.
Dobro napisan algoritam je poput ogledala intelekta svog autora. Općenitoformula rekurzije u programiranju je "f(x)", gdje "x ~/=f(x)" ima najmanje dvije interpretacije. Ovdje je "~" sličnost ili odsutnost rezultata, a "=" prisutnost rezultata funkcije.
Prva opcija: dinamika podataka.
- funkcija "f(x)" ima rekurzivni i nepromjenjivi algoritam;
- "x" i rezultat "f(x)" svaki put imaju nove vrijednosti, rezultat "f(x)" je novi parametar "x" ove funkcije.
Druga opcija: dinamika koda.
- funkcija "f(x)" ima nekoliko algoritama koji preciziraju (analiziraju) podatke;
- analiza podataka - jedan dio koda i implementacija rekurzivnih algoritama koji izvode željenu radnju - drugi dio koda;
- rezultat funkcije "f(x)" nije.
Nijedan rezultat nije normalan. Programiranje nije matematika, ovdje rezultat ne mora biti eksplicitno prisutan. Rekurzivna funkcija može jednostavno raščlaniti stranice i popuniti bazu podataka ili instancirati objekte prema dolaznom ulazu.
Podaci i rekurzija
Programiranje rekurzivnih algoritama ne radi se o izračunavanju faktorijala, u kojem funkcija svaki put prima zadanu vrijednost koja je jedna više ili manja od jedan - opcija implementacije ovisi o preferencijama programera.
Nije važno kako je faktorijel "8!",algoritam koji striktno slijedi ovu formulu.
Obrada informacija je "matematika" potpuno drugačijeg reda. Rekurzivne funkcije i algoritmi ovdje rade na slovima, riječima, frazama, rečenicama i odlomcima. Svaka sljedeća razina koristi prethodnu.
Ulazni tok podataka analizira se u širokom rasponu uvjeta, ali je proces analize općenito rekurzivan. Nema smisla pisati jedinstvene algoritme za sve varijante ulaznog toka. Trebala bi postojati jedna funkcionalnost. Ovdje su rekurzivni algoritmi primjeri kako formirati izlazni tok koji je adekvatan ulazu. Ovo nije izlaz rekurzivnog algoritma, ali je željeno i potrebno rješenje.
Apstrakcija, rekurzija i OOP
Objektno orijentirano programiranje (OOP) i rekurzija su fundamentalno različiti entiteti, ali se savršeno nadopunjuju. Apstrakcija nema nikakve veze s rekurzijom, ali kroz leću OOP-a stvara mogućnost implementacije kontekstualne rekurzije.
Na primjer, informacije se raščlanjuju, a slova, riječi, fraze, rečenice i odlomci su posebno istaknuti. Očito, programer će osigurati stvaranje instanci objekata ovih pet vrsta i ponuditi rješenje rekurzivnih algoritama na svakoj razini.
U međuvremenu, ako na razini slova “nema smisla tražiti značenje”, onda se semantika pojavljuje na razini riječi. Riječi možete podijeliti na glagole, imenice, priloge, prijedloge… Možete ići dalje i definirati padeže.
Na razini fraze semantika je dopunjena interpunkcijskim znakovima i logikomkombinacije riječi. Na razini rečenica pronalazi se savršenija razina semantike, a paragraf se može smatrati cjelovitom mišlju.
Objektno orijentirani razvoj unaprijed određuje nasljeđivanje svojstava i metoda i predlaže da se započne hijerarhija objekata stvaranjem potpuno apstraktnog pretka. Istodobno, bez sumnje, analiza svakog potomka bit će rekurzivna i neće se previše razlikovati na tehničkoj razini u mnogim pozicijama (slova, riječi, fraze i rečenice). Paragrafi, poput cjelovitih misli, mogu se izdvojiti s ovog popisa, ali oni nisu bit.
Važno je da se najveći dio algoritma može formulirati na razini apstraktnog pretka, pročišćavajući ga na razini svakog potomka s podacima i metodama pozvanim s apstraktne razine. U ovom kontekstu, apstrakcija otvara nove horizonte za rekurziju.
Povijesne značajke OOP-a
OOP je dvaput došao u svijet softvera, iako neki stručnjaci mogu izdvojiti pojavu računalstva u oblaku i modernih ideja o objektima i klasama kao novi krug u razvoju IT tehnologija.
Izrazi "objekt" i "objektiv" u modernom kontekstu OOP-a obično se pripisuju 50-im i 60-im godinama prošlog stoljeća, ali su povezani s 1965. i pojavom Simula, Lisp, Algol, Smalltalk.
U to vrijeme programiranje nije bilo posebno razvijeno i nije moglo adekvatno odgovoriti na revolucionarne koncepte. Borba ideja i stilova programiranja (C / C ++ i Pascal - uglavnom) bila je još uvijek daleko, a baze podataka su još koncepcijski formirane.
Kasnih 80-ih i ranih 90-ih, objekti su se pojavili u Pascalu i svi su se sjećali klasa u C/C++ - to je označilo novi krug interesa za OOP i tada alati, prvenstveno programski jezici, nisu postali podržavaju samo objektno orijentirane ideje, ali se u skladu s tim razvijaju.
Naravno, ako su raniji rekurzivni algoritmi bili samo funkcije korištene u općem kodu programa, sada bi rekurzija mogla postati dio svojstava objekta (klase), što je pružalo zanimljive mogućnosti u kontekstu nasljeđivanja.
Obilježje modernog OOP-a
Razvoj OOP-a prvobitno je deklarirao objekte (klase) kao zbirke podataka i svojstava (metoda). Zapravo, radilo se o podacima koji imaju sintaksu i značenje. Ali tada nije bilo moguće predstaviti OOP kao alat za upravljanje stvarnim objektima.
OOP je postao alat za upravljanje objektima "prirode računala". Skripta, gumb, stavka izbornika, traka izbornika, oznaka u prozoru preglednika je objekt. Ali ne stroj, prehrambeni proizvod, riječ ili rečenica. Pravi objekti ostali su izvan objektno orijentiranog programiranja, a računalni alati dobili su novu inkarnaciju.
Zbog razlika u popularnim programskim jezicima, pojavili su se mnogi dijalekti OOP-a. U semantičkom smislu, oni su praktički ekvivalentni, a njihov fokus na instrumentalnu sferu, a ne na primijenjenu, omogućuje da se opis stvarnih objekata odmakne dalje odalgoritme i osigurati njihovo "postojanje" na više platformi i na više jezika.
Stogovi i mehanizmi pozivanja funkcija
Mehanizmi za pozivanje funkcija (procedure, algoritmi) zahtijevaju prosljeđivanje podataka (parametara), vraćanje rezultata i pamćenje adrese operatora koji mora primiti kontrolu nakon što funkcija (procedura) završi.
Obično se u tu svrhu koristi stog, iako programski jezici ili sam programer mogu pružiti razne opcije za prijenos kontrole. Suvremeno programiranje priznaje da naziv funkcije može biti ne samo parametar: može se formirati tijekom izvršavanja algoritma. Algoritam se također može stvoriti dok se izvršava drugi algoritam.
Koncept rekurzivnih algoritama, kada se njihova imena i tijela mogu odrediti u trenutku formiranja zadatka (odabir željenog algoritma), proširuje rekurzivnost ne samo na to kako nešto učiniti, već i na to tko bi točno trebao učini to. Odabir algoritma prema njegovom "smislenom" nazivu obećava, ali stvara poteškoće.
Rekurzivnost na skupu funkcija
Ne možete reći da je algoritam rekurzivan kada se poziva i to je to. Programiranje nije dogma, a koncept rekurzivnosti nije isključivi zahtjev za pozivanje sebe iz tijela vlastitog algoritma.
Praktične primjene ne daju uvijek čisto rješenje. Često se moraju pripremiti početni podaci, a rezultat rekurzivnog poziva analizirati u kontekstu cijelog problema (cijelog algoritma) uukupno.
Zapravo, ne samo prije nego što se pozove rekurzivna funkcija, već i nakon što je dovršena, drugi program se može ili treba pozvati. Ako nema posebnih problema s pozivom: rekurzivna funkcija A() poziva funkciju B(), koja nešto radi i poziva A(), tada odmah dolazi do problema s vraćanjem kontrole. Nakon što je dovršila rekurzivni poziv, funkcija A() mora primiti kontrolu kako bi ponovno pozvala B(), koji će je ponovno pozvati. Vraćanje kontrole kako bi trebala biti na stogu natrag na B() je pogrešno rješenje.
Programer nije ograničen u izboru parametara i može ih dopuniti nazivima funkcija. Drugim riječima, idealno rješenje je proslijediti ime B() u A() i dopustiti da A() sam pozove B(). U tom slučaju neće biti problema s vraćanjem kontrole, a implementacija rekurzivnog algoritma bit će transparentnija.
Razumijevanje i razina rekurzije
Problem s razvojem rekurzivnih algoritama je taj što trebate razumjeti dinamiku procesa. Kada se koristi rekurzija u objektnim metodama, posebno na razini apstraktnog pretka, postoji problem razumijevanja vlastitog algoritma u kontekstu vremena njegovog izvršavanja.
Trenutno ne postoje ograničenja u pogledu razine ugniježđenja funkcija i kapaciteta steka u mehanizmima poziva, ali postoji problem razumijevanja: u kojem trenutku koja razina podataka ili koje mjesto u općem algoritmu zvanom rekurzivna funkciju i na kojem broju poziva sama je.
Postojeći alati za otklanjanje pogrešaka često su nemoćnireci programeru pravo rješenje.
Petlje i rekurzija
Smatra se da je cikličko izvršenje ekvivalentno rekurziji. Doista, u nekim slučajevima, rekurzivni se algoritam može implementirati u sintaksi uvjetnih i cikličkih konstrukcija.
Međutim, ako postoji jasno razumijevanje da se određena funkcija mora implementirati putem rekurzivnog algoritma, svaka vanjska upotreba petlje ili uvjetnih izraza treba biti napuštena.
Ovdje znači da će rekurzivno rješenje u obliku funkcije koja sama sebe koristi biti potpuni, funkcionalno potpuni algoritam. Ovaj algoritam će zahtijevati od programera da ga stvori s trudom, razumijevajući dinamiku algoritma, ali će to biti konačno rješenje koje ne zahtijeva vanjsku kontrolu.
Bilo koja kombinacija vanjskih uvjetnih i cikličkih operatora neće nam dopustiti da rekurzivni algoritam predstavimo kao cjelovitu funkciju.
Rekurzivni konsenzus i OOP
U gotovo svim varijantama razvoja rekurzivnog algoritma, nameće se plan razvoja dva algoritma. Prvi algoritam generira popis budućih objekata (instanci), a drugi algoritam je zapravo rekurzivna funkcija.
Najbolje rješenje bilo bi organizirati rekurziju kao jedno svojstvo (metodu) koje zapravo sadrži rekurzivni algoritam i staviti sav pripremni rad u konstruktor objekta.
Rekurzivni algoritam će biti pravo rješenje samo kada radisamo sam, bez vanjske kontrole i upravljanja. Vanjski algoritam može dati samo signal za rad. Rezultat ovog rada trebao bi biti očekivano rješenje, bez vanjske podrške.
Rekurzija bi uvijek trebala biti potpuno samostalno rješenje.
Intuitivno razumijevanje i funkcionalna potpunost
Kada je objektno orijentirano programiranje postalo de facto standard, postalo je očito da za učinkovito kodiranje morate promijeniti vlastito razmišljanje. Programer mora prijeći sa sintakse i semantike jezika na dinamiku semantike tijekom izvođenja algoritma.
Obilježje rekurzije: može se primijeniti na sve:
- struganje weba;
- tražne operacije;
- raščlanjivanje tekstualnih informacija;
- čitanje ili stvaranje MS Word dokumenata;
- uzorkovanje ili analiza oznaka…
Obilježje OOP-a: omogućuje opisivanje rekurzivnog algoritma na razini apstraktnog pretka, ali predviđa da se odnosi na jedinstvene potomke, od kojih svaki ima svoju paletu podataka i svojstava.
Rekurzija je idealna jer zahtijeva funkcionalnu potpunost svog algoritma. OOP poboljšava performanse rekurzivnog algoritma dajući mu pristup svoj jedinstvenoj djeci.
