Rekurzija u logici. Rep rekurzija i petlja

30.07.2019 Iron

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

strukture podataka:
- graf (posebno stabla i liste) se može posmatrati kao kolekcija jednog čvora i podgrafa (manji graf);
- string se sastoji od prvog znaka i podniza (manji string);
uzorci dizajna, na primjer. Dekoratorski objekt može uključivati druge objekte koji su također dekoratori. McColm Smith je detaljno proučavao rekurzivne obrasce, ističući u svojoj knjizi opći obrazac dizajna - Rekurziju;
rekurzivne funkcije (algoritmi) sami sebe nazivaju.

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

Primjeri rekurzivnih algoritama

Rekurzivni algoritam uvijek dijeli problem na dijelove koji su po svojoj strukturi isti kao i originalni problem, ali jednostavniji. Za rješavanje podzadataka, funkcija se poziva rekurzivno, a njihovi rezultati se nekako kombiniraju. Do podjele problema dolazi samo kada se ne može odmah riješiti (prekomplicirano je).

Na primjer, zadatak obrade niza se često može svesti na obradu njegovih dijelova. Podjela na dijelove se vrši dok ne postanu elementarni, tj. dovoljno jednostavno da dobijete rezultat bez daljeg pojednostavljivanja.

Pronalaženje elementa niza

Start; pretraga (niz, početak, kraj, element); traži element sa vrijednošću elementa u nizu između indeksa start i end if begin> end result: = false; element nije pronađen inače ako je niz = element rezultat: = istina; element pronađen inače rezultat: = pretraga (niz, početak + 1, kraj, element) kraj; vrati rezultat

Algoritam dijeli originalni niz na dva dijela - prvi element i niz ostalih elemenata. Postoje dva jednostavna slučaja u kojima nije potrebno razdvajanje - svi elementi su obrađeni ili je prvi element željeni.

U algoritmu pretraživanja bilo bi moguće podijeliti niz na drugi način (na primjer, na pola), ali to ne bi uticalo na efikasnost. Ako je niz sortiran, onda je preporučljivo podijeliti ga na pola, jer na svakom koraku, količina obrađenih podataka može se prepoloviti.

Binarno pretraživanje u nizu

Binarno pretraživanje se izvodi preko sortiranog niza. U svakom koraku, traženi element se poredi sa vrednošću u sredini niza. U zavisnosti od rezultata poređenja, lijeva ili desna strana se mogu „odbaciti“.

Start; binary_search (niz, početak, kraj, element); traži element sa vrijednošću elementa; u rastućem nizu niza; između indeksa početak i kraj ako početak> kraj kraj; vrati false - nijedan element nije pronađen u sredini: = (kraj + početak) div 2; izračunavanje indeksa elementa u sredini razmatranog dijela niza ako je niz = kraj elementa; vrati true (element pronađen) ako je niz< element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Izračunavanje Fibonačijevih brojeva

Fibonačijevi brojevi su definisani rekurzivnim izrazom, tj. takav da je proračun elementa izražen iz prethodnih elemenata: \ (F_0 = 0, F_1 = 1, F_n = F_ (n-1) + F_ (n-2), n> 2 \).

Start; fibonači (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 end; vrati rezultat

Brzo sortiranje

Algoritam brzog sortiranja u svakom koraku odabire jedan od elemenata (pivot) i, u odnosu na njega, dijeli niz na dva dijela, koji se obrađuju rekurzivno. Elementi manji od osovine se postavljaju u jedan deo, a ostali u drugi.

Dijagram toka algoritma brzog sortiranja

Sortiranje spajanjem

Algoritam za sortiranje spajanjem baziran je na mogućnosti brzog kombinovanja uređenih nizova (ili lista) tako da je rezultat uređen. Algoritam dijeli originalni niz na dva nasumično (obično na pola), sortira ih rekurzivno i spaja rezultat. Podjela se događa sve dok je veličina niza veća od jedan, jer prazan niz i niz od jednog elementa su uvijek sortirani.

Blok dijagram sortiranja spajanjem

U svakom koraku spajanja, prva neobrađena stavka se bira sa obje liste. Stavke se upoređuju, najmanji od njih se dodaje rezultatu i označava kao obrađen. Spajanje se dešava sve dok jedna od lista nije prazna.

Start; spajanje (Niz1, Veličina1, Niz2, Veličina2); originalni nizovi su poređani; rezultat je uređeni niz dužine Size1 + Size2 i: = 0, j: = 0 vječni_ciklus ako i> = Size1 dodaje elemente iz j u Size2 niza Niz2 na kraj rezultata izlazi iz petlje ako je j> = Veličina2 dodaj elemente iz i u Size1 niza Niz1 na kraj rezultata; izađi iz petlje ako Array1 [i]< Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Niz2 [j]) rezultat: = Niz2 [j] j: = j + 1 kraj; vrati rezultat

Analiza rekurzivnih algoritama

Kada se izračunavaju složenost iteracija i njihov broj u najgorim, najboljim i prosječnim slučajevima. Međutim, nećete moći primijeniti ovaj pristup na rekurzivnu funkciju, jer rezultat će biti rekurentna relacija. Na primjer, za funkciju da pronađe element u nizu:

