Rekurzivni i rekurzivni algoritmi. Šta je rekurzija

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 čitav Web se računa 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 .

Zdravo Habrahabr!

Ovaj članak će raspravljati o problemima rekurzije i kako ih riješiti.

Ukratko o rekurziji

Rekurzija je prilično česta pojava koja se javlja ne samo u oblastima nauke, već iu svakodnevnom životu. Na primjer, efekat Drostea, trokut Sierpinskog, itd. Jedna od opcija da vidite rekurziju je usmjeravanje web kamere 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).

Mnogo je rečeno o rekurziji. Evo nekoliko dobrih resursa:

• Rekurzija i rekurzivni zadaci. Područja primjene rekurzije

Pretpostavlja se da je čitalac teoretski upoznat sa rekurzijom i da zna šta je ona. U ovom članku posvetit ćemo više pažnje problemima rekurzije.

Zadaci

Kada se uči rekurzija, najefikasniji način razumijevanja rekurzije je rješavanje problema.

Kako riješiti probleme rekurzije?

Prije svega, morate shvatiti da je rekurzija vrsta grube sile. Uopšteno govoreći, sve što se rješava iterativno može se riješiti rekurzivno, odnosno korištenjem rekurzivne funkcije.

sa neta

Svaki algoritam implementiran u rekurzivnom obliku može se prepisati u iterativnom obliku i obrnuto. Ostaje pitanje da li je to neophodno i koliko će to biti efikasno.

Za opravdanje ovoga mogu se koristiti sljedeći argumenti.

Za početak, sjetite se definicije rekurzije i iteracije. Rekurzija je način organiziranja obrade podataka u kojem program poziva sebe direktno ili uz pomoć drugih programa. Iteracija je način organiziranja obrade podataka u kojem se određene radnje ponavljaju mnogo puta bez dovođenja do rekurzivnih poziva programa.

Nakon toga možemo zaključiti da su međusobno zamjenjivi, ali ne uvijek sa istim troškovima resursa i brzine. Za opravdanje možete navesti sljedeći primjer: postoji funkcija u kojoj, za organiziranje određenog algoritma, postoji ciklus koji izvodi niz radnji ovisno o trenutnoj vrijednosti brojača (možda ne ovisi o tome). Jednom kada postoji ciklus, to znači da se niz radnji ponavlja u tijelu - iteracije ciklusa. Možete premjestiti operacije u poseban potprogram i proslijediti mu vrijednost brojača, ako postoji. Po završetku izvršavanja potprograma, provjeravamo uslove za izvršenje ciklusa, i ako je tačno, prelazimo na novi poziv potprograma, ako je lažno, završavamo izvršenje. Jer Cijeli sadržaj petlje smjestili smo u potprogram, što znači da je uvjet za izvršavanje petlje također smješten u potprogram, a može se dobiti kroz povratnu vrijednost funkcije, parametre proslijeđene referencom ili pokazivačem na potprogram, kao i globalne varijable. Nadalje, lako je pokazati da se poziv ovog potprograma iz petlje može lako pretvoriti u poziv, ili ne poziv (vraćanje vrijednosti ili jednostavno završetak rada) potprograma iz samog sebe, vođen nekim uvjetima ( oni koji su prethodno bili u stanju petlje). Sada, ako pogledate naš apstraktni program, to izgleda nešto kao prosljeđivanje vrijednosti potprogramu i njihovo korištenje, koje će potprogram promijeniti po završetku, tj. zamenili smo iterativnu petlju rekurzivnim pozivom potprograma da rešimo ovaj algoritam.

Zadatak pretvaranja rekurzije u iterativni pristup je simetričan.

Sumirajući, možemo izraziti sljedeće misli: za svaki pristup postoji klasa problema, koja je određena specifičnim zahtjevima za određeni problem.

S ovim se možete detaljnije upoznati.

Baš kao iteracija (petlja), rekurzija mora imati uslov zaustavljanja - osnovni slučaj (inače, baš kao i petlja, rekurzija će trajati zauvijek - beskonačno). Ovaj uslov je slučaj do kojeg ide rekurzija (korak rekurzije). U svakom koraku, rekurzivna funkcija se poziva sve dok sljedeći poziv ne pokrene osnovni uvjet i zaustavi rekurziju (ili bolje rečeno, vrati se na posljednji poziv funkcije). Cijelo rješenje se svodi na rješavanje osnovnog slučaja. 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.

Dakle, rekurzivna funkcija se sastoji od

• Stanje zaustavljanja ili osnovni slučaj
• Uvjet nastavka ili korak rekurzije je način da se zadatak svede na jednostavnije.

Razmotrimo ovo koristeći primjer pronalaženja faktorijala:

