Rekurzija i rekurzivni algoritmi. Što je rekurzija

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 .

Pozdrav Habrahabr!

U ovom ćemo članku govoriti o problemima rekurzije i kako ih riješiti.

Ukratko o rekurziji

Rekurzija je prilično čest fenomen koji se ne pojavljuje samo u područjima znanosti, već iu svakodnevnom životu. Na primjer, Drosteov efekt, trokut Sierpinskog, itd. Jedan od načina da vidite rekurziju je usmjeriti web kameru na zaslon monitora računala, naravno, nakon što ste je 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).

Puno je rečeno o rekurziji. Evo nekoliko dobrih izvora:

• Rekurzija i rekurzivni problemi. Područja primjene rekurzije

Pretpostavlja se da je čitatelj teoretski upoznat s rekurzijom i da zna što je to. U ovom ćemo članku više pažnje posvetiti problemima rekurzije.

Zadaci

Kada se uči rekurzija, najučinkovitiji način za razumijevanje rekurzije je rješavanje problema.

Kako riješiti probleme rekurzije?

Prije svega, morate shvatiti da je rekurzija neka vrsta pretjeranog rada. Općenito govoreći, sve što se rješava iterativno može se riješiti i rekurzivno, odnosno pomoću rekurzivne funkcije.

iz mreže

Svaki algoritam implementiran u rekurzivnom obliku može se prepisati u iterativnom obliku i obrnuto. Ostaje pitanje je li to potrebno i koliko će biti učinkovito.

Sljedeći argumenti mogu se dati da se to opravda.

Za početak se možemo prisjetiti definicije rekurzije i iteracije. Rekurzija je način organizacije obrade podataka u kojem program poziva sam sebe izravno 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 čega možemo zaključiti da su međusobno zamjenjivi, ali ne uvijek s istim troškovima u smislu resursa i brzine. Da bismo to opravdali, možemo navesti sljedeći primjer: postoji funkcija u kojoj, kako bi se organizirao određeni algoritam, postoji petlja koja izvodi niz radnji ovisno o trenutnoj vrijednosti brojača (možda ne ovisi o to). Budući da postoji ciklus, to znači da tijelo ponavlja slijed radnji - ponavljanja ciklusa. Možete premjestiti operacije u zasebnu podrutinu i proslijediti joj vrijednost brojača, ako postoji. Po završetku izvođenja potprograma provjeravamo uvjete za izvođenje petlje, te ako je istinit, prelazimo na novi poziv potprograma, ako je netočan, završavamo izvršenje. Jer Sav sadržaj petlje smjestili smo u potprogram, što znači da se u potprogramu nalazi i uvjet za izvođenje petlje, a može se dobiti kroz povratnu vrijednost funkcije, parametre proslijeđene referencom ili pokazivačem na podprogram , kao i globalne varijable. Nadalje, lako je pokazati da se poziv određenog potprograma iz petlje može lako pretvoriti u poziv ili nepoziv (vraćanje vrijednosti ili jednostavno dovršavanje posla) potprograma iz samog sebe, vođen nekim uvjetima (onima da prethodno bili u stanju petlje). Sada, ako pogledate naš apstraktni program, to otprilike izgleda kao prosljeđivanje vrijednosti potprogramu i njihovo korištenje, koje će potprogram promijeniti kada završi, tj. zamijenili smo iterativnu petlju rekurzivnim pozivom potprograma za rješavanje zadanog algoritma.

Zadatak dovođenja rekurzije u iterativni pristup je simetričan.

Ukratko, možemo izraziti sljedeće misli: za svaki pristup postoji vlastita klasa zadataka, koja je određena specifičnim zahtjevima za određeni zadatak.

Možete saznati više o ovome

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

Dakle, rekurzivna funkcija se sastoji od

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

Pogledajmo ovo na primjeru pronalaženja faktorijela:

Javna klasa Rješenje ( public static int recursion(int n) ( // uvjet izlaza // Osnovni slučaj // kada prestati ponavljati rekurziju? if (n == 1) ( return 1; ) // Korak rekurzije / povratak rekurzivnog uvjeta recursion( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // poziv rekurzivne funkcije ) )

Ovdje je osnovni uvjet uvjet kada je n=1. Pošto znamo da je 1!=1 i izračunati 1! ne trebamo ništa. Za izračun 2! možemo koristiti 1!, tj. 2!=1!*2. Za izračun 3! trebamo 2!*3... Da bismo izračunali n! trebamo (n-1)!*n. Ovo je korak rekurzije. Drugim riječima, da bismo dobili faktorijel broja n, dovoljno je faktorijel prethodnog broja pomnožiti s n.

Oznake:

• rekurzija
• zadaci
• Java

Dodaj oznake

Rekurzija je kada podrutina poziva samu sebe. Kada se po prvi put suoči s takvim algoritamskim dizajnom, većina ljudi ima određene poteškoće, ali uz malo vježbe, rekurzija će postati razumljiv i vrlo koristan alat u vašem programerskom arsenalu.

1. Bit rekurzije

Procedura ili funkcija može sadržavati pozive drugih procedura ili funkcija. Postupak se također može sam pozvati. Ovdje nema paradoksa – računalo samo sekvencijalno izvršava naredbe na koje naiđe u programu i, ako naiđe na poziv procedure, jednostavno počinje izvršavati ovu proceduru. Nije važno koja je procedura dala naredbu da se to učini.

Primjer rekurzivnog postupka:

Procedura Rec(a: integer); početi ako a>

Razmotrimo što se događa ako se u glavnom programu izvrši poziv, na primjer, oblika Rec(3). Ispod je dijagram toka koji prikazuje redoslijed izvršavanja naredbi.

Riža. 1. Blok dijagram rekurzivnog postupka.

Procedura Rec se poziva s parametrom a = 3. Sadrži poziv procedure Rec s parametrom a = 2. Prethodni poziv još nije završio, pa možete zamisliti da je kreirana druga procedura, a prva ne završi svoj posao sve dok završava. Proces pozivanja završava kada je parametar a = 0. U ovoj točki, 4 instance procedure se izvode istovremeno. Naziva se broj istovremeno izvedenih postupaka dubina rekurzije.

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

Druga vizualna slika onoga što se događa prikazana je na sl. 2.

Riža. 2. Izvršenje Rec procedure s parametrom 3 sastoji se od izvršavanja Rec procedure s parametrom 2 i ispisa broja 3. S druge strane, izvršavanje Rec procedure s parametrom 2 sastoji se od izvršavanja Rec procedure s parametrom 1 i ispisa broja 2. Itd. .

Kao vježbu za sebe, razmislite što se događa kada pozovete Rec(4). Također razmislite što bi se dogodilo da pozovete proceduru Rec2(4) u nastavku, s obrnutim operatorima.

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

Imajte na umu da je u ovim primjerima rekurzivni poziv unutar uvjetne naredbe. Ovo je nužan uvjet da bi rekurzija ikada završila. Također imajte na umu da procedura sama sebe poziva s drugačijim parametrom od onog s kojim je pozvana. Ako procedura ne koristi globalne varijable, onda je i to potrebno kako se rekurzija ne bi nastavila unedogled.

Moguća je malo složenija shema: funkcija A poziva funkciju B, koja pak poziva A. Ovo se zove složena rekurzija. Ispada da prva opisana procedura mora pozvati proceduru koja još nije opisana. Da bi to bilo moguće, morate koristiti .

Procedura A(n: cijeli broj); (Naprijed opis (zaglavlje) prve procedure) procedure B(n: integer); (Naprijed opis druge procedure) procedure A(n: integer); (Potpuni opis procedure A) begin writeln(n); B(n-1); kraj; procedura B(n: cijeli broj); (Potpuni opis procedure B) begin writeln(n); ako n

Deklaracija za prosljeđivanje procedure B omogućuje da se pozove iz procedure A. Deklaracija za prosljeđivanje procedure A nije potrebna u ovom primjeru i dodaje se iz estetskih razloga.

Ako se obična rekurzija može usporediti s ouroborosom (Sl. 3), onda se slika složene rekurzije može izvući iz poznate dječje pjesme, gdje su se "Vukovi prestrašili i pojeli jedni druge." Zamislite dva vuka kako jedu jedan drugoga i shvatit ćete složenu rekurziju.

Riža. 3. Ouroboros - zmija koja proždire vlastiti rep. Crtež iz alkemijske rasprave “Synosius” Theodorea Pelecanosa (1478.).

Riža. 4. Složena rekurzija.

3. Simulacija petlje pomoću rekurzije

Ako procedura pozove samu sebe, ona u biti uzrokuje ponovno izvršavanje instrukcija koje sadrži, slično petlji. Neki programski jezici uopće ne sadrže konstrukcije petlji, ostavljajući programerima da organiziraju ponavljanja pomoću rekurzije (na primjer, Prolog, gdje je rekurzija osnovna 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: integer); (Prvi parametar je brojač koraka, drugi parametar je ukupan broj koraka) begin writeln("Hello N ", i); //Ovdje su upute koje će se ponoviti ako i

Rezultat poziva obrasca LoopImitation(1, 10) bit će izvršenje instrukcija deset puta, mijenjajući brojač s 1 na 10. U ovom slučaju bit će ispisano sljedeće:

Pozdrav N1
Pozdrav N 2
…
Pozdrav N 10

Općenito, nije teško vidjeti da su parametri postupka granice za promjenu vrijednosti brojača.

Možete zamijeniti rekurzivni poziv i upute koje se ponavljaju, kao u sljedećem primjeru.

Primjer 2.

Procedura LoopImitation2(i, n: integer); početi ako ja

U ovom slučaju, poziv rekurzivne procedure dogodit će se prije nego što se upute počnu izvršavati. Nova instanca procedure također će prije svega pozvati drugu instancu, i tako sve dok ne postignemo maksimalnu vrijednost brojača. Tek nakon toga posljednja od pozvanih procedura izvršit će svoje instrukcije, potom će pretposljednja izvršiti svoje instrukcije itd. Rezultat pozivanja LoopImitation2(1, 10) bit će ispis pozdrava obrnutim redoslijedom:

Pozdrav N 10
…
Pozdrav N1

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

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

Procedura LoopImitation3(i, n: integer); begin writeln("Zdravo N ", i); (Prvi blok uputa može se nalaziti ovdje) ako i

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

Pozdrav N1
…
Pozdrav N 10
Pozdrav N 10
…
Pozdrav N1

Bile bi potrebne dvije petlje da se napravi ista stvar bez rekurzije.

Možete iskoristiti činjenicu da je izvođenje dijelova iste procedure vremenski razmaknuto. Na primjer:

Primjer 3: Pretvaranje broja u binarni.

Dobivanje znamenki binarnog broja, kao što je poznato, događa se dijeljenjem s ostatkom s bazom brojevnog sustava 2. Ako postoji broj, tada je njegova zadnja znamenka u binarnom prikazu jednaka

Uzimajući cijeli dio dijeljenja s 2:

dobivamo broj koji ima isti binarni prikaz, ali bez zadnje znamenke. Dakle, dovoljno je ponavljati gornje dvije operacije dok sljedeće polje za dijeljenje ne dobije cjelobrojni dio 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 znamenke binarne reprezentacije računaju obrnutim redoslijedom (prvo najnovije). Da biste ispisali broj u normalnom obliku, morat ćete zapamtiti sve brojeve u elementima niza i ispisati ih u zasebnoj petlji.

Koristeći rekurziju, nije teško postići ispis ispravnim redoslijedom bez niza i druge petlje. Naime:

Procedura BinaryRepresentation(x: integer); var c, x: cijeli broj; begin (Prvi blok. Izvršava se redoslijedom poziva procedura) c:= x mod 2; x:= x div 2; (Rekurzivni poziv) if x>0 then BinaryRepresentation(x); (Drugi blok. Izvršava se obrnutim redoslijedom) write(c); kraj;

Općenito govoreći, nismo dobili nikakve dobitke. Znamenke binarnog prikaza pohranjene su u lokalnim varijablama koje su različite za svaku instancu rekurzivne procedure koja se izvodi. Odnosno, nije bilo moguće spremiti memoriju. Naprotiv, gubimo dodatnu memoriju pohranjujući mnoge lokalne varijable x. Međutim, ovo rješenje mi se čini lijepim.

4. Rekurentne relacije. Rekurzija i iteracija

Za slijed vektora kaže se da je zadan relacijom ponavljanja ako su zadani početni vektor i funkcionalna ovisnost sljedećeg vektora o prethodnom

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

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

Uvođenjem oznake dobivamo relaciju:

Vektori iz formule (1) mogu se interpretirati kao skupovi varijabilnih vrijednosti. Tada će se izračun potrebnog elementa niza sastojati od ponovljenog ažuriranja njihovih vrijednosti. Posebno za faktorijele:

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

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

Napomenimo, međutim, da je relacija (1) čisto rekurzivna definicija niza i da je izračun n-tog elementa zapravo opetovano uzimanje funkcije f od same sebe:

Konkretno, za faktorijel se može napisati:

Funkcija Faktorij(n: cijeli broj): cijeli broj; start if n > 1 then Faktorijel:= n * Faktorijel(n-1) else Faktorijel:= 1; kraj;

Treba imati na umu da pozivanje funkcija podrazumijeva neke dodatne troškove, tako da će prva opcija za izračun faktorijela biti malo brža. Općenito, iterativna rješenja rade brže od rekurzivnih.

Prije nego prijeđemo na situacije u kojima je rekurzija korisna, pogledajmo još jedan primjer gdje se ne bi trebala koristiti.

Razmotrimo poseban slučaj ponavljajućih odnosa, kada sljedeća vrijednost u nizu ne ovisi o jednoj, već o nekoliko prethodnih vrijednosti odjednom. Primjer je poznati Fibonaccijev niz, u kojem je svaki sljedeći element zbroj prethodna dva:

Uz "frontalni" pristup, možete napisati:

Funkcija Fib(n: integer): cijeli broj; start if n > 1 then Fib:= Fib(n-1) + Fib(n-2) else Fib:= 1; kraj;

Svaki Fib poziv stvara dvije kopije sebe, svaka kopija stvara još dvije, i tako dalje. Broj operacija raste s brojem n eksponencijalno, iako s linearnim iterativnim rješenjem n broj operacija.

Zapravo, gornji primjer nas ne uči KADA rekurzija se ne bi trebala koristiti, inače KAKO ne treba ga koristiti. Uostalom, ako postoji brzo iterativno (temeljeno na petlji) rješenje, tada se ista petlja može implementirati pomoću rekurzivne procedure ili funkcije. Na primjer:

// x1, x2 – početni uvjeti (1, 1) // n – broj tražene funkcije Fibonaccijevog broja Fib(x1, x2, n: integer): integer; var x3: cijeli broj; start ako je n > 1 onda početak x3:= x2 + x1; x1:= x2; x2:= x3; Fib:= Fib(x1, x2, n-1); end else Fib:= x2; kraj;

Ipak, poželjna su iterativna rješenja. Pitanje je kada bi se u ovom slučaju trebala koristiti rekurzija?

Sve rekurzivne procedure i funkcije koje sadrže samo jedan rekurzivni poziv same sebi mogu se lako zamijeniti iterativnim petljama. Da biste dobili nešto što nema jednostavan nerekurzivni pandan, trebate pribjeći procedurama i funkcijama koje same sebe pozivaju dva ili više puta. U ovom slučaju, skup pozvanih procedura više ne čini lanac, kao na sl. 1, već cijelo stablo. Postoje široke klase problema kada se računski proces mora organizirati na ovaj način. Za njih će rekurzija biti najjednostavnije i najprirodnije rješenje.

5. Drveće

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

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

Definicija: nazvat ćemo 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) Preostali čvorovi (isključujući korijen) sadržani su u disjunktnim podskupovima, od kojih je svaki zauzvrat stablo. Drveće se zove podstabla ovog drveta.

Ova je definicija rekurzivna. Ukratko, stablo je skup koji se sastoji od korijena i na njega vezanih podstabala, koja su također stabla. Stablo je definirano kroz sebe. Međutim, ova definicija ima smisla jer je rekurzija konačna. Svako podstablo sadrži manje čvorova od stabla koje ga sadrži. Na kraju dolazimo do podstabala koja sadrže samo jedan čvor, a tu je već jasno o čemu se radi.

Riža. 3. Drvo.

Na sl. Slika 3 prikazuje stablo sa sedam čvorova. Iako obična stabla rastu odozdo prema gore, uobičajeno ih je crtati obrnuto. Kada ručno crtate dijagram, ova je metoda očito prikladnija. Zbog ove nedosljednosti ponekad dolazi do zabune kada se kaže da je jedan čvor iznad ili ispod drugog. Zbog toga je prikladnije koristiti terminologiju koja se koristi pri opisivanju obiteljskih stabala, nazivajući čvorove bliže korijenskim precima, a udaljenije potomcima.

Drvo se grafički može prikazati na neke druge načine. Neki od njih prikazani su na sl. 4. Prema definiciji, stablo je sustav ugniježđenih skupova, pri čemu se ti skupovi ili ne sijeku ili su potpuno sadržani jedan u drugom. Takvi skupovi mogu se prikazati kao regije na ravnini (slika 4a). Na sl. 4b, ugniježđeni skupovi nisu smješteni u ravnini, već su izduženi u jednu liniju. Riža. Slika 4b također se može promatrati kao dijagram neke algebarske formule koja sadrži ugniježđene zagrade. Riža. Slika 4c daje još jedan popularan način predstavljanja strukture stabla kao raspoređeni popis.

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

Rasporedni popis ima očite sličnosti s načinom na koji je programski kod formatiran. Doista, program napisan u okviru paradigme strukturiranog programiranja može se prikazati kao stablo koje se sastoji od ugniježđenih struktura.

Također možete povući analogiju između stepenastog popisa i izgleda tablica sadržaja u knjigama, gdje odjeljci sadrže pododjeljke, koji zauzvrat sadrže pododjeljke itd. Tradicionalni način numeriranja takvih odjeljaka (odjeljak 1, pododjeljci 1.1 i 1.2, pododjeljak 1.1.2 itd.) naziva se Deweyev decimalni sustav. Primijenjeno na stablo na sl. 3 i 4 ovaj sustav će dati:

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

5.2. Prolazeće drveće

U svim algoritmima koji se odnose na strukture stabla uvijek se pojavljuje ista ideja, naime ideja pretjecanje ili obilazak stabla. Ovo je način posjećivanja čvorova stabla u kojem se svaki čvor obilazi točno jednom. To rezultira linearnim rasporedom čvorova stabla. Konkretno, postoje tri načina: možete ići kroz čvorove prema naprijed, unazad i na kraju.

Algoritam za prolazak naprijed:

• Dođite do korijena
• Prođite kroz sva podstabla s lijeva na desno izravnim redoslijedom.

Ovaj algoritam je rekurzivan, budući da obilazak stabla sadrži obilazak podstabala, a ona se zauzvrat obilaze korištenjem istog algoritma.

Konkretno, za stablo na Sl. 3 i 4, izravno obilaženje daje niz čvorova: A, B, C, D, E, F, G.

Rezultirajući niz odgovara nabrajanju čvorova slijeva nadesno kada se stablo predstavlja pomoću ugniježđenih zagrada i u Deweyevom decimalnom zapisu, kao i odlomku odozgo prema dolje kada se predstavlja kao raspoređeni popis.

Kada se ovaj algoritam implementira u programskom jeziku, pogađanje korijena odgovara proceduri ili funkciji koja izvodi neke akcije, a prolazak kroz podstabla odgovara rekurzivnim pozivima samoj sebi. Konkretno, za binarno stablo (gdje svaki čvor ima najviše dva podstabla), odgovarajući postupak bi izgledao ovako:

// Preorder Traversal – engleski naziv za izravnu narudžbu procedure PreorderTraversal((Arguments)); početak //Prosljeđivanje korijena DoSomething((Argumenti)); //Tranzicija lijevog podstabla if (Postoji lijevo podstablo) then PreorderTransversal((Argumenti 2)); //Tranzicija desnog podstabla if (Postoji desno podstablo) then PreorderTransversal((Argumenti 3)); kraj;

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

Algoritam obrnutog prolaska:

• Prođite kroz lijevo podstablo,
• Dođite do korijena
• Prođite kroz sljedeće podstablo lijevo.
• Dođite do korijena
• itd. dok se ne prijeđe krajnje desno podstablo.

To jest, sva podstabla se obilaze slijeva nadesno, a povratak na korijen se nalazi između tih obilazaka. Za stablo na Sl. 3 i 4 to daje slijed čvorova: B, A, D, C, E, G, F.

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

// Inorder Traversal – engleski naziv za proceduru obrnutog reda InorderTraversal((Argumenti)); početak //Putovanje lijevim podstablom if (Lijevo podstablo postoji) then InorderTraversal((Argumenti 2)); //Prosljeđivanje korijena DoSomething((Argumenti)); //Kroz desno podstablo if (Desno podstablo postoji) then InorderTraversal((Argumenti 3)); kraj;

Algoritam za prolaz krajnjeg reda:

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

Za stablo na Sl. 3 i 4 to će dati slijed čvorova: B, D, E, G, F, C, A.

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

// Postorder Traversal – engleski naziv za krajnju proceduru naloga PostorderTraversal((Arguments)); početak //Putovanje lijevim podstablom if (Postoji lijevo podstablo) then PostorderTraversal((Argumenti 2)); //Nadilaženje desnog podstabla if (Desno podstablo postoji) then PostorderTraversal((Argumenti 3)); //Prosljeđivanje korijena DoSomething((Argumenti)); kraj;

5.3. Prikaz stabla u memoriji računala

Ako se neke informacije nalaze u čvorovima stabla, tada se za njihovu pohranu može koristiti odgovarajuća dinamička struktura podataka. U Pascalu se to radi pomoću varijable tipa zapisa koja sadrži pokazivače na podstabla istog tipa. Na primjer, binarno stablo u kojem svaki čvor sadrži cijeli broj može se pohraniti pomoću varijable tipa PTree, koja je opisana u nastavku:

Upišite PTree = ^TTree; TTree = zapis Inf: cijeli broj; Lijevo podstablo, desno podstablo: PTree; kraj;

Svaki čvor ima tip PTree. Ovo je pokazivač, što znači da svaki čvor mora biti kreiran pozivanjem New procedure na njemu. Ako je čvor lisnati čvor, tada se njegovim poljima LeftSubTree i RightSubTree dodjeljuje vrijednost nula. U suprotnom, čvorovi LeftSubTree i RightSubTree također se kreiraju postupkom New.

Jedan takav zapis shematski je prikazan na sl. 5.

Riža. 5. Shematski prikaz zapisa tipa TTree. Zapis ima tri polja: Inf – broj, LeftSubTree i RightSubTree – pokazivače na zapise istog tipa TTree.

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

Riža. 6. Stablo sastavljeno od zapisa tipa TTree. Svaki unos pohranjuje broj i dva pokazivača koji mogu sadržavati bilo koji nula, ili adrese drugih zapisa istog tipa.

Ako prethodno niste radili sa strukturama koje se sastoje od zapisa koji sadrže veze na zapise iste vrste, preporučujemo da se upoznate s materijalom o.

6. Primjeri rekurzivnih algoritama

6.1. Crtanje stabla

Razmotrimo algoritam za crtanje stabla prikazanog na sl. 6. Ako se svaka linija smatra čvorom, tada ova slika u potpunosti zadovoljava definiciju stabla danu u prethodnom odjeljku.

Riža. 6. Drvo.

Rekurzivna procedura bi očito nacrtala jednu liniju (deblo do prve grane), a zatim pozvala sebe da nacrta dva podstabla. Podstabla se od stabla koje ih sadrži razlikuju po koordinatama svoje početne točke, kutu zakreta, duljini debla i broju grana koje sadrže (jedna manje). Sve ove razlike treba učiniti parametrima rekurzivnog postupka.

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

Procedura Tree(Canvas: TCanvas; //Platno na kojem će stablo biti nacrtano x,y: prošireno; //Korijenske koordinate Kut: prošireno; //Kut pod kojim drvo raste TrunkLength: prošireno; //Duljina debla n: cijeli broj / /Broj grana (koliko još //rekurzivnih poziva ostaje)); var x2, y2: prošireno; //Kraj debla (točka grananja) početak x2:= x + Duljina debla * cos(Kut); y2:= y - Duljina trupa * sin(Kut); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); ako je n > 1 tada započnite stablo (platno, x2, y2, kut+pi/4, 0,55*duljina debla, n-1); Stablo (platno, x2, y2, kut-pi/4, 0,55*duljina debla, n-1); kraj; kraj;

Za dobivanje Sl. 6 ova procedura je pozvana sa sljedećim parametrima:

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

Imajte na umu da se crtanje provodi prije rekurzivnih poziva, to jest, stablo se crta izravnim redoslijedom.

6.2. Hanojski tornjevi

Prema legendi u Velikom hramu Banaras, ispod katedrale koja označava sredinu svijeta, nalazi se brončani disk na kojem su pričvršćene 3 dijamantne šipke, visine jedan lakat i debele poput pčele. Nekada davno, na samom početku vremena, monasi ovog samostana počinili su uvredu bogu Brahmi. Bijesan, Brahma je podigao tri visoke šipke i na jednu od njih stavio 64 diska od čistog zlata, tako da je svaki manji disk počivao na većem. Čim se svih 64 diska sa šipke na koju ih je postavio Bog Brahma pri stvaranju svijeta prebaci na drugu šipku, kula će se zajedno s hramom pretvoriti u prah, a svijet će propasti pod udarima groma.
Proces zahtijeva da veći disk nikada ne završi na vrhu manjeg. Redovnici su u dilemi: kojim redom raditi smjene? Potrebno im je osigurati softver za izračunavanje ovog niza.

Neovisno o Brahmi, ovu je zagonetku krajem 19. stoljeća predložio francuski matematičar Edouard Lucas. Prodana verzija obično je koristila 7-8 diskova (slika 7).

Riža. 7. Zagonetka “Towers of Hanoi”.

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

1) Pomak n-1 disk.
2) Pomak n disk na preostali slobodni pin.
3) Prebacujemo hrpu s n-1 disk primljen u točki (1) na vrhu n-ti disk.