$
\ započeti (jednačina *)
T ^ (pretraga) _n = \ početak (slučajevi)
\ mathcal (O) (1) \ quad & \ text ($ n = 0 $) \\
\ mathcal (O) (1) + \ mathcal (O) (T ^ (pretraga) _ (n-1)) \ quad & \ text ($ n> 0 $)
\ kraj (slučajevi)
\ kraj (jednačina *)
$

Rekurentne relacije nam ne dozvoljavaju da procenimo složenost – ne možemo ih samo upoređivati, a samim tim i efikasnost odgovarajućih algoritama. Potrebno je dobiti formulu koja će opisivati rekurentnu relaciju - univerzalni način da se to uradi je odabir formule metodom zamjene, a zatim dokazivanje korespondencije formule sa relacijom metodom matematičke indukcije.

Metoda zamjene (iteracije).

Sastoji se u sekvencijalnoj zamjeni ponavljajućeg dijela u izrazu kako bi se dobili novi izrazi. Zamjena se vrši sve dok ne bude moguće shvatiti opći princip i izraziti ga u obliku formule koja se ne ponavlja. Na primjer, da biste pronašli element u nizu:

$
T ^ (pretraga) _n = \ mathcal (O) (1) + \ mathcal (O) (T ^ (pretraga) _ (n-1)) =
2 \ puta \ mathcal (O) (1) + \ mathcal (O) (T ^ (pretraga) _ (n-2)) =
3 \ puta \ mathcal (O) (1) + \ mathcal (O) (T ^ (traži) _ (n-3))
$

Možemo pretpostaviti da je \ (T ^ (pretraga) _n = T ^ (pretraga) _ (nk) + k \ puta \ mathcal (O) (1) \), ali tada \ (T ^ (pretraga) _n = T ^ (pretraga) _ (0) + n \ puta \ matematički (O) (1) = \ matematički (O) (n) \).

Izveli smo formulu, ali prvi korak sadrži pretpostavku, tj. ne postoji dokaz o korespondenciji formule sa rekurentnim izrazom - metoda matematičke indukcije omogućava dobijanje dokaza.

Metoda matematičke indukcije

Omogućava vam da dokažete istinitost neke izjave (\ (P_n \)), sastoji se od dva koraka:

dokaz tvrdnje za jedan ili više posebnih slučajeva \ (P_0, P_1, ... \);
dokaz \ (P_ (n + 1) \) je izveden iz istinitosti \ (P_n \) (induktivna hipoteza) i posebnih slučajeva.

Dokažimo ispravnost pretpostavke napravljene pri procjeni složenosti funkcije pretraživanja (\ (T ^ (pretraga) _n = (n + 1) \ puta \ mathcal (O) (1) \)):