Rješenje javne klase (javna statička int rekurzija (int n) (// izlazni uvjet // Osnovni slučaj // kada zaustaviti ponavljanje rekurzije? Ako (n == 1) (povratak 1;) // Korak rekurzije / rekurzivni uvjet vraćanje rekurzije ( n - 1) * n;) public static void main (String args) (System.out.println (rekurzija (5)); // rekurzivni poziv funkcije))

Ovdje je osnovni uvjet uvjet kada je n = 1. Pošto znamo da je 1! = 1 i da izračunamo 1! ne treba nam ništa. Da izračunam 2! možemo koristiti 1 !, tj. 2! = 1! * 2. Da izračunam 3! treba nam 2!*3... Za izračunavanje n! trebamo (n-1)!* n. Ovo je korak rekurzije. Drugim riječima, da biste dobili vrijednost faktorijala iz broja n, dovoljno je pomnožiti vrijednost faktorijala iz prethodnog broja sa n.

Tagovi:

• rekurzija
• zadataka
• java

Dodaj oznake

Rekurzija je kada potprogram poziva sam sebe. Kada se prvi put suoče s takvom algoritamskom konstrukcijom, većina ljudi iskusi određene poteškoće, ali malo vježbe i rekurzije će postati razumljiv i vrlo koristan alat u vašem programskom arsenalu.

1. Suština rekurzije

Procedura ili funkcija može sadržavati pozive drugim procedurama ili funkcijama. Uključujući proceduru može sama pozvati. Tu nema paradoksa – računar samo sekvencijalno izvršava komande na koje naiđe u programu, a ako naiđe na poziv procedure, jednostavno počinje da izvršava ovu proceduru. Nije bitno koja je procedura dala naredbu da se to uradi.

Primjer rekurzivne procedure:

Procedure Rec (a: cijeli broj); početi ako a>

Razmotrite šta se dešava ako se poziv uputi u glavni program, na primer, u obliku Rec (3). Ispod je blok dijagram koji prikazuje redoslijed izvršavanja naredbi.

Rice. 1. Blok dijagram rekurzivne procedure.

Procedura Rec se poziva sa parametrom a = 3. Sadrži poziv Rec procedure sa parametrom a = 2. Prethodni poziv još nije završen, tako da možete zamisliti da se kreira druga procedura, a prva se ne završava svoj rad prije nego što završi svoj rad. Proces poziva se završava kada je parametar a = 0. U ovom trenutku 4 instance procedure se izvršavaju istovremeno. Poziva se broj istovremeno izvedenih procedura dubina rekurzije.

Četvrta pozvana procedura (Rec (0)) će ispisati broj 0 i završiti svoj posao. Nakon toga kontrola se vraća na proceduru koja ju je pozvala (Rec (1)) i ispisuje se broj 1. I tako sve dok se sve procedure ne završe. Početni poziv će ispisati četiri broja: 0, 1, 2, 3.

Druga vizuelna slika onoga što se dešava prikazana je na Sl. 2.

Rice. 2. Izvršavanje Rec procedure sa parametrom 3 sastoji se od izvršavanja Rec procedure sa parametrom 2 i štampanja broja 3. Zauzvrat, izvršavanje Rec procedure sa parametrom 2 sastoji se od izvršavanja Rec procedure sa parametrom 1 i štampanja broja 2. I tako dalje.

Kao samostalnu vježbu, razmislite šta ćete dobiti kada pozovete Rec (4). Takođe, razmislite šta se dešava kada pozovete proceduru Rec2 (4) opisanu u nastavku, gde se iskazi zamenjuju.

Procedura Rec2 (a: cijeli broj); započeti pisanje (a); ako je a> 0 onda Rec2 (a-1); kraj;

Imajte na umu da je u gornjim primjerima rekurzivni poziv unutar uvjetnog izraza. Ovo je preduslov da se rekurzija jednog dana završi. Također imajte na umu da se procedura poziva sa različitim parametrom od onog s kojim je pozvana. Ako procedura ne koristi globalne varijable, onda je i to neophodno kako se rekurzija ne bi nastavila beskonačno.

Moguća je malo složenija shema: funkcija A poziva funkciju B, a ona zauzvrat poziva A. Ovo se zove kompleksna rekurzija... U ovom slučaju ispada da prva opisana procedura mora pozvati onu koja još nije opisana. Da bi to bilo moguće, morate koristiti.

Procedura A (n: cijeli broj); (Naprijed opis (naslov) prve procedure) procedura B (n: cijeli broj); (Opis prosljeđivanja druge procedure) procedura A (n: cijeli broj); (Kompletan opis procedure A) begin writeln (n); B (n-1); kraj; postupak B (n: cijeli broj); (Kompletan opis procedure B) begin writeln (n); ako n

Prednji opis procedure B dopušta da se ona pozove iz procedure A. Prednji opis procedure A nije potreban u ovom primjeru i dodan je iz estetskih razloga.

Ako se obična rekurzija može uporediti sa uroborosom (slika 3), onda se slika složene rekurzije može izvući iz poznate dečije pesme, gde su „Vukovi od straha pojeli jedni druge“. Zamislite da dva vuka jedu jedan drugoga i razumete složenu rekurziju.

Rice. 3. Ouroboros je zmija koja proždire svoj rep. Crtež iz alhemijske rasprave "Sinozije" Teodora Pelekanosa (1478).

Rice. 4. Kompleksna rekurzija.

3. Simulacija petlje korištenjem rekurzije

Ako procedura pozove samu sebe, to zapravo dovodi do ponovnog izvršavanja instrukcija sadržanih u njoj, što je slično radu petlje. Neki programski jezici uopće ne sadrže konstrukcije petlje, ostavljajući programerima da organiziraju ponavljanja koristeći rekurziju (na primjer, Prolog, gdje je rekurzija glavna tehnika programiranja).

Na primjer, simulirajmo rad for petlje. Da bismo to učinili, potrebna nam je varijabla brojača koraka, koja se može implementirati, na primjer, kao parametar procedure.

Primjer 1.

Procedura LoopImitation (i, n: cijeli broj); (Prvi parametar je brojač koraka, drugi parametar je ukupan broj koraka) begin writeln ("Zdravo N", i); // Ovdje su sve upute koje će se ponoviti ako i

Rezultat poziva kao što je LoopImitation (1, 10) izvršit će instrukcije deset puta uz promjenu brojača sa 1 na 10. U ovom slučaju, ispisat će:

Zdravo N 1
Zdravo N 2
…
Zdravo N 10

Općenito, nije teško uočiti da su parametri postupka granice promjene vrijednosti brojača.

Možete zamijeniti rekurzivni poziv i naredbe koje će se ponoviti, kao u sljedećem primjeru.

Primjer 2.

Procedura LoopImitation2 (i, n: cijeli broj); početi ako i

U ovom slučaju, procedura će biti pozvana rekurzivno prije nego što instrukcije počnu da se izvršavaju. Nova instanca procedure će također, prije svega, pozvati drugu instancu, i tako dalje, dok ne dostignemo maksimalnu vrijednost brojača. Tek nakon toga posljednja od pozvanih procedura će izvršiti svoje instrukcije, zatim će pretposljednja izvršiti svoje instrukcije, itd. Pozivanje LoopImitation2 (1, 10) će ispisati pozdrave obrnutim redoslijedom:

Zdravo N 10
…
Zdravo N 1

Ako zamislimo lanac rekurzivno pozvanih procedura, onda u primjeru 1 prolazimo kroz njega od ranije pozvanih procedura do kasnijih. U primjeru 2, obrnuto, od kasnijeg do ranog.

Konačno, rekurzivni poziv se može postaviti između dva bloka instrukcija. Na primjer:

Procedura LoopImitation3 (i, n: cijeli broj); početi pisati ("Zdravo N", i); (Prvi blok uputstava se može nalaziti ovdje) ako i

Ovdje se prvo uzastopno izvršavaju instrukcije iz prvog bloka, zatim obrnutim redoslijedom instrukcije iz drugog bloka. Kada pozovemo LoopImitation3 (1, 10), dobijamo:

Zdravo N 1
…
Zdravo N 10
Zdravo N 10
…
Zdravo N 1

Bilo bi potrebno dvije petlje odjednom da se uradi isto bez rekurzije.

Može se iskoristiti činjenica da je izvođenje dijelova iste procedure vremenski razmaknuto. Na primjer:

Primjer 3: Pretvaranje broja u binarni sistem.

Kao što znate, dobijanje cifara binarnog broja se dešava deljenjem ostatka sa osnovom brojevnog sistema 2. Ako postoji broj, onda je njegova poslednja cifra u binarnom prikazu

Uzimajući cijeli dio od dijeljenja sa 2:

dobijamo broj koji ima istu binarnu reprezentaciju, ali bez zadnje cifre. Dakle, dovoljno je ponoviti gornje dvije operacije dok na sljedećem polju dijeljenja ne dobijemo cijeli broj jednak 0. Bez rekurzije, to će izgledati ovako:

Dok je x> 0 počinje c: = x mod 2; x: = x div 2; napisati (c); kraj;

Problem je u tome što se cifre binarne reprezentacije izračunavaju obrnutim redoslijedom (prve posljednje). Da biste ispisali broj u normalnom obliku, morat ćete zapamtiti sve brojeve u elementima niza i prikazati ih u zasebnoj petlji.

Rekurzija olakšava dobivanje izlaza u ispravnom redoslijedu bez niza i druge petlje. naime:

Procedura BinaryRepresentation (x: cijeli broj); var c, x: cijeli broj; begin (Prvi blok. Izvršava se redoslijedom poziva procedure) c: = x mod 2; x: = x div 2; (Rekurzivni poziv) ako je x> 0 onda BinaryRepresentation (x); (Drugi blok. Izvodi se obrnutim redoslijedom) write (c); kraj;

Uopšteno govoreći, nismo dobili nijedan dobitak. Brojevi binarne reprezentacije pohranjeni su u lokalnim varijablama, koje su različite za svaku pokrenutu instancu rekurzivne procedure. Odnosno, nije bilo moguće sačuvati memoriju. Naprotiv, gubimo dodatnu memoriju pohranjivanjem mnogih lokalnih varijabli x. Ipak, takvo rješenje mi se čini predivnim.

4. Rekurentni odnosi. Rekurzija i iteracija

Kažu da je niz vektora dan rekurentnom relacijom ako su dati početni vektor i funkcionalna ovisnost sljedećeg vektora od prethodnog.

Jednostavan primjer količine izračunate korištenjem rekurentnih odnosa je faktorijel

Sljedeći faktorijel se može izračunati iz prethodnog kao:

Nakon unosa oznake dobijamo omjer:

Vektori iz formule (1) mogu se tumačiti kao skupovi varijabilnih vrijednosti. Tada će se izračunavanje potrebnog elementa niza sastojati od ponovnog ažuriranja njihovih vrijednosti. Konkretno za faktorijel:

X: = 1; za i: = 2 do n do x: = x * i; upis (x);

Svako takvo ažuriranje (x: = x * i) se poziva iteracija, a proces ponavljanja iteracija je ponavljanje.

Imajte na umu, međutim, da je relacija (1) čisto rekurzivna definicija niza i da je izračunavanje n-tog elementa zapravo višestruko uzimanje funkcije f iz same sebe:

Konkretno, za faktorijel možete napisati:

Faktor funkcije (n: cijeli broj): cijeli broj; početi ako je n> 1 onda Faktorijalno: = n * Faktorijalno (n-1) inače Faktorijalno: = 1; kraj;

Treba shvatiti da pozivanje funkcija podrazumijeva dodatne troškove, tako da će prva opcija za izračunavanje faktorijala biti nešto brža. Općenito, iterativna rješenja rade brže od rekurzivnih rješenja.

Prije nego što pređete na situacije u kojima je rekurzija korisna, razmotrite još jedan primjer gdje je ne biste trebali koristiti.

Razmotrimo poseban slučaj rekurentnih odnosa, kada sljedeća vrijednost u nizu ne ovisi o jednoj, već o nekoliko prethodnih vrijednosti odjednom. Primjer je dobro poznati Fibonačijev niz, u kojem je svaki sljedeći element zbir prethodna dva:

Sa "head-on" pristupom, možete napisati:

Funkcija Fib (n: cijeli broj): cijeli broj; početi ako je n> 1 onda Fib: = Fib (n-1) + Fib (n-2) inače Fib: = 1; kraj;

Svaki Fib poziv kreira dvije kopije sebe odjednom, svaka od kopija kreira još dvije, itd. Broj transakcija raste sa brojem n eksponencijalno, iako s iterativnim rješenjem, linearni in n broj operacija.

Zapravo, gornji primjer nas uči da to ne radimo KADA rekurzija ne treba da se koristi, i to KAKO ne bi trebalo da se koristi. Uostalom, ako postoji brzo iterativno (bazirano na petlji) rješenje, tada se ista petlja može implementirati korištenjem rekurzivne procedure ili funkcije. Na primjer:

// x1, x2 - početni uvjeti (1, 1) // n - broj tražene funkcije Fibonacci broja Fib (x1, x2, n: cijeli broj): cijeli broj; var x3: cijeli broj; započni ako je n> 1 onda započni x3: = x2 + x1; x1: = x2; x2: = x3; Fib: = Fib (x1, x2, n-1); kraj else Fib: = x2; kraj;

Ipak, preferiraju se iterativna rješenja. Pitanje je kada, u ovom slučaju, treba koristiti rekurziju?

Sve rekurzivne procedure i funkcije koje sadrže samo jedan rekurzivni poziv sebi mogu se lako zamijeniti iterativnim petljama. Da biste dobili nešto što nema jednostavan nerekurzivni analog, trebali biste se pozvati na procedure i funkcije koje se pozivaju dva ili više puta. U ovom slučaju, skup pozvanih procedura više ne čini lanac, kao na sl. 1, ali cijelo drvo. Postoje široke klase problema kada bi proces izračunavanja trebao biti organiziran na ovaj način. Za njih će rekurzija biti najlakši i najprirodniji način da se to riješi.

5. Drveće

Teorijska osnova za rekurzivne funkcije koje se nazivaju više puta je grana diskretne matematike koja proučava stabla.

5.1. Osnovne definicije. Načini predstavljanja drveća

definicija: konačni skup T koji se sastoji od jednog ili više čvorova tako da:
a) Postoji jedan poseban čvor koji se zove korijen ovog stabla.
b) Ostali čvorovi (isključujući korijen) sadržani su u parovima disjunktnim podskupovima, od kojih je svaki zauzvrat stablo. Drveće se zove podstabla ovo drvo.