Jer za slučaj n= 1 algoritam preuređivanja je očigledan, tada indukcijom, korištenjem akcija (1) – (3), možemo preurediti proizvoljan broj diskova.

Kreirajmo rekurzivnu proceduru koja ispisuje cijeli niz preuređivanja za zadani broj diskova. Svaki put kad se takva procedura pozove, mora ispisati informaciju o jednoj smjeni (iz točke 2 algoritma). Za preraspodjele iz točaka (1) i (3) procedura će se sama pozvati s brojem diskova smanjenim za jedan.

//n – broj diskova //a, b, c – brojevi pinova. Prebacivanje se vrši od pina a, //do zatika b s pomoćnim zatičem c. procedura Hanoi(n, a, b, c: cijeli broj); start if n > 1 then begin Hanoi(n-1, a, c, b); writeln(a, " -> ", b); Hanoi (n-1, c, b, a); end else writeln(a, " -> ", b); kraj;

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

6.3. Raščlanjivanje aritmetičkih izraza

Zadatak parsiranja je izračunati vrijednost izraza pomoću postojećeg niza koji sadrži aritmetički izraz i poznate vrijednosti varijabli uključenih u njega.

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

Riža. 8. Sintaksno stablo koje odgovara aritmetičkom izrazu (6).

U takvom stablu krajnji čvorovi uvijek će biti varijable (ovdje x) ili numeričke konstante, a svi unutarnji čvorovi sadržavat će aritmetičke operatore. Da biste izvršili operator, prvo morate procijeniti njegove operande. Dakle, stablo na slici treba prelaziti terminalnim redoslijedom. Odgovarajući niz čvorova