\ (T ^ (pretraga) _ (1) = 2 \ puta \ mathcal (O) (1) \) je tačno iz uslova (može se zameniti u originalnu rekurzivnu formulu);
recimo istina \ (T ^ (pretraga) _n = (n + 1) \ puta \ mathcal (O) (1) \);
potrebno je dokazati da je \ (T ^ (pretraga) _ (n + 1) = ((n + 1) +1) \ puta \ mathcal (O) (1) = (n + 2) \ puta \ mathcal ( O) (jedan)\);
1. zameni \ (n + 1 \) u rekurentnu relaciju: \ (T ^ (pretraga) _ (n + 1) = \ mathcal (O) (1) + T ^ (pretraga) _n \);
2. na desnoj strani izraza moguće je izvršiti zamjenu na osnovu induktivne hipoteze: \ (T ^ (pretraga) _ (n + 1) = \ mathcal (O) (1) + (n + 1) \ times \ mathcal (O) (1) = (n + 2) \ times \ 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 se koristi tzv. opšta metoda.

Opća (glavna) metoda za rješavanje rekurentnih odnosa

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

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

Jednačine ove vrste se dobijaju ako se originalni problem podijeli na podzadatke, od kojih svaki obrađuje \ (\ frac (n) (b) \) elemente. \ (f_n \) - složenost operacija dijeljenja problema na dijelove i kombinovanja rješenja. Pored tipa relacije, opća metoda nameće ograničenja na funkciju \ (f_n \), izdvajajući tri slučaja:

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

Ispravnost iskaza za svaki slučaj se formalno dokazuje. Problem analize rekurzivnog algoritma se sada svodi na određivanje slučaja glavne teoreme, koji odgovara rekurentnoj relaciji.

Analiza algoritma binarnog pretraživanja

Algoritam dijeli originalne 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 dijeljenja problema i sastavljanja rezultata raste istom brzinom kao \ (n ^ (\ log_b a) \), pa je potrebno koristiti drugi slučaj teoreme:

\ (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 originalni problem na jedan podzadatak (a = 1), podaci se dijele na jedan dio (b = 1). Ne možemo koristiti glavnu teoremu za analizu ovog algoritma, jer uslov \ (b> 1 \) nije ispunjen.

Za izvođenje analize može se koristiti metoda zamjene ili sljedeće rezonovanje: svaki rekurzivni poziv smanjuje dimenziju ulaznih podataka za jedan, tako da će biti ukupno n, od kojih svaki ima složenost \ (\ mathcal (O) (1) \). Tada \ (T ^ (pretraga) _n = n \ cdot \ mathcal (O) (1) = \ mathcal (O) (n) \).

Analiza algoritma za sortiranje spajanjem

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

Prilikom obrade liste, cijepanje može zahtijevati izvođenje \ (\ Theta (n) \) operacija, a za niz se izvodi u konstantnom vremenu (\ (\ Theta (1) \)). Međutim, bit će potrebno \ (\ Theta (n) \) da se rezultati ipak spoje, tako da \ (f_n = n \).

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

Analiza složenosti brzog sortiranja

U najboljem slučaju, originalni niz je podijeljen na dva dijela, od kojih svaki sadrži polovinu originalnih podataka. Za razdvajanje će biti potrebno n operacija. Složenost sastavljanja rezultata ovisi o korištenim strukturama podataka - za niz \ (\ mathcal (O) (n) \), za povezanu listu \ (\ mathcal (O) (1) \). \ (a = 2, b = 2, f_n = b \), tako 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 će se stalno birati kao referenca. Tada \ (b = 1 \), što znači da opet ne možemo koristiti glavnu teoremu. Međutim, znamo da će u ovom slučaju biti izvršeno n rekurzivnih poziva, od kojih svaki dijeli niz na dijelove (\ (\ mathcal (O) (n) \)) - otuda i složenost algoritma \ (T ^ (quickSort ) _n = \ mathcal (O) (n ^ 2) \).

Prilikom analize brzog sortiranja zamjenom, također bi morali odvojeno razmotriti najbolje i najgore slučajeve.

Rep rekurzija i petlja

Analiza složenosti rekurzivnih funkcija je mnogo teža od evaluacije petlji, ali glavni razlog zašto su petlje poželjnije je visoka cijena poziva funkcije.

Nakon poziva kontrola se prenosi druga funkcija. Za prijenos kontrole dovoljno je promijeniti vrijednost registra programskog brojača, u koji procesor pohranjuje broj trenutno izvršene naredbe - na isti način se kontrola prenosi na grane algoritma, na primjer, kada se koristi uslovni operator. Međutim, poziv nije samo prijenos kontrole, jer nakon što pozvana funkcija završi proračune, mora vratiti kontrolu do tačke u kojoj je poziv obavljen, kao i vraćanje vrijednosti lokalnih varijabli koje su tamo postojale prije poziva.

Za implementaciju ovakvog ponašanja koristi se stek (stek poziva, stek poziva) - u njega se stavljaju broj komande za vraćanje i informacije o lokalnim varijablama. Stog nije beskonačan, stoga rekurzivni algoritmi mogu dovesti do njegovog prelivanja; u svakom slučaju, može potrajati značajan dio vremena za rad s njim.

U nekim je slučajevima prilično lako zamijeniti rekurzivnu funkciju petljom, na primjer, one o kojima je bilo riječi gore. U nekim slučajevima je potreban kreativniji pristup, ali češće je takva zamjena moguća. Osim toga, postoji posebna vrsta rekurzije gdje je rekurzivni poziv posljednja operacija koju obavlja funkcija. Očigledno, u ovom slučaju funkcija koja poziva neće ni na koji način promijeniti rezultat, što znači da nema smisla da vraća kontrolu. Takve rekurzija se zove repna rekurzija- prevodioci ga automatski zamenjuju petljom.

Često pomaže da se napravi repna rekurzija metoda akumulirajućeg parametra, koji se sastoji u dodavanju dodatnog argumenta akumulatora funkciji, u kojoj se akumulira rezultat. Funkcija izvodi proračune akumulatora prije rekurzivnog poziva. Dobar primjer korištenja ove tehnike je faktorijalna funkcija:
\ (činjenica_n = n \ cdot činjenica (n-1) \\
fact_3 = 3 \ cdot fact_2 = 3 \ cdot (2 \ cdot fact_1) = 3 \ cdot (2 \ cdot (1 \ cdot fact_0)) = 6 \\
fact_n = factTail_ (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 Fibonačijevih brojeva. Glavna funkcija poziva pomoćnu funkciju, koja koristi metodu akumulirajućeg parametra, i kao argumente prosljeđuje početnu vrijednost iteratora i dva akumulatora (dva prethodna Fibonačijeva broja).

Start; fibonacci (broj) return fibonacci (broj, 1, 1, 0) end start; fibonacci (broj, iterator, fib1, fib2) ako je iterator == broj vrati fib1 vrati fibonacci (broj, iterator + 1, fib1 + fib2, fib1) kraj

Funkcija sa akumulirajućim parametrom vraća akumulirani rezultat ako je izračunat određeni broj brojeva, u suprotnom povećava brojač, izračunava novi Fibonačijev broj i vrši rekurzivni poziv. Optimizirajući prevodioci mogu otkriti da se rezultat poziva funkcije prosljeđuje nepromijenjen na izlaz funkcije i zamjenjuje petljom. Ova tehnika je posebno relevantna u funkcionalnim i logičkim programskim jezicima, jer programer ne može eksplicitno koristiti cikličke konstrukcije u njima.

Književnost

Višenitni Qt server. Skup tema. Uzorak dekoratera [Elektronski izvor] - način pristupa: https: // stranica / arhiva / 1390. Datum pristupa: 21.02.2015.
Jason McColm Smith: Trans. sa engleskog - M.: DOO “I.D. Williams”, 2013. - 304 str.
Skiena S. Algorithms. Vodič za razvoj.-2. izd.: trans. sa engleskog-SPb.: BHV-Peterburg, 2011.-720p.: ilustr.
Vasiljev V.S., Analiza složenosti algoritama. Primjeri [Elektronski izvor] - način pristupa: https: // stranica / arhiva / 1660. Datum pristupa: 21.02.2015.
A. Aho, J. Hopcroft, J. Ullman, Strukture podataka i algoritmi, M., Williams, 2007.
Miller, R. Sekvencijalni i paralelni algoritmi: opći pristup / R. Miller, L. Boxer; per. sa engleskog - M.: BINOM. Laboratorij znanja, 2006.-- 406 str.
Sergievsky G.M. Funkcionalno i logičko programiranje: udžbenik. priručnik za studente viših. studija. institucije / G.M. Sergievsky, N.G. Volchenkov. - M.: Izdavački centar "Akademija", 2010.- 320s.

Od lat recursio (povratak). Općenito, ovo je naziv za proces ponavljanja elemenata na "samosličan način".

Matrjoške su upečatljiv primjer rekurzije. Rekurzivna definicija: "Matrjoška je podijeljena šuplja drvena lutka s manjom matrjoškom unutra." Evo rekurzije na ruskom. A da nije granica mogućnosti majstora, idealna matrjoška bi duboko ušla u sebe do atomskog nivoa. I još dublje. Samo što Lefty nije imao mali domet dovoljne snage. Gornja granica je teoretski također neograničena, ali baobabi odgovarajuće veličine ne rastu na našoj planeti. Općenito, iz tehničkih razloga, rekurzija bi trebala biti konačna.

U programiranju (kao u matematici), rekurzija je proces pozivanja same funkcije (direktna rekurzija) ili poziv funkcije B unutar funkcije A, koja zauzvrat sadrži poziv funkciji A (indirektna ili međusobna rekurzija). Naravno, rekurzivni pozivi moraju imati zadovoljavajući uslov završetka, inače će takav program "visiti" kao u beskonačnoj petlji - ali, za razliku od beskonačne petlje, sa beskonačnom rekurzijom, on će se srušiti sa prelivanjem steka.

Primjer rekurzije

Najdosadniji primjer rekurzije u matematičkom programiranju je izračunavanje faktorijala. Nemojmo iznevjeriti slavne tradicije. Za one koji to još nisu uradili: N! (faktorijal N) je proizvod svih prirodnih brojeva od jedan do N (faktorijal nule je 1).
Možete glupo množiti brojeve od 1 do N u petlji. Ili možete konstruirati faktorijel funkcije (n), koji će sadržavati uvjet i sam se pozvati. Ako je n jednako jedan, onda funkcija vraća vrijednost 1, u suprotnom vraća vrijednost n pomnoženu faktorijelom (n-1).
PHP skica

Faktorijal funkcije ($ n) (ako ($ n == 1) (povratak 1;) else (povratni intval ($ n * faktorijel ($ n - 1));))

Praktična upotreba rekurzije

"Pa, a zašto je ovo potrebno ovdje?" - pitaće nas nestrpljivi mladi čitalac - "Naučne gluposti, dosadnost, svakakvi faktorijali... I na šta praktično primeniti ovu rekurziju?"
“Na crno oko web programiranja” - odgovorit ćemo bez oklijevanja. A onda ćemo to opravdati.

U stvari, postoji mnogo više upotreba rekurzije u web programiranju nego što se čini. Zato što je rekurzija možda jedini način da se pređe bilo koju strukturu drveta, kada ni njena veličina ni dubina ugniježđenja nisu unaprijed poznati. Inače, konstrukcija i obilaženje grafova takođe ne mogu bez toga. Ovo je klasika, gospodo - pokušajte na neki drugi način tražiti datoteke koje su vam potrebne u stablu unix direktorija i odmah ćete shvatiti da bez rekurzije ne možete ići nigdje.

Pokušajte bez toga tako što ćete napraviti mapu sajta sa hijerarhijskom strukturom sekcija u obliku ugniježđenih lista. Radije ćete se objesiti nego izgraditi ako ne znate unaprijed na koliko je točno nivoa dubina ugniježđenja ograničena. Čak i ako znate, ali pokušajte bez rekurzije, onda umjesto jednostavne, transparentne i besprijekorne funkcije, napravite glomaznu softversku "policu na štakama". A kada završite i obrišete svoje znojno čelo, mračna životna istina će doprijeti do vas: kada se dubina gniježđenja promijeni, vaša struktura koja se širi odmah će prestati ispravno raditi. Stoga je malo vjerovatno da ćete ga moći primijeniti bilo gdje drugdje.

Rekurzija pretraživača

Da upravo. Ni tražilice nemaju gdje otići od rekurzije. Pošto je uspostavljen običaj da se autoritet sajta (dokumenta) meri brojem linkova, pretraživači su upali u rekurzivnu zamku, i pustili ih da tumaraju zauvek (ovo je iskrena dobra želja autora). Veza "težina" stranice se sastoji od malih dijelova "težine" svih onih koji se povezuju na nju. Da biste izračunali ovu težinu za A, koju nazivaju B, C i D, morate izračunati njihovu težinu, koju zauzvrat prenose sve vrste drugih, čiju težinu također treba izračunati... i tako dalje na cijelom webu računaju u pretraživaču. Potpuno rekurzivni problem. A vi kažete - čvrsta teorija. Najviše što ni jedno ni drugo je prava praksa.

Rekurzivni PageRank od Googlea

Kreatori Gugla su davno objavili svoj osnovni algoritam za izračunavanje PageRank-a. I koliko god se od tada promijenio, koliko god da je dopunjen poboljšanjima, osnova ostaje ista. Ne možete znati koliko PageRank stranica B povezuje sa stranicom A dok ne izračunamo koliko je PageRank stranica B dobila od svih drugih stranica koje su povezane sa njom, a to se ne može znati dok ne izračunamo PageRank tih stranice ... nastaviti? Vjerovatno više nije potrebno. Opet je Ona - Njeno Veličanstvo Rekurzija .

Collegiate YouTube

1 / 5
U matematici, rekurzija se odnosi na metodu definisanja funkcija i nizova brojeva: rekurzivno dato funkcija određuje svoju vrijednost upućivanjem na sebe drugim argumentima. U ovom slučaju su moguće 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+ \ ldots)))))) \; = 2 + f (2)), gdje f (n) = n n + f (n + 1) (\ displaystyle f (n) = (\ cfrac (n) (n + f (n + 1)))) Direktno izračunavanje korištenjem gornje formule će uzrokovati beskonačnu rekurziju, ali se može dokazati da vrijednost f (n) teži jedan s povećanjem n (dakle, uprkos beskonačnosti niza, vrijednost Eulerovog broja je konačna). Za približan proračun vrijednosti e dovoljno je umjetno ograničiti dubinu rekurzije na određeni unaprijed određeni broj unaprijed, a kada se dostigne, koristiti je umjesto f (n) (\ displaystyle f (n)) jedinica.
Drugi primjer rekurzije u matematici je numerički niz, dat rekurzivnom formulom, kada se svaki sljedeći član u nizu izračunava kao rezultat funkcije iz n prethodnih članova. Dakle, uz pomoć konačnog izraza (koji je kombinacija rekurentne formule i skupa vrijednosti za prvih n članova niza), može se definirati beskonačan niz.