Ova definicija je rekurzivna. Ukratko, drvo je skup koji se sastoji od korijena i podstabala vezanih za njega, a koja su također stabla. Stablo je definisano kroz sebe. Međutim, ova definicija ima smisla, budući da je rekurzija konačna. Svako podstablo sadrži manje čvorova od stabla koje sadrži. Na kraju dolazimo do podstabala koja sadrže samo jedan čvor, a već je jasno šta je to.

Rice. 3. Drvo.

Na sl. 3 prikazuje stablo sa sedam čvorova. Iako obična stabla rastu odozdo prema gore, uobičajeno je crtati ih obrnuto. Kada crtate dijagram rukom, ova metoda je očito prikladnija. Zbog ove nedosljednosti, ponekad nastaje zabuna kada se kaže da je jedan od čvorova iznad ili ispod drugog. Iz tog razloga, prikladnije je koristiti terminologiju koja se koristi pri opisivanju porodičnih stabala, pozivajući čvorove bliže korijenskim precima i udaljenije potomke.

Stablo se može grafički predstaviti na nekoliko drugih načina. Neki od njih su prikazani na sl. 4. Prema definiciji, stablo je sistem ugniježđenih skupova, gdje se ti skupovi ili ne seku ili su potpuno sadržani jedan u drugom. Takvi skupovi se mogu prikazati kao oblasti na ravni (slika 4a). Na sl. 4b, ugniježđeni skupovi se ne nalaze na ravni, već su prošireni u jednu liniju. Rice. 4b se također može smatrati dijagramom neke algebarske formule koja sadrži ugniježđene zagrade. Rice. 4c pruža još jedan popularan način prikazivanja strukture drveta kao ivice.