nazvao obrnuti poljski zapis aritmetički izraz.

Prilikom konstruiranja stabla sintakse treba obratiti pozornost na sljedeću značajku. Ako npr. postoji izraz

a mi ćemo čitati operacije zbrajanja i oduzimanja slijeva nadesno, tada će ispravno stablo sintakse sadržavati minus umjesto plusa (slika 9a). U biti ovo stablo odgovara izrazu.Moguće je olakšati kreiranje stabla ako izraz (8) analizirate obrnuto, s desna na lijevo. U ovom slučaju, rezultat je stablo sa sl. 9b, ekvivalentno stablu 8a, ali ne zahtijeva zamjenu znakova.

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

Riža. 9. Sintaksna stabla za izražavanje a – b + c kod čitanja slijeva na desno (a) i s desna na lijevo (b).

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

7.3. Određivanje čvora stabla po njegovom broju

Ideja ovog pristupa je zamijeniti rekurzivne pozive jednostavnom petljom koja će se izvršavati onoliko puta koliko ima čvorova u stablu formiranom rekurzivnim procedurama. Što će se točno raditi u svakom koraku treba odrediti brojem koraka. Usporedba broja koraka i potrebnih radnji nije trivijalan zadatak i u svakom slučaju morat će se riješiti zasebno.