Struktura 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šnim (terminalnim) ćelijama obično se upisuju nulti pokazivači, koji su ujedno i zastavice koje ukazuju na to da program obrađuje strukturu da je došao do njenog kraja.

Rekurzija je prilično česta pojava koja se javlja ne samo u oblastima nauke, već iu svakodnevnom životu. Na primjer, efekat Drostea, trougao Sierpinskog, itd. Najlakši način da vidite rekurziju je da usmjerite web kameru na ekran kompjutera, naravno, nakon što je uključite. Tako će kamera snimiti sliku ekrana računara i prikazati je na ovom ekranu, ispostaviće se nešto poput zatvorene petlje. Kao rezultat toga, posmatraćemo nešto što liči na tunel.

U programiranju, rekurzija je usko povezana sa funkcijama, tačnije zahvaljujući funkcijama u programiranju postoji nešto kao što je rekurzija ili rekurzivna funkcija. Jednostavnim riječima, rekurzija je definicija dijela funkcije (metode) kroz samu sebe, odnosno to je funkcija koja sama sebe poziva, direktno (u svom tijelu) ili indirektno (preko druge funkcije). Tipični rekurzivni problemi su problemi: pronalaženje n !, Fibonačijev broj. Takve probleme smo već rješavali, ali koristeći petlje, odnosno iterativno. Uopšteno govoreći, sve što se rješava iterativno može se riješiti rekurzivno, odnosno korištenjem rekurzivne funkcije. Cijelo rješenje se svodi na rješavanje osnovnog ili, kako ga još nazivaju, osnovnog slučaja. Postoji takva stvar kao što je korak rekurzije ili rekurzivni poziv. U slučaju kada se rekurzivna funkcija poziva da riješi složeni problem (ne osnovni slučaj), izvodi se određeni broj rekurzivnih poziva ili koraka kako bi se problem sveo na jednostavniji. I tako sve dok ne dobijemo osnovno rješenje. Hajde da razvijemo program koji deklariše 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 Šifra :: Blokovi