Rice. 4. Drugi načini prikazivanja struktura stabla: (a) ugniježđeni skupovi; (b) ugniježđene zagrade; (c) lista koncesija.

Kongruentna lista ima očigledne sličnosti sa načinom na koji je programski kod formatiran. Zaista, program napisan u okviru paradigme strukturiranog programiranja može se predstaviti kao stablo koje se sastoji od ugniježđenih konstrukcija.

Također možete povući analogiju između tabelarnog popisa i izgleda sadržaja u knjigama, gdje sekcije sadrže pododjeljke, one pak sadrže pododjeljke, itd. Tradicionalni način numerisanja takvih sekcija (odjeljak 1, pododjeljci 1.1 i 1.2, pododjeljak 1.1.2, itd.) naziva se Deweyjev decimalni sistem. Primijenjeno na stablo na sl. 3 i 4 ovaj sistem će dati:

1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Drveće u prolazu

U svim algoritmima povezanim sa strukturama stabla, uvijek se javlja jedna te ista ideja, odnosno ideja prolazeći ili prelazak stabla... Ovo je način posjete čvorovima stabla, u kojem se svaki čvor prelazi tačno jednom. Ovo rezultira linearnim rasporedom čvorova stabla. Konkretno, postoje tri načina: možete proći kroz čvorove naprijed, obrnuto i krajnjim redoslijedom.

Algoritam prelaska naprijed:

• Dođi do korijena,
• Pređite sva podstabla s lijeva na desno u direktnom redoslijedu.

Ovaj algoritam je rekurzivan, budući da obilaženje stabla sadrži prelazna podstabla, koja se, zauzvrat, prelaze prema istom algoritmu.

Konkretno, za stablo na Sl. 3 i 4, direktno prelazak daje niz čvorova: A, B, C, D, E, F, G.

Rezultirajuća sekvenca odgovara sekvencijalnom nabrajanju čvorova slijeva nadesno kada je predstavljeno stablom pomoću ugniježđenih zagrada i u Dewey-jevom decimalnom sistemu, kao i ide od vrha do dna kada je predstavljeno kao lista ivica.

Kada se ovaj algoritam implementira u programskom jeziku, pogodak u korijen odgovara izvršavanju određenih akcija od strane procedure ili funkcije, a prelazak podstabla odgovara rekurzivnim pozivima samoga sebe. Konkretno, za binarno stablo (gdje ne potiče više od dva podstabla iz svakog čvora), odgovarajuća procedura će izgledati ovako:

// Preorder Traversal je engleski naziv za proceduru direktne narudžbe PreorderTraversal ((Argumenti)); begin // Prolazak kroz korijen DoSomething ((Argumenti)); // Prelazi lijevo podstablo if (lijevo podstablo postoji) then PreorderTransversal ((Argumenti 2)); // Prelazak desnog podstabla if (Postoji desno podstablo) then PreorderTransversal ((Argumenti 3)); kraj;

To jest, prvo procedura izvodi sve akcije, a tek onda se javljaju svi rekurzivni pozivi.

Algoritam obrnutog prelaska:

• Pređite lijevo podstablo,
• Dođi do korijena,
• Pređite sljedeće podstablo s lijeve strane.
• Dođi do korijena,
• i tako dalje dok se ne pređe krajnje desno podstablo.

To jest, sva podstabla se prelaze s lijeva na desno, a povratak u korijen se nalazi između ovih prolaza. Za drvo na sl. 3 i 4 ovo daje niz čvorova: B, A, D, C, E, G, F.

U odgovarajućoj rekurzivnoj proceduri, akcije će biti postavljene između rekurzivnih poziva. Konkretno za binarno stablo:

// Inorder Traversal je engleski naziv za proceduru obrnutog reda InorderTraversal ((Argumenti)); begin // Prelazi lijevo podstablo if (lijevo podstablo postoji) then InorderTraversal ((Argumenti 2)); // Prolazak kroz korijen DoSomething ((Argumenti)); // Prelazak desnog podstabla if (Postoji desno podstablo) then InorderTraversal ((Argumenti 3)); kraj;

Algoritam prelaska s kraja na kraj:

• Pređite sva podstabla s lijeva na desno,
• Dođite do korijena.

Za drvo na sl. 3 i 4 ovo će dati niz čvorova: B, D, E, G, F, C, A.

U odgovarajućoj rekurzivnoj proceduri, akcije će se pojaviti nakon rekurzivnih poziva. Konkretno za binarno stablo:

// Postorder Traversal je engleski naziv za proceduru praćenja naloga PostorderTraversal ((Argumenti)); begin // Prelazi lijevo podstablo if (lijevo podstablo postoji) then PostorderTraversal ((Argumenti 2)); // Prelazak desnog podstabla if (Postoji desno podstablo) then PostorderTraversal ((Argumenti 3)); // Prolazak kroz korijen DoSomething ((Argumenti)); kraj;

5.3. Prikaz stabla u memoriji računara

Ako se neke informacije nalaze u čvorovima stabla, onda da biste ih pohranili, možete koristiti odgovarajuću dinamičku strukturu podataka. U Pascalu, ovo se radi pomoću varijable tipa record (record), koja sadrži pokazivače na podstabla istog tipa. Na primjer, binarno stablo gdje svaki čvor sadrži cijeli broj može se pohraniti korištenjem varijable tipa PTree, koja je opisana u nastavku:

Tip PTree = ^ TTree; TTree = zapis Inf: cijeli broj; LeftSubTree, RightSubTree: PTree; kraj;

Svaki čvor je tipa Ptree. Ovo je pokazivač, odnosno svaki čvor mora biti kreiran pozivanjem procedure New na njemu. Ako je čvor list, tada se njegovim poljima LeftSubTree i RightSubTree dodjeljuje vrijednost nula... Inače, čvorovi LeftSubTree i RightSubTree se takođe kreiraju procedurom New.

Jedan takav zapis je šematski prikazan na Sl. 5.

Rice. 5. Šematski prikaz TTree zapisa. Zapis ima tri polja: Inf - neki broj, LeftSubTree i RightSubTree - pokazivači na zapise istog tipa TTree.

Primjer stabla sastavljenog od takvih zapisa prikazan je na slici 6.

Rice. 6. Stablo koje se sastoji od TTree zapisa. Svaki zapis pohranjuje broj i dva pokazivača, koji mogu sadržavati bilo koji nula, ili adrese drugih zapisa istog tipa.

Ako do sada niste radili sa strukturama koje se sastoje od zapisa koji sadrže veze do zapisa istog tipa, preporučujemo da se upoznate sa materijalom o tome.

6. Primjeri rekurzivnih algoritama

6.1. Crtanje drveta

Razmotrite algoritam za crtanje stabla prikazan na Sl. 6. Ako se svaka linija smatra čvorom, onda ova slika sasvim zadovoljava definiciju stabla datu u prethodnom odeljku.

Rice. 6. Malo drvo.

Rekurzivna procedura bi očigledno trebala nacrtati jednu liniju (deblo prije prve račve), a zatim se pozivati ​​da nacrta dva podstabla. Podstabla se razlikuju od stabla koje ih sadrži po koordinatama početne tačke, kutu rotacije, dužini debla i broju grana koje sadrže (jedna manje). Sve ove razlike treba napraviti parametrima rekurzivne procedure.

Primjer takve procedure, napisan u Delphiju, predstavljen je u nastavku:

Stablo procedure (Canvas: TCanvas; // Platno na kojem će stablo biti nacrtano x, y: prošireno; // Koordinate korijena Ugao: prošireno; // Ugao pod kojim drvo raste TrunkLength: prošireno; // Dužina debla n: cijeli broj // Broj račva (koliko // rekurzivnih poziva tek treba pozvati)); var x2, y2: prošireno; // Kraj debla (tačka grananja) počinje x2: = x + TrunkLength * cos (Angle); y2: = y - Dužina stabla * sin (ugao); Canvas.MoveTo (okruglo (x), okruglo (y)); Canvas.LineTo (okrugla (x2), okrugla (y2)); ako je n> 1 onda počinje Stablo (Canvas, x2, y2, Angle + Pi / 4, 0.55 * TrunkLength, n-1); Stablo (Canvas, x2, y2, Angle-Pi / 4, 0.55 * TrunkLength, n-1); kraj; kraj;

Za dobijanje sl. 6 ova rutina je pozvana sa sljedećim parametrima:

Drvo (Slika 1. Platno, 175, 325, Pi / 2, 120, 15);

Imajte na umu da se crtanje vrši prije rekurzivnih poziva, odnosno da se stablo crta u direktnom redoslijedu.

6.2. Hanojske kule

Prema legendi, u Velikom hramu u Benarasu, ispod katedrale koja označava sredinu svijeta, nalazi se bronzani disk na koji su pričvršćene tri dijamantske šipke, visoke jedan lakat i debljine kao pčela. Davno, na samom početku vremena, monasi ovog manastira bili su krivi pred bogom Brahmom. Razjaren, Brahma je podigao tri visoka štapa i na jedan od njih stavio 64 diska od čistog zlata, tako da svaki manji disk leži na većem. Čim se sva 64 diska prenesu sa štapa, na koji ih je Bog Brahma stavio prilikom stvaranja svijeta, na drugi štap, toranj zajedno sa hramom će se pretvoriti u prah i svijet će propasti pod gromoglasnim kolutovima.
Proces zahtijeva da veći disk nikada ne premaši manji. Monasi su u teškoćama, kojim redosledom transpozicije? Potrebno ih je opremiti softverom za izračunavanje ovog niza.

Bez obzira na Brahmu, ovu zagonetku krajem 19. veka predložio je francuski matematičar Eduard Lukas. Prodata verzija obično je koristila 7-8 diskova (slika 7).

Rice. 7. Zagonetka "Hanojske kule".

Pretpostavimo da postoji rješenje za n-1 disk. Zatim za prebacivanje n diskova, postupite na sljedeći način:

1) Prebacivanje n-1 disk.
2) Prebacivanje n disk na preostali slobodni pin.
3) Prebacujemo hrpu od n-1 disk dobijen u koraku (1) preko n th disk.

Za slučaj n= 1, algoritam pomjeranja je očigledan, tada indukcijom koristeći akcije (1) - (3) možemo pomjeriti proizvoljan broj diskova.

Kreirajmo rekurzivnu proceduru koja ispisuje cijeli niz prijenosa za dati broj diskova. Takva procedura sa svakim svojim pozivom treba da ispisuje informaciju o jednom transferu (iz tačke 2 algoritma). Za prijenose iz stavki (1) i (3), procedura će se sama pozvati sa brojem diskova smanjenim za jedan.

// n - broj diskova // a, b, c - brojevi pinova. Prenos se vrši sa pin a, // na pin b sa pomoćnim pin c. procedura Hanoi (n, a, b, c: cijeli broj); započeti ako je n> 1, onda započeti Hanoi (n-1, a, c, b); writeln (a, "->", b); Hanoj ​​(n-1, c, b, a); end else writeln (a, "->", b); kraj;

Imajte na umu da skup rekurzivno pozvanih procedura u ovom slučaju formira stablo kojim se prelazi obrnutim redoslijedom.

6.3. Parsing aritmetičkih izraza

Zadatak raščlanjivanja je izračunavanje vrijednosti izraza koristeći postojeći niz koji sadrži aritmetički izraz i poznate vrijednosti varijabli uključenih u njega.

Proces izračunavanja aritmetičkih izraza može se predstaviti kao binarno stablo. Zaista, svaki od aritmetičkih operatora (+, -, *, /) zahtijeva dva operanda, koji će također biti aritmetički izrazi i, shodno tome, mogu se smatrati podstablima. Rice. 8 prikazuje primjer stabla koje odgovara izrazu:

Rice. 8. Stablo sintakse koje odgovara aritmetičkom izrazu (6).

U takvom stablu krajnji čvorovi će uvijek biti varijable (ovdje x) ili numeričke konstante, a svi interni čvorovi će sadržavati aritmetičke operatore. Da biste izvršili operator, prvo morate procijeniti njegove operande. Dakle, drvo na slici treba preći krajnjim redom. Odgovarajući niz čvorova

pozvao obrnuti poljski zapis aritmetički izraz.

Kada konstruišete stablo sintakse, obratite pažnju na sledeću osobinu. Ako postoji, na primjer, izraz

a mi ćemo čitati operacije sabiranja i oduzimanja s lijeva na desno, tada će ispravno stablo sintakse sadržavati minus umjesto plusa (slika 9a). U stvari, ovo stablo odgovara izrazu.Moguće je olakšati konstrukciju stabla ako se izraz (8) analizira naprotiv, s desna na lijevo. U ovom slučaju, drvo sa sl. 9b, što je ekvivalentno stablu 8a, ali ne zahtijeva zamjenu znakova.

Slično, s desna na lijevo, trebate raščlaniti izraze koji sadrže operatore množenja i dijeljenja.

Rice. 9. Stabla sintakse za izražavanje a – b + c kada čitate s lijeva na desno (a) i s desna na lijevo (b).

Ovaj pristup ne eliminira u potpunosti rekurziju. Međutim, omogućava vam da se ograničite na samo jedan poziv rekurzivne procedure, što može biti dovoljno ako je motiv briga za maksimalnu performansu.

7.3. Određivanje čvora stabla po broju

Ideja iza ovog pristupa je zamijeniti rekurzivne pozive jednostavnom petljom koja će se izvršiti onoliko puta koliko ima čvorova u stablu formiranom rekurzivnim procedurama. Šta će se tačno uraditi na svakom koraku treba odrediti brojem koraka. Usporediti broj koraka i potrebne radnje nije trivijalan zadatak i u svakom slučaju morat će se rješavati zasebno.

Na primjer, pretpostavimo da želite izvršiti k ugniježđene petlje preko n koraci u svakom:

Za i1: = 0 do n-1 uradi za i2: = 0 do n-1 uradi za i3: = 0 do n-1 uradi ...

Ako k nije poznato unaprijed, onda ih je nemoguće eksplicitno napisati, kao što je gore prikazano. Koristeći tehniku ​​prikazanu u Odjeljku 6.5, možete dobiti potreban broj ugniježđenih petlji koristeći rekurzivnu proceduru:

Procedura NestedCycles (Indeksi: niz cijelih brojeva; n, k, dubina: cijeli broj); var i: cijeli broj; početi ako dubina

Da biste se riješili rekurzije i sveli sve na jednu petlju, imajte na umu da ako numerirate korake u radixu n, tada svaki korak ima broj koji se sastoji od cifara i1, i2, i3, ... ili odgovarajućih vrijednosti iz niza Indeksi. Odnosno, brojevi odgovaraju vrijednostima brojača ciklusa. Broj koraka u uobičajenom decimalnom sistemu:

Ukupni koraci će biti n k... Prolaskom kroz njihove brojeve u sistemu decimalnog zapisa i prevođenjem svakog od njih u sistem sa radiksom n, dobijamo vrijednosti indeksa:

M: = okrugli (IntPower (n, k)); za i: = 0 do M-1 započnite Broj: = i; za p: = 0 do k-1 početi Indeksi: = Broj mod n; Broj: = Broj div n; kraj; DoSomething (Indeksi); kraj;

Još jednom napominjemo da metoda nije univerzalna i da ćete za svaki zadatak morati smisliti nešto svoje.

Kontrolna pitanja

1. Odredite šta će sljedeće rekurzivne procedure i funkcije učiniti.

(a) Šta će sljedeća procedura ispisati kada se pozove Rec (4)?

Procedure Rec (a: cijeli broj); započeti pisanje (a); ako je a> 0 onda Rec (a-1); pisati (a); kraj;

(b) Kolika će biti vrijednost funkcije Nod (78, 26)?

Funkcija Nod (a, b: cijeli broj): cijeli broj; početi ako a> b onda Nod: = Nod (a - b, b) inače ako b> a onda Nod: = Nod (a, b - a) inače Nod: = a; kraj;

(c) Šta će sljedeće procedure ispisati prilikom pozivanja A (1)?

Procedura A (n: cijeli broj); postupak B (n: cijeli broj); postupak A (n: cijeli broj); započeti pisanje (n); B (n-1); kraj; postupak B (n: cijeli broj); započeti pisanje (n); ako n

(d) Šta će sljedeća procedura ispisati kada se poziva BT (0, 1, 3)?

Procedura BT (x: real; D, MaxD: cijeli broj); početi ako je D = MaxD onda upišiln (x) inače počinje BT (x - 1, D + 1, MaxD); BT (x + 1, D + 1, MaxD); kraj; kraj;

2. Ouroboros - zmija koja proždire sopstveni rep (slika 14) kada je rasklopljen ima dužinu L, prečnik blizu glave D, debljina trbušnog zida d... Odredite koliko repa može stati u sebe i u koliko slojeva će rep biti položen nakon toga?

Rice. 14. Rasklopljeni ouroboros.

3. Za drvo na sl. 10a pokazuje redoslijed posjećivanja čvorova za redoslijed prelaska naprijed, nazad i od kraja do kraja.

4. Nacrtajte grafički prikaz stabla, definisan pomoću ugniježđenih zagrada: (A (B (C, D), E), F, G).

5. Nacrtajte stablo sintakse za sljedeći aritmetički izraz:

Napišite ovaj izraz u obrnutoj poljskoj notaciji.

6. Za grafikon ispod (Slika 15), zapišite matricu susjedstva i matricu incidencije.

Zadaci

1. Nakon što ste izračunali faktorijel dovoljno veliki broj puta (milion ili više), uporedite efikasnost rekurzivnog i iterativnog algoritama. Koliko puta će se razlikovati vrijeme izvršenja i kako će ovaj omjer zavisiti od broja čiji se faktorijel izračunava?

2. Napišite rekurzivnu funkciju koja provjerava ispravne zagrade u nizu. Pravilnim postavljanjem su ispunjeni sljedeći uslovi:

(a) broj otvarajućih i završnih zagrada je jednak.
(b) unutar bilo kog para otvaranja - odgovarajućih završnih zagrada, zagrade su ispravno postavljene.

