Rekurzija u logici. Repna rekurzija i petlja

Rekurzija je svojstvo objekta da oponaša sam sebe. Objekt je rekurzivan ako njegovi dijelovi izgledaju isto kao cijeli objekt. Rekurzija se vrlo široko koristi u matematici i programiranju:

• strukture podataka:
  • graf (osobito stabla i liste) može se promatrati kao skup jednog čvora i podgrafa (manji graf);
  • niz se sastoji od prvog znaka i podniza (manjeg niza);
• uzorci dizajna, npr. Objekt dekorater može uključivati ​​druge objekte koji su također dekorateri. McColm Smith je detaljno proučavao rekurzivne obrasce, ističući opći obrazac dizajna u svojoj knjizi - Recursion;
• rekurzivne funkcije (algoritmi) pozivaju same sebe.

Članak je posvećen analizi složenosti rekurzivnih algoritama, dane su potrebne matematičke informacije i razmotreni primjeri. Dodatno je opisana mogućnost zamjene rekurzije petljom, repnom rekurzijom.

Primjeri rekurzivnih algoritama

Rekurzivni algoritam uvijek rastavlja problem na dijelove koji su po strukturi isti kao izvorni problem, ali su jednostavniji. Za rješavanje podproblema funkcija se poziva rekurzivno, a njihovi se rezultati na neki način kombiniraju. Do podjele zadatka dolazi samo kada se ne može odmah riješiti (presložen je).

Na primjer, zadatak obrade niza često se može svesti na obradu njegovih dijelova. Podjela na dijelove provodi se sve dok ne postanu elementarni, tj. dovoljno jednostavan za dobivanje rezultata bez daljnjeg pojednostavljivanja.

Pronalaženje elementa niza

Početak; traži(niz, početak, kraj, element) ; traži element s vrijednosnim elementom u nizu između početnog i završnog indeksa if begin > end result:= false; element nije pronađen inače ako niz = rezultat elementa:= istina; inače pronađen element rezultat:= traženje(niz, početak+1, kraj, element) kraj; vratiti rezultat

Algoritam dijeli originalni niz na dva dijela - prvi element i niz preostalih elemenata. Postoje dva jednostavna slučaja kada razdvajanje nije potrebno - svi elementi su obrađeni ili je prvi element onaj koji se traži.

U algoritmu pretraživanja niz bi se mogao podijeliti drugačije (npr. na pola), ali to ne bi utjecalo na učinkovitost. Ako je niz sortiran, preporučljivo je podijeliti ga na pola, jer U svakom koraku, količina obrađenih podataka može se smanjiti za pola.

Binarno pretraživanje u nizu

Binarno pretraživanje izvodi se na sortiranom nizu. U svakom koraku traženi element se uspoređuje s vrijednošću koja se nalazi u sredini niza. Ovisno o rezultatima usporedbe, može se "odbaciti" lijeva ili desna strana.

Početak; binarno_pretraživanje(niz, početak, kraj, element) ; traži element s elementom vrijednosti ; u nizu poredanom uzlaznim redoslijedom niz; između indeksa početak i kraj ako početak > kraj kraj; return false - element nije pronađen mid:= (kraj + početak) div 2; izračunavanje indeksa elementa u sredini razmatranog dijela niza ako je niz = kraj elementa; return true (element pronađen) if niz< element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Izračunavanje Fibonaccijevih brojeva

Fibonaccijevi brojevi određeni su rekurentnim izrazom, tj. tako da je izračun elementa koji se izražava iz prethodnih elemenata: \(F_0 = 0, F_1 ​​​​= 1, F_n = F_(n-1) + F_(n-2), n > 2\).

Početak; fibonacci(broj) ako je broj = 0 kraj; vrati 0 ako je broj = 1 kraj; return 1 fib_1:= fibonacci(broj-1) fib_2:= fibonacci(broj-2) rezultat:= fib_1 + fib_2 kraj; vratiti rezultat

Brzo sortiranje

U svakom koraku algoritam za brzo sortiranje odabire jedan od elemenata (referencu) iu odnosu na njega dijeli niz na dva dijela koji se rekurzivno obrađuju. Elementi manji od nosivog postavljaju se u jedan dio, a ostali u drugi.

Dijagram toka algoritma za brzo sortiranje

Sortiranje spajanjem

Osnova algoritma za sortiranje spajanjem je sposobnost brzog kombiniranja uređenih nizova (ili popisa) tako da rezultat bude uređen. Algoritam nasumično dijeli izvorni niz na dva dijela (obično na pola), rekurzivno ih sortira i kombinira rezultat. Dijeljenje se događa sve dok je veličina niza veća od jedan, jer prazan niz i niz od jednog elementa uvijek su sortirani.

Blok dijagram sortiranja spajanjem

U svakom koraku spajanja odabire se prvi neobrađeni element s obje liste. Elementi se uspoređuju, a najmanji se dodaje rezultatu i označava kao obrađen. Spajanje se događa sve dok jedan od popisa ne bude prazan.

Početak; spoji(Niz1, Veličina1, Niz2, Veličina2) ; originalni nizovi su poredani; rezultat je uređen niz duljine Veličina1+Veličina2 i:= 0, j:= 0 vječna_petlja ako je i >= Veličina1 dodaj elemente od j do Veličina2 niza Niz2 na kraj rezultata izađi iz petlje ako je j >= Veličina2 dodajte elemente od i do Size1 niza Array1 na kraj rezultata izađite iz petlje if Array1[i]< Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Niz2[j]) rezultat := Niz2[j] j:= j + 1 kraj; vratiti rezultat