// Dev-C ++ kod

// factorial.cpp: definira ulaznu točku za aplikaciju konzole. #include korištenje imenskog prostora std; unsigned long int factorial (unsigned long int); // prototip rekurzivne funkcije int i = 1; // inicijalizacija globalne varijable za brojanje broja rekurzivnih poziva unsigned long int result; // 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 tastature 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; }

V redovi 7, 9, 21 tip podataka je unsigned long int, pošto faktorijalna vrijednost raste vrlo brzo, na primjer, već 10! = 3 628 800. Ako veličina tipa podataka nije dovoljna, onda kao rezultat dobijamo potpuno pogrešnu vrijednost. U kodu je deklarirano više operatora nego što je potrebno da se pronađe n!. Ovo je učinjeno tako da, nakon razrade, program pokaže šta se dešava u svakom koraku rekurzivnih poziva. Obratite pažnju na označene linije koda, redovi 23, 24, 28 Je rekurzivno rješenje n !. Redovi 23, 24 su osnovno rješenje za rekurzivnu funkciju, odnosno čim se vrijednost u varijabli fće biti jednako 1 ili 0 (pošto znamo da je 1! = 1 i 0! = 1), rekurzivni pozivi će se zaustaviti, a vrijednosti će početi da se vraćaju, za svaki rekurzivni poziv. Kada vrati vrijednost za prvi rekurzivni poziv, program će vratiti vrijednost izračunatog faktorijala. V red 28 faktorijalna () funkcija poziva samu sebe, ali već je njen argument jedan manje. Argument se svaki put smanjuje 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++