Na primjer, recimo da želite učiniti k ugniježđene petlje n koraka u svakom:

Za i1:= 0 do n-1 učiniti za i2:= 0 do n-1 učiniti za i3:= 0 do n-1 učiniti …

Ako k unaprijed nepoznat, nemoguće ih je eksplicitno napisati, kao što je prikazano gore. Koristeći tehniku ​​prikazanu u odjeljku 6.5, možete dobiti potreban broj ugniježđenih petlji pomoću rekurzivne procedure:

Procedure 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 sve sveli na jedan ciklus, imajte na umu da ako numerirate korake u sustavu brojeva radix n, tada svaki korak ima broj koji se sastoji od brojeva i1, i2, i3, ... ili odgovarajućih vrijednosti iz polja indeksa. Odnosno, brojevi odgovaraju vrijednostima brojača ciklusa. Broj koraka u uobičajenom decimalnom zapisu:

Bit će ukupno koraka n k. Prolazeći kroz njihove brojeve u decimalnom brojevnom sustavu i pretvarajući svaki od njih u radix sustav n, dobivamo vrijednosti indeksa:

M:= okrugli(IntPower(n, k)); za i:= 0 do M-1 započnite Broj:= i; za p:= 0 do k-1 do begin Indeksi := Broj mod n; Broj:= Broj div n; kraj; Učini nešto (indeksi); kraj;