Analiza rekurzivnih algoritama

Kada se izračuna složenost iteracija i njihov broj u najgorem, najboljem i prosječnom slučaju. Međutim, ovaj pristup neće biti moguće primijeniti na rekurzivnu funkciju jer rezultat će biti relacija ponavljanja. Na primjer, za funkciju za traženje elementa u nizu:

\(
\početak(jednadžba*)
T^(pretraživanje)_n = \početak(slučajevi)
\mathcal(O)(1) \quad &\text($n = 0$) \\
\mathcal(O)(1) + \mathcal(O)(T^(pretraži)_(n-1)) \quad &\text($n > 0$)
\kraj(slučajevi)
\end(jednadžba*)
\)

Rekurentne relacije nam ne dopuštaju procjenu složenosti – ne možemo ih jednostavno usporediti, a time ni učinkovitost odgovarajućih algoritama. Potrebno je dobiti formulu koja opisuje rekurentnu relaciju - univerzalni način za to je odabrati formulu metodom supstitucije, a zatim dokazati podudarnost formule s relacijom metodom matematičke indukcije.

Metoda supstitucije (iteracije).

Sastoji se od sekvencijalne zamjene ponavljajućeg dijela u izrazu da bi se dobili novi izrazi. Zamjena se vrši sve dok nije moguće shvatiti opći princip i izraziti ga u obliku neponavljajuće formule. Na primjer, za traženje elementa u nizu:

\(
T^(pretraživanje)_n = \mathcal(O)(1) + \mathcal(O)(T^(pretraživanje)_(n-1)) =
2\puta\mathcal(O)(1) + \mathcal(O)(T^(pretraži)_(n-2)) =
3\puta\mathcal(O)(1) + \mathcal(O)(T^(pretraži)_(n-3))
\)

Možemo pretpostaviti da je \(T^(pretraživanje)_n = T^(pretraživanje)_(n-k) + k\times\mathcal(O)(1)\), ali tada \(T^(pretraživanje)_n = T^ (pretraživanje)_(0) + n\puta\mathcal(O)(1) = \mathcal(O)(n)\).

Izveli smo formulu, ali prvi korak sadrži pretpostavku, tj. nema dokaza o podudarnosti formule s rekurentnim izrazom - metoda matematičke indukcije omogućuje nam dobivanje dokaza.

Metoda matematičke indukcije

Omogućuje vam da dokažete istinitost određene izjave (\(P_n\)), sastoji se od dva koraka:

1. dokaz izjave za jedan ili više posebnih slučajeva \(P_0, P_1, …\);
2. iz istinitosti \(P_n\) (induktivna hipoteza) i posebnih slučajeva izvodi se dokaz \(P_(n+1)\).

Dokažimo točnost pretpostavke napravljene prilikom procjene složenosti funkcije pretraživanja (\(T^(search)_n = (n+1)\times\mathcal(O)(1)\)):

1. \(T^(search)_(1) = 2\times\mathcal(O)(1)\) je istina iz uvjeta (može se zamijeniti u originalnu rekurentnu formulu);
2. pretpostavimo istinu \(T^(search)_n = (n+1)\times\mathcal(O)(1)\);
3. moramo dokazati da je \(T^(pretraživanje)_(n+1) = ((n+1)+1)\times\mathcal(O)(1) = (n+2)\times\mathcal(O ) (1)\);
   1. zamijenimo \(n+1\) u relaciju ponavljanja: \(T^(pretraživanje)_(n+1) = \mathcal(O)(1) + T^(pretraživanje)_n\);
   2. na desnoj strani izraza moguće je izvršiti zamjenu na temelju induktivne hipoteze: \(T^(pretraživanje)_(n+1) = \mathcal(O)(1) + (n+1)\puta \mathcal(O)(1) = (n+2)\puta\mathcal(O)(1)\);
   3. izjava je dokazana.

Često je takav dokaz prilično naporan proces, ali je još teže identificirati obrazac korištenjem metode zamjene. U tom smislu koristi se tzv. opća metoda.

Opća (osnovna) metoda rješavanja rekurentnih relacija

Opća metoda nije univerzalna; na primjer, ne može se koristiti za procjenu složenosti gornjeg algoritma za izračun Fibonaccijevih brojeva. Međutim, primjenjuje se na sve slučajeve korištenja pristupa zavadi pa vladaj:

\(T_n = a\cdot T(\frac(n)(b))+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \zasve n\).

Jednadžbe ovog tipa dobivaju se ako se izvorni problem podijeli na podzadatke, od kojih svaki obrađuje \(\frac(n)(b)\) elemente. \(f_n\) je složenost operacija dijeljenja problema na dijelove i kombiniranja rješenja. Uz vrstu odnosa, opća metoda nameće ograničenja na funkciju \(f_n\), razlikujući tri slučaja:

1. \(\postoji \varepsilon > 0: f_n = \mathcal(O)(n^(\log_b a - \varepsilon)) \Rightarrow T_n = \Theta(n^(\log_b a))\);
2. \(f_n = \Theta(n^(\log_b a)) \Rightarrow T_n = \Theta(n^(\log_b a) \cdot \log n)\);
3. \(\postoji \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)\).