Prema rezultatu programa, svaki korak je jasno vidljiv i rezultat na svakom koraku je jednak nuli, osim za posljednji rekurzivni poziv. Bilo je potrebno izračunati pet faktorijala. Program je izvršio četiri rekurzivna poziva, pri petom pozivu je pronađen osnovni slučaj. I čim je program dobio rješenje za osnovni slučaj, riješio je prethodne korake i zaključio ukupni rezultat. Na slici 1 prikazana su samo četiri koraka jer je u petom koraku pronađeno određeno rješenje koje je na kraju vratilo konačno rješenje, odnosno 120. Slika 2 prikazuje dijagram rekurzivnog izračunavanja 5 !. Dijagram jasno pokazuje da se prvi rezultat vraća kada se postigne određeno rješenje, ali ne odmah, nakon svakog rekurzivnog poziva.

Slika 2 - Rekurzija u C++

Dakle, pronaći 5! treba znati 4! i pomnožite ga sa 5; 4! = 4 * 3! itd. Prema šemi prikazanoj na slici 2, proračun će se svesti na pronalaženje posebnog slučaja, odnosno 1!, nakon čega će vrijednosti biti vraćene svakom rekurzivnom pozivu redom. Posljednji rekurzivni poziv će vratiti 5 !.

Prepravimo program za pronalaženje faktorijala tako da dobijemo tabelu faktorijala. Da bismo to učinili, deklarisat ćemo petlju for u kojoj ćemo pozvati rekurzivnu funkciju.

korištenje imenskog prostora std; unsigned long int factorial (unsigned long int); // prototip rekurzivne funkcije int i = 1; // inicijalizacija globalne varijable za brojanje broja rekurzivnih poziva unsigned long int result; // 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 tastature 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 Šifra :: Blokovi

// Dev-C ++ kod

// fibonacci.cpp: definira ulaznu točku za aplikaciju konzole. #include // biblioteka za formatiranje informacija prikazanih na ekranu #include korištenje imenskog prostora std; unsigned long fibonacci (unsigned long); // prototip rekurzivne funkcije za pronalaženje 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 counter = 1; brojač<= entered_number; counter++) cout << setw(2) <
Pretpostavimo da je potrebno premjestiti tri diska s prve šipke na treću, što znači da je druga šipka pomoćna. Vizuelno rješenje ovog problema implementirano je u Flashu. Kliknite na dugme za početak da biste pokrenuli animaciju, dugme za zaustavljanje da biste zaustavili.

Program mora biti napisan za n-ti broj diskova. Pošto ovaj problem rješavamo rekurzivno, prvo moramo pronaći posebne slučajeve rješenja. U ovom problemu postoji samo jedan poseban slučaj - to je kada je potrebno pomaknuti samo jedan disk, a u ovom slučaju čak ni pomoćna šipka nije potrebna, ali na to jednostavno ne obraćamo pažnju. Sada morate organizirati rekurzivno rješenje ako je broj diskova više od jednog. Hajde da uvedemo neke oznake kako ne bismo pisali previše:

<Б> - šipka na kojoj se diskovi u početku nalaze (osnovna šipka);
<П> - pomoćna ili srednja šipka;
<Ф> - završni štap - štap na koji se diskovi moraju pomaknuti.

Dalje, kada opisujemo algoritam za rješavanje problema, koristit ćemo ove oznake. Za premještanje tri diska iz <Б> na <Ф> moramo prvo premjestiti dva diska iz <Б> na <П> a zatim premjestite treći disk (najveći) na <Ф> , jer <Ф> besplatno.

Kretati se n diskovi sa <Б> na <Ф> moramo prvo krenuti n-1 diskovi sa <Б> na <П> a zatim premjestite n-ti disk (najveći) na <Ф> , jer <Ф> besplatno. Nakon toga, morate se preseliti n-1 diskovi sa <П> na <Ф> , dok koristite štap <Б> kao pomoćno sredstvo. Ova tri koraka su cijeli rekurzivni algoritam. Isti algoritam pseudokoda:
n-1 preseliti se u <П>
n preseliti se u <Ф>
n-1 premjestiti iz <П> na <Ф> , dok koristite <Б> kao pomoćno sredstvo