Napominjemo još jednom da metoda nije univerzalna i da ćete za svaki zadatak morati smisliti nešto drugo.

Kontrolna pitanja

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

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

Procedura Rec(a: integer); početi pisati(a); ako je a>0 onda Rec(a-1); napiši(a); kraj;

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

Funkcija Nod(a, b: cijeli broj): cijeli broj; start if a > b then Nod:= Nod(a – b, b) else if b > a then Nod:= Nod(a, b – a) else Nod:= a; kraj;

(c) Što će biti ispisano dolje navedenim postupcima kada se pozove A(1)?

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

(d) Što će donji postupak ispisati prilikom pozivanja BT(0, 1, 3)?

Procedura BT(x: real; D, MaxD: cijeli broj); start if D = MaxD then writeln(x) else begin BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); kraj; kraj;

2. Ouroboros - zmija koja proždire vlastiti rep (sl. 14) kada je rasklopljena ima dužinu L, promjer oko glave D, debljina trbušne stijenke d. Odredite koliko repa može stisnuti u sebe iu koliko će slojeva rep nakon toga biti položen?

Riža. 14. Prošireni ouroboros.

3. Za stablo na Sl. Slike 10a pokazuju redoslijed posjećivanja čvorova prema naprijed, unatrag i na kraju obilaska.