Točnost iskaza za svaki slučaj dokazuje se formalno. Zadatak analize rekurzivnog algoritma sada se svodi na određivanje slučaja glavnog teorema kojemu odgovara relacija ponavljanja.

Analiza algoritma binarnog pretraživanja

Algoritam dijeli izvorne podatke na 2 dijela (b = 2), ali obrađuje samo jedan od njih (a = 1), \(f_n = 1\). \(n^(\log_b a) = n^(\log_2 1) = n^0 = 1\). Funkcija podjele zadatka i sređivanja rezultata raste istom brzinom kao \(n^(\log_b a)\), što znači da je potrebno koristiti drugi slučaj teorema:

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

Analiza algoritma pretraživanja

Rekurzivna funkcija dijeli izvorni problem na jedan podzadatak (a = 1), podaci se dijele na jedan dio (b = 1). Ne možemo koristiti glavni teorem za analizu ovog algoritma, jer uvjet \(b > 1\) nije zadovoljen.

Za provođenje analize može se koristiti metoda zamjene ili sljedeće razmišljanje: svaki rekurzivni poziv smanjuje dimenziju ulaznih podataka za jedan, što znači da će biti ukupno n dijelova, od kojih svaki ima složenost \(\mathcal( O)(1)\). Tada je \(T^(pretraži)_n = n \cdot \mathcal(O)(1) = \mathcal(O)(n)\).

Analiza algoritma sortiranja spajanjem

Izvorni podaci su podijeljeni u dva dijela, od kojih se oba obrađuju: \(a = 2, b = 2, n^(\log_b a) = n\).

Prilikom obrade liste, dijeljenje može zahtijevati \(\Theta(n)\) operacije, dok je za niz potrebno konstantno vrijeme (\(\Theta(1)\)). Međutim, u svakom slučaju, \(\Theta(n)\) će se potrošiti na povezivanje rezultata, tako da \(f_n = n\).

Koristi se drugi slučaj teorema: \(T^(mergeSort)_n = \Theta(n^(\log_b a) \cdot \log n) = \Theta(n \cdot \log n)\).

Analiza radnog intenziteta brzog sortiranja

U najboljem slučaju, izvorni niz je podijeljen na dva dijela, od kojih svaki sadrži polovicu izvornih podataka. Podjela će zahtijevati n operacija. Složenost sastavljanja rezultata ovisi o korištenim podatkovnim strukturama - za niz \(\mathcal(O)(n)\), za povezani popis \(\mathcal(O)(1)\). \(a = 2, b = 2, f_n = b\), što znači da će složenost algoritma biti ista kao kod sortiranja spajanjem: \(T^(quickSort)_n = \mathcal(O)(n \ cdot \log n)\ ).

Međutim, u najgorem slučaju, minimalni ili maksimalni element niza bit će stalno odabran kao referenca. Zatim \(b = 1\), što znači da opet ne možemo koristiti glavni teorem. Međutim, znamo da će u ovom slučaju biti napravljeno n rekurzivnih poziva, od kojih svaki dijeli niz na dijelove (\(\mathcal(O)(n)\)) - što znači složenost algoritma \(T^( brzo sortiranje)_n = \mathcal(O)(n^2)\).

Pri analizi brzog sortiranja supstitucijom, također bi se morali odvojeno razmotriti najbolji i najgori slučajevi.

Repna rekurzija i petlja

Analiza složenosti rekurzivnih funkcija mnogo je složenija od procjene petlji, ali glavni razlog zašto su petlje poželjnije je visoka cijena pozivanja funkcije.

Nakon poziva kontrola se prenosi drugu funkciju. Za prijenos kontrole dovoljno je promijeniti vrijednost registra programskog brojača, u koji procesor pohranjuje broj instrukcije koja se trenutno izvršava - na isti način se kontrola prenosi na grane algoritma, na primjer, kada se koristi uvjetni operator. Međutim, poziv nije samo prijenos kontrole, jer nakon što pozvana funkcija završi svoje izračune, mora vratiti kontrolu do točke gdje je poziv napravljen, te također vratiti vrijednosti lokalnih varijabli koje su tamo postojale prije poziva.

Da bi se implementiralo ovo ponašanje, koristi se stog (stog poziva) - u njega se stavlja broj naredbe za vraćanje i informacije o lokalnim varijablama. Stog nije beskonačan, tako da rekurzivni algoritmi mogu dovesti do prekoračenja stoga, au svakom slučaju, rad s njim može potrajati značajno vrijeme.

U nekim slučajevima, vrlo je lako zamijeniti rekurzivnu funkciju petljom, na primjer, onima o kojima smo raspravljali gore. U nekim slučajevima potreban je kreativniji pristup, ali najčešće je takva zamjena moguća. Dodatno, postoji posebna vrsta rekurzije gdje je rekurzivni poziv posljednja operacija koju izvodi funkcija. Očito, u ovom slučaju funkcija koja poziva neće ni na koji način promijeniti rezultat, što znači da nema smisla vraćati kontrolu. Takav rekurzija se naziva repna rekurzija— kompajleri ga automatski zamjenjuju petljom.