Primjeri pogrešnog postavljanja:) (, ()) (, ()) ((), itd.

3. Red može sadržavati zagrade, i zagrade i uglaste zagrade. Svaka otvorena zagrada odgovara zatvaranju istog tipa (okrugla - okrugla, kvadratna - kvadratna). Napišite rekurzivnu funkciju da provjerite da li su zagrade ispravne u ovom slučaju.

Primjer pogrešnog postavljanja: ([)].

4. Broj ispravnih struktura zagrada dužine 6 je 5: () () (), (()) (), () (()), ((())), (() ())..
Napišite rekurzivni program za generiranje svih ispravnih struktura zagrada dužine 2 n.

Indikacija: Ispravna struktura zagrada sa minimalnom dužinom "()". Duže strukture se dobijaju od kraćih na dva načina:

(a) ako je manja struktura zatvorena u zagradama,
(b) ako su dvije manje strukture napisane uzastopno.

5. Kreirajte rutinu koja ispisuje sve moguće permutacije za cijele brojeve od 1 do N.

6. Kreirajte proceduru koja ispisuje sve podskupove skupa (1, 2,…, N).

7. Kreirajte proceduru koja ispisuje sve moguće reprezentacije prirodnog broja N kao zbir drugih prirodnih brojeva.

8. Kreirajte funkciju koja izračunava zbir elemenata niza prema sljedećem algoritmu: niz se dijeli na pola, zbroji elemenata u svakoj polovini se broje i sabiraju. Zbir elemenata u polovini niza izračunava se pomoću istog algoritma, odnosno opet dijeljenjem na pola. Podjele se dešavaju sve dok rezultirajući dijelovi niza ne sadrže po jedan element i izračunavanje sume, odnosno, ne postane trivijalno.

Komentar: Ovaj algoritam je alternativa. U slučaju nizova realnih vrijednosti, obično vam omogućava da dobijete manje greške zaokruživanja.

10. Kreirajte proceduru koja crta Kochovu krivu (slika 12).

11. Reproducirajte sl. 16. Na slici, pri svakoj narednoj iteraciji, krug je 2,5 puta manji (ovaj koeficijent se može napraviti kao parametar).

Književnost

1.D. Knut. Umetnost kompjuterskog programiranja. v. 1. (Odjeljak 2.3. "Drveće").
2. N. Virt. Algoritmi i strukture podataka.

Funkcije: rekurzivno dato funkcija u svojoj definiciji sadrži samu sebe, posebno, funkcija definisana rekurzivnom formulom je rekurzivna. Dakle, jedan izraz može dati beskonačan skup metoda za izračunavanje funkcije, definirati skup objekata kroz sebe koristeći prethodno date privatne definicije.

Podaci

Struktura element_of_list (element_of_list * next; / * veza do sljedećeg elementa istog tipa * / int podaci; / * neki podaci * /);

Rekurzivna struktura podataka često diktira upotrebu rekurzije za obradu tih podataka.

U fizici

Klasičan primjer beskonačne rekurzije su dva ogledala okrenuta jedno prema drugom: u njima se formiraju dva hodnika sve manje refleksije ogledala.

Drugi primjer beskonačne rekurzije je efekat samopobude (pozitivna povratna sprega) elektronskih kola za pojačavanje, gdje signal sa izlaza ulazi na ulaz, pojačava se, ponovo ulazi na ulaz kola i ponovo se pojačava. Pojačala za koje je ovaj način rada standardan nazivaju se oscilatori.

U lingvistici

Sposobnost jezika da generiše ugniježđene rečenice i konstrukcije. Osnovna ponuda" mačka je pojela miša"Može se proširiti rekurzijom kao Vanja je pogodila da je mačka pojela miša, zatim kao Katya zna da je Vanja pogodila da je mačka pojela miša itd. Rekurzija se smatra jednom od lingvističkih univerzalija, odnosno karakteristična je za svaki prirodni jezik. Međutim, nedavno se vodila aktivna rasprava o mogućem odsustvu rekurzije u jednom od jezika Amazone - Piraha, što primjećuje lingvista Daniel Everett ( engleski) .

U kulturi

Većina viceva o rekurziji tiče se beskonačne rekurzije, u kojoj nema izlaznog uslova, na primjer, poznata je izreka: "da biste razumjeli rekurziju, prvo morate razumjeti rekurziju".

Vrlo popularan vic o rekurziji, koji podsjeća na unos iz rječnika:

Nekoliko priča Stanislava Lema posvećeno je (mogućim) incidentima sa beskonačnim ponavljanjem:

• priča o Jonu Tihiju "Četrnaesto putovanje" iz "Zvezdanih dnevnika Ijona Tihija", u kojoj junak uzastopno prelazi od članka o sepulki do članka o sepulaciji, odatle do članka o sepulkariji, u kojem se opet referenca na članak "sepulki":

Našao sam sljedeće kratke informacije:
„SEPULKI su važan element civilizacije Ardrit (vidi) sa planete Enteropia (vidi). Vidi SEPULCARIA".
Poslušao sam ovaj savjet i pročitao:
"SEPULKARIA - uređaji za razdvajanje (vidi)".
Tražio sam Sepulenie; pisalo je:
„SEPULENIE je zanimanje ardrita (vidi) sa planete Enteropia (vidi). Vidi SEPULKI".

Lem S. „Zvezdani dnevnici Ijona Tihija. Putovanje četrnaesto."

• Priča iz "Cyberiade" o inteligentnoj mašini koja je posjedovala dovoljno inteligencije i lijenosti da napravi sličnu da riješi zadatak i povjeri mu rješenje (rezultat je bila beskrajna rekurzija, kada je svaka nova mašina napravila sličnu i prošla zadatak za to).
• Rekurzivne akronimi: GNU (GNU nije Unix), PHP (PHP: Hypertext Preprocessor), itd.

vidi takođe

• Obrnuti niz

Bilješke (uredi)

Wikimedia fondacija. 2010.

• Video memorija
• Elektromagnetno zračenje

Pogledajte šta je "Rekurzija" u drugim rječnicima:

rekurzija- povratak, ponavljanje Rječnika ruskih sinonima. rekurzivna imenica, broj sinonima: 1 ... Rečnik sinonima

rekurzija- - [] rekurzija U opštem smislu, izračunavanje funkcije prema određenom algoritmu. Primjeri takvih algoritama su ponavljajuće formule koje izvode izračunavanje datog pojma ... ... Vodič za tehničkog prevodioca

Rekurzija- u opštem smislu, izračunavanje funkcije prema određenom algoritmu. Primjeri takvih algoritama su rekurentne formule koje izvode izračunavanje datog člana niza (najčešće numeričkog) iz izračunavanja nekoliko prethodnih ... Ekonomsko-matematički rječnik

Rekurzija- Terapijski obrazac, kada se neki uslov ili kriterijum formulisan u originalnoj izjavi uzima i primenjuje na samu izjavu. Na primjer: Nemam vremena. Koliko ste vremena morali da potrošite da biste bili sigurni da imate ... ... Velika psihološka enciklopedija

RECURSION- način definiranja funkcija, koji je predmet proučavanja u teoriji algoritama i drugim dijelovima matematike. logika. Ova metoda se dugo koristila u aritmetici za određivanje numeričkih nizova (progresije, Fibonačijevi brojevi, itd.). Enciklopedija matematike

rekurzija- (pozadina.) (lat. recursio povratak). Jedna od tri faze artikulacije zvukova, uvlačenje. Prevođenje govornih organa u mirno stanje ili početak artikulacije sljedećeg zvuka. U riječi odmor, rekurzija (uvlačenje) pri artikulaciji [t] može se preklapati sa ... ... Rječnik lingvističkih pojmova T.V. Ždrebe

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 pomoću 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.