4. Grafički oslikajte stablo definirano pomoću ugniježđenih zagrada: (A(B(C, D), E), F, G).

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

Zapišite ovaj izraz u obrnutom poljskom zapisu.

6. Za donji grafikon (slika 15) zapišite matricu susjedstva i matricu incidencije.

Zadaci

1. Nakon što ste faktorijel izračunali dovoljno velik broj puta (milijun ili više), usporedite učinkovitost rekurzivnog i iterativnog algoritma. Koliko će se razlikovati vrijeme izvršenja i kako će taj omjer ovisiti o broju čiji se faktorijel računa?

2. Napišite rekurzivnu funkciju koja provjerava jesu li zagrade ispravno postavljene u nizu. Ako je raspored točan, ispunjeni su sljedeći uvjeti:

(a) broj otvarajućih i zatvarajućih zagrada je jednak.
(b) unutar bilo kojeg para postoji početna - odgovarajuća završna zagrada, zagrade su ispravno postavljene.

Primjeri netočnog postavljanja:)(, ())(, ())(() itd.

3. Redak može sadržavati okrugle i uglate zagrade. Svaka otvorna zagrada ima odgovarajuću zatvorenu zagradu iste vrste (okrugla - okrugla, četvrtasta - četvrtasta). Napišite rekurzivnu funkciju koja provjerava jesu li zagrade ispravno postavljene u ovom slučaju.

Primjer netočnog postavljanja: ([)].

4. Broj pravilnih struktura zagrada duljine 6 je 5: ()()(), (())(), ()(()), ((())), (()()).
Napišite rekurzivni program za generiranje svih regularnih struktura zagrada duljine 2 n.

Bilješka: Ispravna struktura zagrada minimalne duljine "()". Konstrukcije veće duljine dobivaju se od konstrukcija kraće duljine na dva načina:

(a) ako je manja struktura stavljena u zagradu,
(b) ako su dvije manje strukture napisane jedna za drugom.

5. Napravite proceduru 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. Napravite proceduru koja ispisuje sve moguće prikaze prirodnog broja N kao zbroj ostalih prirodnih brojeva.

8. Napravite funkciju koja izračunava zbroj elemenata niza pomoću sljedećeg algoritma: niz se dijeli na pola, zbrojevi elemenata u svakoj polovici se izračunavaju i zbrajaju. Zbroj elemenata u polovici niza izračunava se istim algoritmom, odnosno ponovno dijeljenjem na pola. Dijeljenja se događaju sve dok rezultirajući dijelovi niza ne sadrže po jedan element i izračunavanje zbroja, u skladu s tim, postaje trivijalno.

Komentar: Ovaj algoritam je alternativa. U slučaju nizova s ​​realnim vrijednostima, obično dopušta manje pogreške zaokruživanja.

10. Napravite proceduru koja crta Kochovu krivulju (slika 12).

11. Reproducirajte lik. 16. Na slici je u svakoj sljedećoj iteraciji krug 2,5 puta manji (ovaj koeficijent se može učiniti parametrom).

Književnost

1. D. Knuth. Umijeće računalnog programiranja. v. 1. (odjeljak 2.3. “Drveće”).
2. N. Wirth. Algoritmi i strukture podataka.

Funkcije: rekurzivno zadano funkcija u svojoj definiciji sadrži samu sebe; konkretno, funkcija definirana rekurentnom formulom je rekurzivna. Dakle, u jednom izrazu možete dati beskonačan skup načina za izračunavanje funkcije, definirati mnoge objekte kroz sebe koristeći prethodno navedene privatne definicije.

Podaci

Struct element_of_list ( element_of_list * sljedeći; /* referenca na sljedeći element istog tipa */ int podataka; /* neki podaci */ );

Rekurzivna struktura podataka često diktira korištenje rekurzije za obradu podataka.

U fizici

Klasičan primjer beskonačne rekurzije su dva zrcala postavljena jedno nasuprot drugoga: tvore dva koridora opadajućih refleksija zrcala.

Drugi primjer beskonačne rekurzije je učinak samopobude (pozitivna povratna sprega) u elektroničkim krugovima za pojačanje, kada signal s izlaza ide na ulaz, pojačava se, vraća se na ulaz kruga i ponovno se pojačava. Pojačala kod kojih je ovaj način rada standardan nazivamo autooscilatorima.

U lingvistici

Sposobnost jezika da generira ugniježđene rečenice i konstrukcije. Osnovna ponuda" mačka pojela miša»može se proširiti rekurzijom kao Vanja je pogodio da je mačka pojela miša, zatim kao Katja zna da je Vanja pogodio da je mačka pojela miša i tako dalje. Rekurzija se smatra jednom od lingvističkih univerzalija, odnosno karakteristična je za svaki prirodni jezik. Međutim, nedavno se aktivno raspravljalo o mogućem nedostatku rekurzije u jednom od jezika Amazone - Pirahã, što je primijetio lingvist Daniel Everett ( Engleski) .

U kulturi

Većina šala o rekurziji odnosi se na beskonačnu rekurziju, u kojoj nema izlaznog uvjeta, na primjer, poznata izreka: "da biste razumjeli rekurziju, prvo morate razumjeti rekurziju."

Vrlo popularan vic o rekurziji, koji podsjeća na rječničku natuknicu:

Nekoliko priča Stanislawa Lema posvećeno je (mogućim) incidentima s beskonačnom rekurzijom:

• priča o Ionu Tihom “Četrnaesto putovanje” iz “Zvjezdanih dnevnika Ijona Tihog”, u kojoj se junak sekvencijalno kreće od članka o sepulkiju do članka o sepulaciji, odatle do članka o sepulkariji, koji opet sadrži referenca na članak “sepulki”:

Našao sam sljedeće kratke podatke:
“SEPULKI su važan element Ardritske civilizacije (q.v.) s planeta Enteropia (q.v.). Vidi SEPULCARIA."
Poslušao sam ovaj savjet i pročitao:
“SEPULCARIA - uređaji za sepulaciju (vidi).”
Tražio sam "Sepulenia"; glasilo je:
“SEPULACIJA je okupacija Ardrita (q.v.) s planeta Enteropia (q.v.). Vidi SEPULS.”

Lem S. “Zvjezdani dnevnici Iyona Tihog. Putovanje četrnaesto."

• Priča iz “Cyberiade” o inteligentnom stroju koji je imao dovoljno pameti i lijenosti izgraditi sličan za rješavanje zadanog problema, te mu povjeriti rješenje (rezultat je bila beskonačna rekurzija, kada je svaki novi stroj izgradio sličan i delegirao zadatak na njega).
• Rekurzivni akronimi: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), itd.