Često pomaže napraviti rekurziju repa metoda akumulativnog parametra, koji se sastoji od dodavanja funkcije dodatnog akumulatorskog argumenta u kojem se akumulira rezultat. Funkcija izvodi izračune na akumulatoru prije rekurzivnog poziva. Dobar primjer korištenja ove tehnike je faktorijelna funkcija:
\(činjenica_n = n \cdot činjenica(n-1) \\
činjenica_3 = 3 \cdot činjenica_2 = 3 \cdot (2 \cdot činjenica_1) = 3\cdot (2 \cdot (1 \cdot činjenica_0)) = 6 \\
činjenica_n = činjenicaRep_(n, 1) \\
\\
factTail_(n, akumulator) = factTail(n-1, akumulator \cdot n)\\
factTail_(3, 1) = factTail_(2, 3) = factTail_(1, 6) = factTail_(0, 6) = 6
\)

Kao složeniji primjer, razmotrite funkciju za izračunavanje Fibonaccijevih brojeva. Glavna funkcija poziva pomoćnu funkciju koja koristi metodu skupljajućeg parametra, prosljeđujući početnu vrijednost iteratora i dva akumulatora (dva prethodna Fibonaccijeva broja) kao argumente.

Početak; fibonacci(broj) return fibonacci(broj, 1, 1, 0) kraj početak; fibonacci(broj, iterator, fib1, fib2) if iterator == broj return fib1 return fibonacci(broj, iterator + 1, fib1 + fib2, fib1) kraj

Funkcija s akumulirajućim parametrom vraća akumulirani rezultat ako je izračunat navedeni broj brojeva, u protivnom povećava brojač, izračunava novi Fibonaccijev broj i vrši rekurzivni poziv. Optimizirajući prevoditelji mogu otkriti da se rezultat poziva funkcije prenosi nepromijenjen na izlaz funkcije i zamijeniti ga petljom. Ova tehnika je posebno relevantna u funkcionalnim i logičkim programskim jezicima, jer u njima programer ne može eksplicitno koristiti cikličke konstrukcije.

Književnost

1. Qt poslužitelj s više niti. Bazen niti. Uzorak dekoratera [Elektronički izvor] - način pristupa: https://site/archives/1390. Datum pristupa: 21.02.2015.
2. Jason McColm Smith: Trans. s engleskog - M.: LLC “I.D. Williams”, 2013. - 304 str.
3. Skiena S. Algoritmi. Development Guide.-2nd ed.: trans. s engleskog-SPb.: BHV-Petersburg, 2011.-720 str.: ilustr.
4. Vasiliev V. S. Analiza složenosti algoritama. Primjeri [Elektronički izvor] - način pristupa: https://site/archives/1660. Datum pristupa: 21.02.2015.
5. A. Aho, J. Hopcroft, J. Ullman, Strukture podataka i algoritmi, M., Williams, 2007.
6. Miller, R. Sekvencijalni i paralelni algoritmi: opći pristup / R. Miller, L. Boxer; traka s engleskog - M.: BINOM. Laboratorij znanja, 2006. - 406 str.
7. Sergievsky G.M. Funkcionalno i logičko programiranje: udžbenik. priručnik za studente viših razreda udžbenik ustanove / G.M. Sergievsky, N.G. Volčenkov. - M.: Izdavački centar "Akademija", 2010.- 320 str.

Od latinskog recursio (povratak). Općenito, ovo je naziv dat procesu ponavljanja elemenata na "sebi sličan način".

Upečatljiv primjer rekurzije su lutke. Rekurzivna definicija: "lutka za gniježđenje je odvojiva šuplja drvena lutka koja sadrži manju lutku." Ovo je rekurzija na ruskom. I da nije bilo granice sposobnosti majstora, idealna matrjoška bi zašla duboko u sebe do atomske razine. Ili još dublje. Lefty jednostavno nije imao dovoljno jak nišan. Gornja granica također je teoretski neograničena, ali baobabi odgovarajuće veličine ne rastu na našem planetu. Općenito, iz tehničkih razloga, rekurzija mora biti konačna.

U programiranju (kao i u matematici), rekurzija je proces pozivanja same funkcije (izravna rekurzija) ili pozivanja funkcije B iz funkcije A, koja zauzvrat sadrži poziv funkciji A (neizravna ili međusobna rekurzija). Naravno, rekurzivni pozivi moraju imati zadovoljavajući izlazni uvjet, inače će program visjeti, kao u beskonačnoj petlji - ali, za razliku od beskonačne petlje, beskonačna rekurzija će se srušiti na preljevu stoga.

Primjer rekurzije

Najneugodniji primjer rekurzije u matematičkom programiranju je izračun faktorijela. Ne mijenjajmo naše slavne tradicije. Za one koji još nisu: N! (faktorijel N) je umnožak svih prirodnih brojeva od jedan do N (faktorijel nule je 1).
Možete glupo množiti brojeve od 1 do N u petlji. Ili možete izgraditi funkciju factorial(n), koja će sadržavati uvjet i poziv sebi. Ako je n jednako jedan, tada funkcija vraća vrijednost 1, inače vraća vrijednost n pomnoženu s faktorijelom (n-1).
Skiciranje u PHP-u

Funkcija factorial($n) ( if ($n == 1) ( return 1; ) else ( return intval($n * factorial($n - 1)); ) )

Praktične primjene rekurzije

"Pa, zašto je ovo potrebno ovdje?" – pitat će nas nestrpljivi mladi čitatelj – “Znanstvene gluposti, zamajavanja, kojekakvi faktorijeli... Ali, praktično, čemu ova rekurzija?”
“Na crno oko web programiranja”, odgovorit ćemo bez oklijevanja. I to ćemo odmah opravdati.