// hanoi_tower.cpp: definira ulaznu točku za aplikaciju konzole. // Program koji rekurzivno rješava problem Hanojske kule #include "stdafx.h" #include #include korištenje imenskog prostora std; praznina kula (int, int, int, int); // deklaracija prototipa rekurzivne funkcije int count = 1; // globalna varijabla za brojanje 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 >> osnovna_šipka; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // blok za određivanje broja pomoćnog terminala, analiziranje brojeva početnog i završnog terminala if (basic_rod! = 2 && final_rod! = 2) help_rod = 2; inače if (basic_rod! = 1 && final_rod! = 1) help_rod = 1; inače if (basic_rod! = 3 && final_rod! = 3) help_rod = 3; tower (// pokrenuti rekurzivnu funkciju za rješavanje problema broja Towers of Hanoi, // varijabla koja pohranjuje broj diskova za pomicanje basic_rod, // varijabla koja pohranjuje broj jezgre gdje će diskovi biti inicijalno lociran help_rod, // varijabla koja pohranjuje broj jezgre, koji se koristi kao pomoćni final_rod); // varijabla koja pohranjuje broj osovine na koju diskovi trebaju biti premješteni sistem ("pauza"); return 0; ) void toranj (int count_disk, int baza, int help_baza, int new_baza) (if (count_disk == 1) // uslov 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 Šifra :: Blokovi

// Dev-C ++ kod

// hanoi_tower.cpp: definira ulaznu točku za aplikaciju konzole. // Program koji rekurzivno rješava problem Hanojske kule #include #include korištenje imenskog prostora std; praznina kula (int, int, int, int); // deklaracija prototipa rekurzivne funkcije int count = 1; // globalna varijabla za brojanje koraka int main () (cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> broj; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> osnovna_šipka; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // blok za određivanje broja pomoćnog terminala, analiziranje brojeva početnog i završnog terminala if (basic_rod! = 2 && final_rod! = 2) help_rod = 2; inače if (basic_rod! = 1 && final_rod! = 1) help_rod = 1; inače if (basic_rod! = 3 && final_rod! = 3) help_rod = 3; tower (// pokrenuti rekurzivnu funkciju za rješavanje problema broja Towers of Hanoi, // varijabla koja pohranjuje broj diskova za pomicanje basic_rod, // varijabla koja pohranjuje broj jezgre gdje će diskovi biti inicijalno lociran help_rod, // varijabla koja pohranjuje broj jezgre, koji se koristi kao pomoćni final_rod); // varijabla koja pohranjuje broj trake na koju treba premjestiti diskove return 0; ) void toranj (int count_disk, int baza, int help_baza, int new_baza) (if (count_disk == 1) // uslov 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 pokazuje primjer kako rekurzivni program Tower of Hanoi radi. Prvo smo unijeli broj diskova jednak tri, zatim smo uveli osnovni štap (prvi) i označili konačni štap (treći). Automatski je drugi štap postao pomoćni. Program je dao takav rezultat da se potpuno poklapa sa animacijskim rješenjem ovog problema.

Unesite brojeve diskova: 3 Unesite broj osnovnog štapa: 1 Unesite broj finalnog štapa: 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 se može vidjeti da se prvo disk kreće od štapa jedan do štapa tri, zatim od štapa jedan do štapa dva, od štapa tri do štapadva, itd. To jest, program daje samo redoslijed pomicanja diskova i minimalni broj koraka u kojima će svi diskovi biti pomjereni.

Svi ovi zadaci mogu se rješavati iterativno. Postavlja se pitanje: "Koje je najbolje rješenje, iterativno ili rekurzivno?" Moj odgovor je: „Nedostatak rekurzije je što troši znatno više računarskih resursa nego iteracija. Ovo se pretvara u veliko opterećenje i RAM-a i procesora. Ako je rješenje određenog problema očigledno na iterativni način, onda ga treba koristiti drugačije, koristiti rekurziju!" U zavisnosti od problema koji se rešava, složenost pisanja programa se menja kada se koristi jedan ili drugi metod rešenja. Ali češće je problem riješen rekurzivnom metodom sa stanovišta čitljivosti koda mnogo jasniji i kraći.