vidi također

• Povratni niz

Bilješke

Zaklada Wikimedia. 2010.

• Video memorija
• Elektromagnetska radijacija

Pogledajte što je "rekurzija" u drugim rječnicima:

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

rekurzija- - [] rekurzija U općem smislu, izračun funkcije pomoću specifičnog algoritma. Primjeri takvih algoritama su rekurentne formule koje izvode izračun zadanog člana... ... Vodič za tehničke prevoditelje

Rekurzija- u općem smislu, izračun funkcije pomoću specifičnog algoritma. Primjeri takvih algoritama su rekurentne formule, koje izvode izračun zadanog člana niza (najčešće numeričkog) iz izračuna nekoliko prethodnih ... Ekonomski i matematički rječnik

Rekurzija- Terapijski obrazac u kojem se neki uvjet ili kriterij formuliran u izvornoj izjavi uzima i primjenjuje na samu izjavu. Na primjer: Nemam vremena. Koliko ste vremena morali potrošiti da biste bili sigurni da ste... ... Velika psihološka enciklopedija

REKURZIJA- metoda određivanja funkcija, koja je predmet proučavanja u teoriji algoritama i drugim granama matematike. logika. Ova se metoda dugo koristi u aritmetici za određivanje numeričkih nizova (progresija, Fibonacci brojevi, itd.).... ... Matematička enciklopedija

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

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.