Zapravo, postoji mnogo više upotreba rekurzije u web programiranju nego što se čini. Zato što je rekurzija, možda, jedini način da se obiđe bilo koja struktura stabla kada niti njegova veličina niti dubina ugniježđenja nisu unaprijed poznati. Usput, konstruiranje i prelaženje grafova također se ne može učiniti bez njega. Ovo je klasika, gospodo - pokušajte na neki drugi način tražiti potrebne datoteke u Unix stablu imenika i odmah će vam biti jasno da bez rekurzije nećete stići nikamo.

Pokušajte bez toga izgradnjom karte web mjesta s hijerarhijskom strukturom odjeljaka u obliku ugniježđenih popisa. Radije biste se objesili nego izgradili ako unaprijed ne znate točno na koliko je razina ograničena dubina gniježđenja. Čak i ako znate, ali pokušate bez rekurzije, tada ćete umjesto jednostavne, transparentne i sigurne funkcije izgraditi glomaznu softversku „policu na štakama“. A kada završite i obrišete znojno čelo, sinut će vam sumorna životna istina: ako promijenite dubinu ugniježđivanja, vaša struktura za širenje odmah će prestati ispravno raditi. Stoga je malo vjerojatno da ćete ga moći koristiti bilo gdje drugdje.

Rekurzija u tražilicama

Da točno. Tražilice također nemaju kamo pobjeći od rekurzije. Budući da se uvriježio običaj da se autoritet stranice (dokumenta) mjeri brojem poveznica, tražilice su upale u rekurzivnu zamku i pustile ih da u njoj zauvijek lutaju (to je iskrena dobra želja autora). “Težina” poveznice web mjesta sastoji se od malih dijelova “težine” svih onih koji vode na nju. Da biste izračunali ovu težinu za A, na koju referenciraju B, C i D, morate izračunati njihovu težinu, koju zauzvrat prenose razni drugi, čiju težinu također treba izračunati... i tako dalje u cijeloj Mreži uzeti u obzir u tražilici. Potpuno rekurzivan problem. I kažete da je to potpuna teorija. Najstvarnija praksa.

Googleov rekurzivni PageRank

Tvorci Googlea davno su objavili svoj osnovni algoritam za izračunavanje PageRanka. I koliko god se od tada mijenjao, koliko god poboljšanja dodano, osnova ostaje ista. Ne postoji način da znamo koliko PageRank stranica B prosljeđuje kao vezu na stranicu A dok ne prebrojimo koji je PageRank stranica B dobila od svih drugih stranica koje su povezivale na nju, a to se ne može znati dok ne prebrojimo PageRank tih stranica... hoćemo li nastaviti? Vjerojatno više nije potrebno. Ponovno je njezino veličanstvo Rekurzija .

Enciklopedijski YouTube