Rekurzije su zanimljivi događaji sami po sebi, ali u programiranju su od posebne važnosti u pojedinačnim slučajevima. Kada se prvi put suoče s njima, prilično značajan broj ljudi ima problema da ih razumije. To je zbog ogromnog polja potencijalne upotrebe samog termina, ovisno o kontekstu u kojem se koristi "rekurzija". Ali nadamo se da će ovaj članak pomoći u izbjegavanju mogućih nesporazuma ili nesporazuma.
Šta je uopšte "rekurzija"?
Riječ "rekurzija" ima niz značenja ovisno o području u kojem se koristi. Generička notacija je sledeća: rekurzije su definicije, slike, opisi objekata ili procesa u samim objektima. One su moguće samo u onim slučajevima kada je objekt dio samog sebe. Matematika, fizika, programiranje i niz drugih naučnih disciplina definišu rekurziju na svoj način. Našla je praktičnu primenu u radu informacionih sistema i fizičkim eksperimentima.
Šta se podrazumeva pod rekurzijom u programiranju?
Rekurzivne situacije, ili rekurzija u programiranju, su trenuci kada se procedura ili funkcija u programu poziva sama. Koliko god čudno zvučalo onima koji su počeli da uče programiranje, tu nema ničeg čudnog. Zapamtite da rekurzije nisu teške, au nekim slučajevima zamjenjuju petlje. Ako računar ispravno postavi poziv na proceduru ili funkciju, jednostavno će početi da je izvršava.
Rekurzija može biti konačna ili beskonačna. Da bi prvi prestao da se javlja, mora da sadrži i uslove za raskid. To može biti smanjenje vrijednosti varijable i kada se dostigne određena vrijednost, poziv se zaustavlja i program se prekida / prelazi na sljedeći kod, ovisno o potrebama za postizanjem određenih ciljeva. Beskonačna rekurzija znači da će se pozivati sve dok računar ili program u kojem je pokrenut radi.
Također je moguće organizirati složenu rekurziju koristeći dvije funkcije. Pretpostavimo da postoje A i B. Funkcija A ima poziv B u svom kodu, a B, zauzvrat, ukazuje računaru na potrebu da izvrši A. Kompleksne rekurzije su izlaz iz brojnih složenih logičkih situacija za kompjutersku logiku .
Ako je čitalac ovih redova proučavao programske petlje, onda je vjerovatno već uočio sličnost između njih i rekurzije. Generalno, oni zaista mogu obavljati slične ili identične zadatke. Pogodno je koristiti rekurziju za simulaciju petlje. Ovo je posebno korisno tamo gdje same petlje nisu baš zgodne za korištenje. Shema implementacije softvera se ne razlikuje mnogo između različitih programskih jezika visokog nivoa. Ipak, rekurzija u Pascalu i rekurzija u C ili nekom drugom jeziku imaju svoje posebnosti. Možda se uspješno implementira u jezicima niskog nivoa kao što je Assembler, ali to je problematičnije i dugotrajnije.
Stabla rekurzije
Šta je "drvo" u programiranju? Ovo je konačan skup koji se sastoji od najmanje jednog čvora, koji:
1. Ima poseban početni čvor, koji se zove korijen cijelog stabla.
2. Ostali čvorovi se nalaze u broju parovima disjunktnih podskupova različitom od nule, i oni su također stablo. Svi takvi oblici organizacije nazivaju se podstablima glavnog stabla.
Drugim riječima: stabla sadrže podstabla koja sadrže više stabala, ali u manjem broju od prethodnog stabla. Ovo se nastavlja sve dok na jednom od čvorova nema mogućnosti za dalje kretanje, a to će označiti kraj rekurzije. Postoji još jedna nijansa u vezi sa shematskim crtežom: obična stabla rastu odozdo prema gore, ali u programiranju se crtaju obrnuto. Čvorovi koji nemaju nastavak nazivaju se krajnji čvorovi. Radi lakšeg označavanja i pogodnosti koristi se genealoška terminologija (preci, djeca).
Zašto se koristi u programiranju?
Rekurzija je našla svoju primjenu u programiranju u rješavanju niza složenih problema. Ako je potrebno izvršiti samo jedan poziv, onda je lakše koristiti integracijski ciklus, ali sa dva ili više ponavljanja, kako bi se izbjeglo građenje lanca i natjeralo ih da se izvrše u obliku stabla, primjenjuju se rekurzivne situacije. Za široku klasu problema, organizacija računskog procesa na ovaj način je najoptimalnija sa stanovišta potrošnje resursa. Dakle, rekurzija u Pascal-u ili bilo kojem drugom programskom jeziku visokog nivoa je poziv funkcije ili procedure prije nego što se ispune uvjeti, bez obzira na broj vanjskih poziva. Drugim riječima, može postojati samo jedan poziv potprograma u programu, ali će se to dogoditi do unaprijed određenog trenutka. Na neki način, ovo je analog ciklusa sa svojom specifičnom upotrebom.
Razlike između rekurzije u različitim programskim jezicima
Uprkos opštoj šemi implementacije i specifičnoj primeni u svakom pojedinačnom slučaju, rekurzija u programiranju ima svoje karakteristike. To može otežati pronalaženje potrebnog materijala. Ali uvijek treba zapamtiti: ako programski jezik poziva funkcije ili procedure, onda je poziv rekurzije izvodljiv. Ali njegove najznačajnije razlike se pojavljuju kada se koriste niski i visoki programski jezici. To se posebno odnosi na mogućnosti implementacije softvera. Izvršenje u konačnici ovisi o tome koji je zadatak postavljen, a rekurzija je napisana u skladu s njim. Funkcije i procedure se koriste različito, ali njihova svrha je uvijek ista - prisiliti poziv sebi.
Rekurzija je laka. Koliko je lako zapamtiti sadržaj članka?
Za početnike može biti teško razumjeti u početku, pa su potrebni primjeri rekurzije ili barem jedan. Stoga treba navesti mali primjer iz svakodnevnog života koji će pomoći da se shvati sama suština ovog mehanizma za postizanje ciljeva u programiranju. Uzmite dva ili više ogledala, postavite ih tako da su sva ostala prikazana u jednom. Može se vidjeti da se ogledala reflektiraju više puta, stvarajući efekat beskonačnosti. Ovdje su rekurzije, slikovito rečeno, refleksije (biće ih mnogo). Kao što vidite, nije teško razumjeti, postojala bi želja. Proučavajući programske materijale, onda možete shvatiti da je rekurzija također vrlo lak zadatak.