• 1 / 5

  U matematici, rekurzija ima veze s metodom definiranja funkcija i nizova brojeva: rekurzivno definiran funkcija određuje svoju vrijednost pozivajući samu sebe s drugim argumentima. U ovom slučaju moguće su dvije opcije:

  e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f (2) (\displaystyle e=2+(\cfrac (2)(2+(\cfrac (3)(3+(\cfrac ( 4)(4+\ltočke ))))))\;=2+f(2)), Gdje f (n) = n n + f (n + 1) (\displaystyle f(n)=(\cfrac (n)(n+f(n+1)))) Izravan izračun pomoću gornje formule izazvat će beskonačnu rekurziju, ali se može dokazati da vrijednost f(n) teži jedinici kako n raste (dakle, unatoč beskonačnosti niza, vrijednost Eulerovog broja je konačna ). Da bi se približno izračunala vrijednost e, dovoljno je umjetno ograničiti dubinu rekurzije na neki unaprijed određeni broj i, kada se to postigne, koristiti ga umjesto f (n) (\displaystyle f(n)) jedinica.

  Drugi primjer rekurzije u matematici je niz brojeva zadan rekurentnom formulom, kada se svaki sljedeći član niza izračunava kao rezultat funkcije n prethodnih članova. Dakle, korištenjem konačnog izraza (koji je kombinacija rekurentne formule i skupa vrijednosti za prvih n članova niza), može se dati definicija beskonačnog niza.

  Struct element_of_list ( element_of_list * next ; /* pokazivač na sljedeći element istog tipa */ int podaci; /* neki podaci */ );

  Budući da se beskonačan broj ugniježđenih objekata ne može smjestiti u konačnu memoriju, u stvarnosti su takve rekurzivno definirane strukture uvijek konačne. U završne (terminalne) ćelije obično se upisuju prazni pokazivači, koji su ujedno i zastavice koje programu koji obrađuje strukturu pokazuju da je došao do njegovog kraja.

  Rekurzija je prilično čest fenomen koji se ne pojavljuje samo u područjima znanosti, već iu svakodnevnom životu. Na primjer, Droste efekt, trokut Sierpinskog, itd. Najlakši način da vidite rekurziju je usmjeriti web kameru na zaslon monitora računala, naravno, nakon što ste ga prethodno uključili. Dakle, kamera će snimati sliku ekrana računala i prikazati je na ovom ekranu, to će biti nešto poput zatvorene petlje. Kao rezultat toga, promatrat ćemo nešto slično tunelu.

  U programiranju je rekurzija usko povezana s funkcijama, točnije, zahvaljujući funkcijama u programiranju postoji nešto što se zove rekurzija ili rekurzivna funkcija. Jednostavnim riječima, rekurzija je definiranje dijela funkcije (metode) kroz samu sebe, odnosno to je funkcija koja poziva samu sebe, izravno (u svom tijelu) ili neizravno (kroz drugu funkciju). Tipični rekurzivni problemi su: nalaženje n!, Fibonaccijevi brojevi. Već smo rješavali takve probleme, ali korištenjem petlji, odnosno iterativno. Općenito govoreći, sve što se rješava iterativno može se riješiti i rekurzivno, odnosno pomoću rekurzivne funkcije. Cijelo rješenje se svodi na rješavanje glavnog ili, kako ga još zovu, osnovnog slučaja. Postoji nešto poput koraka rekurzije ili rekurzivnog poziva. U slučaju kada se poziva rekurzivna funkcija za rješavanje složenog problema (ne osnovnog slučaja), izvodi se niz rekurzivnih poziva ili koraka kako bi se problem sveo na jednostavniji. I tako dok ne dobijemo osnovno rješenje. Razvijmo program koji deklarira rekurzivnu funkciju koja izračunava 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; }

  // kod Code::Blocks

  // Dev-C++ kod

  // factorial.cpp: Definira ulaznu točku za konzolnu aplikaciju. #uključi korištenje imenskog prostora std; unsigned long int factorial(unsigned long int); // prototip rekurzivne funkcije int i = 1; // inicijaliziranje globalne varijable za brojanje broja rekurzivnih poziva unsigned long int rezultat; // globalna varijabla za pohranjivanje vraćenog rezultata rekurzivne funkcije int main(int argc, char* argv) ( int n; // lokalna varijabla za prosljeđivanje unesenog broja s tipkovnice cout<< "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; }

  U redovi 7, 9, 21 Tip podataka deklariran je kao unsigned long int, budući da vrijednost faktorijela raste vrlo brzo, na primjer, već 10! = 3 628 800. Ako veličina tipa podataka nije dovoljna, tada će rezultat biti potpuno netočna vrijednost. Kod deklarira više operatora nego što je potrebno za pronalaženje n!. To je učinjeno tako da nakon pokretanja program pokaže što se događa na svakom koraku rekurzivnih poziva. Obratite pažnju na istaknute retke koda, redovi 23, 24, 28 je rekurzivno rješenje za n!. Redci 23, 24 su osnovno rješenje rekurzivne funkcije, odnosno čim vrijednost u varijabli fće biti jednak 1 ili 0 (pošto znamo da je 1! = 1 i 0! = 1), rekurzivni pozivi će prestati, a vrijednosti će se početi vraćati za svaki rekurzivni poziv. Kada se vrati vrijednost za prvi rekurzivni poziv, program će vratiti vrijednost izračunatog faktorijela. U linija 28 funkcija factorial() poziva samu sebe, ali njen argument je jedan manji. Argument se smanjuje svaki put kako bi se došlo do određenog rješenja. Rezultat programa (vidi sliku 1).

  Unesite n!: 5 Korak 1 Rezultat= 0 Korak 2 Rezultat= 0 Korak 3 Rezultat= 0 Korak 4 Rezultat= 0 5!=120

  Slika 1 - Rekurzija u C++

  Na temelju rezultata programa svaki korak je jasno vidljiv i rezultat na svakom koraku je nula, osim zadnjeg rekurzivnog poziva. Bilo je potrebno izračunati pet faktorijela. Program je napravio četiri rekurzivna poziva, au petom pozivu pronađen je osnovni slučaj. I kad je program imao rješenje za osnovni slučaj, riješio je prethodne korake i ispisao ukupni rezultat. Na slici 1 vidljiva su samo četiri koraka jer je u petom koraku pronađeno parcijalno rješenje, koje je u konačnici vratilo konačno rješenje, tj. 120. Slika 2 prikazuje rekurzivnu shemu izračuna 5!. Dijagram jasno pokazuje da se prvi rezultat vraća kada se dođe do određenog rješenja, ali ne odmah, nakon svakog rekurzivnog poziva.

  Slika 2 - Rekurzija u C++

  Dakle, pronaći 5! treba znati 4! i pomnožite ga s 5; 4! = 4 * 3! i tako dalje. Prema shemi prikazanoj na slici 2, izračun će se svesti na pronalaženje posebnog slučaja, to jest 1!, nakon čega će se vrijednosti vraćati svakom rekurzivnom pozivu redom. Zadnji rekurzivni poziv vratit će vrijednost 5!.

  Preradimo program za nalaženje faktorijela tako da dobijemo tablicu faktorijela. Da bismo to učinili, deklarirat ćemo for petlju u kojoj ćemo pozvati rekurzivnu funkciju.

  korištenje imenskog prostora std; unsigned long int factorial(unsigned long int); // prototip rekurzivne funkcije int i = 1; // inicijaliziranje globalne varijable za brojanje broja rekurzivnih poziva unsigned long int rezultat; // globalna varijabla za pohranjivanje vraćenog rezultata rekurzivne funkcije int main(int argc, char* argv) ( int n; // lokalna varijabla za prosljeđivanje unesenog broja s tipkovnice cout<< "Enter n!: "; cin >>n; za (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; za (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) <

  // kod Code::Blocks

  // Dev-C++ kod

  // fibonacci.cpp: definira ulaznu točku za konzolnu aplikaciju. #uključi // biblioteka za formatiranje informacija prikazanih na ekranu #include korištenje imenskog prostora std; unsigned long fibonacci(unsigned long); // prototip rekurzivne funkcije za pretraživanje brojeva iz Fibonaccijevog niza int main(int argc, char* argv) ( unsigned long entered_number; cout<< "Enter number from the Fibonacci series: "; cin >> uneseni_broj; za (int brojač = 1; brojač<= entered_number; counter++) cout << setw(2) <#uključi korištenje imenskog prostora std; void tower(int, int, int, int); // deklaracija prototipa rekurzivne funkcije int count = 1; // globalna varijabla za brojanje broja koraka int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>broj; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> osnovni_štap; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> završna_šipka; int help_rod; // blok za određivanje broja pomoćne šipke, analiza brojeva početne i završne šipke if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// pokretanje rekurzivne funkcije za rješavanje problema Towers of Hanoi broj, // varijabla koja pohranjuje broj diskova koje je potrebno premjestiti basic_rod, // varijabla koja pohranjuje broj šipke na kojoj će diskovi inicijalno biti locirana help_rod , // varijabla koja pohranjuje broj šipke, koja se koristi kao pomoćna final_rod); // varijabla koja pohranjuje broj šipke na koju treba premjestiti diskove system("pause"); povratak 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // uvjet za završetak rekurzivnih poziva ( 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); // перемещаем все диски со вспомогательного стержня на финальный } }

  // kod Code::Blocks

  // Dev-C++ kod

  // hanoi_tower.cpp: Definira ulaznu točku za aplikaciju konzole. // Program koji rekurzivno rješava problem Hanojskog tornja #include #uključi korištenje imenskog prostora std; void tower(int, int, int, int); // deklaracija prototipa rekurzivne funkcije int count = 1; // globalna varijabla za brojanje broja koraka int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>broj; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> osnovni_štap; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> završna_šipka; int help_rod; // blok za određivanje broja pomoćne šipke, analiza brojeva početne i završne šipke if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// pokretanje rekurzivne funkcije za rješavanje problema Towers of Hanoi broj, // varijabla koja pohranjuje broj diskova koje je potrebno premjestiti basic_rod, // varijabla koja pohranjuje broj šipke na kojoj će diskovi inicijalno biti locirana help_rod , // varijabla koja pohranjuje broj šipke, koja se koristi kao pomoćna final_rod); // varijabla koja pohranjuje broj šipke na koju treba premjestiti diskove return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // uvjet za završetak rekurzivnih poziva ( 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); // перемещаем все диски со вспомогательного стержня на финальный } }

  Slika 5 prikazuje primjer rekurzivnog programa Tower of Hanoi. Prvo smo unijeli broj diskova jednak tri, zatim smo unijeli osnovnu šipku (prvu), te označili posljednju šipku (treću). Automatski je druga šipka postala pomoćna. Program je dao rezultat koji se u potpunosti podudara s animiranim rješenjem ovog problema.

  Unesite broj diskova: 3 Unesite broj osnovne šipke: 1 Unesite broj završne šipke: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

  Slika 5 - Rekurzija u C++

  Sa slike je vidljivo da se disk prvo kreće od štapa jedan do štapa tri, zatim od štapa jedan do štapa dva, od štapa tri do štapadva itd. Odnosno, program samo prikazuje redoslijed pomicanja diskova i minimalni broj koraka u kojima će se svi diskovi pomicati.

  Svi ovi problemi mogu se riješiti iterativno. Postavlja se pitanje: "Što je bolje riješiti, iterativno ili rekurzivno?" Odgovaram: “Nedostatak rekurzije je taj što troši znatno više računalnih resursa od iteracije. To rezultira velikim opterećenjem i RAM-a i procesora. Ako je očito da se određeni problem može riješiti na iterativni način, onda ga treba koristiti drugačije, koristeći rekurziju!” Ovisno o problemu koji se rješava, složenost pisanja programa mijenja se korištenjem jedne ili druge metode rješenja. Ali češće je problem riješen rekurzivnom metodom sa stajališta čitljivosti koda mnogo jasniji i kraći.

  Rekurzije su same po sebi zanimljivi događaji, ali u programiranju su posebno važne u specifičnim slučajevima. Pri prvom susretu s njima nemali broj ljudi ima problema s razumijevanjem. To je zbog ogromnog polja potencijalnih primjena samog pojma, ovisno o kontekstu u kojem se "rekurzija" koristi. Ali možemo se nadati da će ovaj članak pomoći u izbjegavanju mogućih nesporazuma ili nesporazuma.

  Što je uopće "rekurzija"?

  Riječ "rekurzija" ima čitav niz značenja, koja ovise o području u kojem se primjenjuje. Univerzalna oznaka je sljedeća: rekurzije su definicije, slike, opisi objekata ili procesa u samim objektima. One su moguće samo u slučajevima kada je predmet dio samog sebe. Matematika, fizika, programiranje i niz drugih znanstvenih disciplina definiraju rekurziju na svoj način. Našao je praktičnu primjenu u radu informacijskih sustava i fizikalnim eksperimentima.

  Što se podrazumijeva pod rekurzijom u programiranju?

  

  Rekurzivne situacije ili rekurzija u programiranju su trenuci kada programska procedura ili funkcija poziva samu sebe. Koliko god to zvučalo čudno za one koji su počeli učiti programiranje, tu nema ničeg čudnog. Treba imati na umu da rekurzije nisu teške, au nekim slučajevima zamjenjuju petlje. Ako je računalu ispravno naloženo da pozove proceduru ili funkciju, ono će je jednostavno početi izvršavati.

  Rekurzija može biti konačna ili beskonačna. Da bi prvi prestao sam sebe uzrokovati, mora sadržavati i uvjete za prestanak. To može biti smanjenje vrijednosti varijable i, kada se postigne određena vrijednost, zaustavljanje poziva i prekid programa / prelazak na sljedeći kod, ovisno o potrebama za postizanjem određenih ciljeva. Pod beskonačnom rekurzijom podrazumijevamo da će se pozivati ​​sve dok računalo ili program u kojem se izvodi radi.

  Također je moguće organizirati složenu rekurziju koristeći dvije funkcije. Recimo da postoje A i B. Funkcija A ima poziv B u svom kodu, a B zauzvrat ukazuje računalu da treba izvršiti A. Složene rekurzije su izlaz iz brojnih složenih logičkih situacija za računalo logika.

  Ako je čitatelj ovih redaka proučavao programske petlje, onda je vjerojatno već uočio sličnosti između njih i rekurzije. Općenito, oni doista mogu obavljati slične ili identične zadatke. Korištenjem rekurzije zgodno je simulirati rad petlje. Ovo je posebno korisno tamo gdje sami ciklusi nisu baš prikladni za korištenje. Shema implementacije softvera ne razlikuje se mnogo između različitih programskih jezika visoke razine. Ipak, rekurzija u Pascalu i rekurzija u C-u ili nekom drugom jeziku imaju svoje karakteristike. Može se uspješno implementirati u jezicima niske razine kao što je Assembly, ali to je problematičnije i dugotrajnije.

  Rekurzijsko stablo

  

  Što je "stablo" u programiranju? Ovo je konačan skup koji se sastoji od najmanje jednog čvora koji:

  1. Ima početni poseban čvor, koji se naziva korijen cijelog stabla.
  2. Preostali čvorovi su u broju različitom od nule upareno disjunktnih podskupova, i oni su također stablo. Svi takvi oblici organizacije nazivaju se podstablom glavnog stabla.

  Drugim riječima: stabla sadrže podstabla, koja sadrže više stabala, ali u manjem broju od prethodnog stabla. To se nastavlja sve dok se jedan od čvorova više ne može kretati naprijed, a to će označiti kraj rekurzije. Postoji još jedna nijansa u shematskom prikazu: obična stabla rastu odozdo prema gore, ali u programiranju se crtaju obrnuto. Čvorovi koji nemaju nastavak nazivaju se lisnati čvorovi. Radi lakšeg označavanja i praktičnosti koristi se genealoška terminologija (preci, djeca).

  Zašto se koristi u programiranju?

  

  Rekurzija u programiranju našla je svoju primjenu u rješavanju niza složenih problema. Ako je potrebno izvršiti samo jedan poziv, tada je lakše koristiti integracijsku petlju, ali s dva ili više ponavljanja, kako bi se izbjegla izgradnja lanca i izvršilo njihovo izvršenje u obliku stabla, koriste se rekurzivne situacije. Za široku klasu zadataka ovakva organizacija računalnog procesa je najoptimalnija sa stajališta potrošnje resursa. Dakle, rekurzija u Pascalu ili bilo kojem drugom programskom jeziku visoke razine je poziv funkciji ili proceduri dok se ne ispune uvjeti, bez obzira na broj vanjskih poziva. Drugim riječima, program može imati samo jedan poziv potprograma, ali on će se događati do unaprijed određenog trenutka. Na neki način, ovo je analog ciklusa sa svojim specifičnostima upotrebe.

  Razlike između rekurzije u različitim programskim jezicima

  Unatoč općoj shemi implementacije i specifičnoj primjeni u svakom pojedinačnom slučaju, rekurzija u programiranju ima svoje karakteristike. To može dovesti do poteškoća prilikom traženja potrebnog materijala. Ali uvijek biste trebali zapamtiti: ako programski jezik poziva funkcije ili procedure, tada je pozivanje rekurzije izvedivo. Ali njegove najznačajnije razlike pojavljuju se pri korištenju niskih i visokih programskih jezika. To posebno vrijedi za mogućnosti implementacije softvera. Izvršenje u konačnici ovisi o tome kakav se zadatak postavlja, a rekurzija se piše u skladu s njim. Funkcije i postupci koji se koriste su različiti, ali cilj im je uvijek isti - natjerati ih da se sami prozovu.

  Rekurzija je jednostavna. Koliko je lako zapamtiti sadržaj članka?

  

  Početnicima će to u početku možda biti teško razumjeti, pa su vam potrebni primjeri rekurzije ili barem jedan. Stoga treba navesti mali primjer iz svakodnevnog života koji će pomoći da se shvati sama bit ovog mehanizma za postizanje ciljeva u programiranju. Uzmite dva ili više ogledala, postavite ih tako da sva ostala budu prikazana u jednom. Možete vidjeti da se ogledala reflektiraju više puta, stvarajući efekt beskonačnosti. Rekurzije su, slikovito rečeno, refleksije (bit će ih mnogo). Kao što vidite, nije teško razumjeti, samo ako imate želju. Proučavajući programske materijale, možete dodatno shvatiti da je rekurziju također vrlo lako izvršiti.