Post on 07-Feb-2016
MINISTERUL EDUCAŢIEI, CERCETĂRII ŞI TINERETULUI ŞI SPORTULULUI
COLEGIUL TEHNIC MĂTĂSARI
PROF. COORDONATOR: SĂCEANU ION
ELEV: Voica Cornelia
AlexandraClasa a XII-a B
Profil: Matematică-informaticăColegiul Tehnic Mătăsari
ATESTAT
PROFESION
AL
-2015-
MINISTERUL EDUCAŢIEI, CERCETĂRII ŞI TINERETULUI ŞI SPORTULULUI
COLEGIUL TEHNIC MĂTĂSARI
PROF. COORDONATOR: SĂCEANU ION
ELEV: Voica Cornelia
Alexandra CLASA a XII-a B
Profil: Matematică-informaticăColegiul Tehnic Mătăsari
CUPRINS:
RECURSIVITATE
-2015-
1. Aspecte teoretice…………………………1
2. Proceduri recursive………………………7
3. Funcţii recursive ……………………….14
4. Backtracking recursiv.…………………..20
5. Funcţii Forward. Referinţe forward……..22
6. Probleme recursive……………………...25
7. Figuri recursive………………………...44
8. Bibliografie……………………………50
Recursivitate
1.Aspecte teoretice
1.1 Ce este recursivitatea?
Recursivitatea, folosită cu multă eficienţă în matematică, s-a impus în programare, odata cu apariţia unor limbaje de nivel inalt, ce permit scrierea de module ce se autoapelează (PASCAL,LISP,ADA,ALGOL,C sunt limbaje recursive, spre deosebire de FORTRAN,BASIC,COBOL, nerecursive).
Recursivitatea e strâns legată de iteratie, dar dacă iteratia e execuţia repetată a unei porţiuni de program, până la îndeplinirea unei conditii (while, repeat, for din PASCAL), recursivitatea presupune executia repetata a unui modul, insa în cursul executiei lui (şi nu la sfârsit, ca în cazul iteratiei), se verifica o conditie a cărei nesatisfacere, implica reluarea executiei modulului de la inceputul sau. Atunci un program recursiv poate fi exprimat: P=M(Şi,P) , unde M este multimea ce contine instructiunile Şi şi pe P insusi.
Structurile de program necesare şi suficiente în exprimarea recursivităţii sunt procedurile şi subrutinele ce pot fi apelate prin nume.
Recursivitatea poate fi:
-directă - un modul P contine o referinţă la el insuşi
-indirectă - un modul P contine o referinţă la un modul Q ce include o referinţă la P.
1.2 Parametrii-valoare şi parametrii-variabilă
Discuţia se face pentru cazul implementării recursivităţii în PASCAL, dar lucrurile sunt similare pentru C.
În PASCAL, există două tipuri de parametri formali (ce apar în antetul unei proceduri sau funcţii) : valoare şi variabilă (ultimii au numele precedat de cuvântul cheie var).
Apelul recursiv al unei proceduri (funcţii) face ca pentru toţi parametrii-valoare să se creeze copii locale apelului curent (în stivă) , acestea fiind referite şi asupra lor făcându-se modificările în timpul execuţiei curente a procedurii (funcţiei). Când execuţia procedurii (funcţiei) se termină, copiile sunt extrase din stivă, astfel încât modificările operate asupra parametrilor-valoare nu afectează parametrii efectivi de apel, corespunzători.
De asemenea pentru toate variabilele locale se rezerva spaţiu la fiecare apel recursiv. În cazul parametrilor-variabila, nu se crează copii locale, ci operarea se face direct asupra spaţiului de memorie afectat parametrilor efectivi, de apel.
De reţinut:-pentru fiecare apel recursiv al unei proceduri (funcţii) se crează copii locale ale parametrilor valoare şi variabilelor locale, ceea ce poate duce la risipă de memorie;-orice parametru-variabila poate fi suprimat prin referirea directă în procedura (funcţie) a variabilei ce figura ca parametru de apel
1.3 Verificarea şi simularea programelor recursive
Se face în cazul celor nerecursive, printr-o demonstraţie formală, sau testând toate cazurile posibile. Se verifică întâi dacă toate cazurile particulare (ce se execută când se îndeplineşte condiţia de terminare a apelului recursiv) funcţionează corect.
Se face apoi o verificare formală a procedurii (funcţiei) recursive, pentru restul cazurilor, presupunând că toate componentele din codul procedurii (funcţiei) funcţionează corect. Verificarea e deci inductivă.Acesta e un avantaj al programelor recursive, ce permite demonstrarea corectitudinii lor simplu şi clar.
Exemplificare: Funcţia recursivă de calcul a factorialului:
function fact(n:integer):integer; begin if n=1 then fact:=1
else fact:=n*fact(n-1) end;
Demonstrarea corectitudinii cuprinde doi paşi:-pentru n=1 valoarea 1 ce se atribuie factorialului este corectă-pentru n>1, presupunând corectă valoarea calculată pentru predecesorul lui n de fact(n-1), prin înmulţirea acesteia cu n se obţine valoarea corectă a factorialului lui n.
1.4 Tehnica eliminării recursivităţii
Orice program recursiv poate fi transformat în unul iterativ, dar algoritmul sau poate deveni mai complicat şi mai greu de înţeles. De multe ori, soluţia unei probleme poate fi elaborată mult mai uşor, mai clar şi mai simplu de verificat, printr-un algoritm recursiv.
Dar pentru implementare, poate fi necesară transformarea algoritmului recursiv în unul nerecursiv, în situaţiile:-solutia problemei trebuie scrisă într-un limbaj nerecursiv; un caz particularsuntcompilatoarele ce "traduc" un program recursiv dintr-un limbaj de nivel înalt în cod maşină (nerecursiv)-varianta recursivă ar duce la o viteză de execuţie şi spaţiu de memorie prea mari, transformarea în una nerecursivă, eliminând dezavantajele.
Se va prezenta una din metodele de eliminare a recursivităţii ce foloseşte o structură de date de tip stivă. În scrierea unei varianta nerecursive, trebuie parcurşi toţi paşii implicaţi în varianta recursivă, prin tehnici nerecursive.
Recursivitatea implica folosirea a cel puţin unei stive. La fiecare apel recursiv sunt depuse în stivă nişte date, care sunt extrase la revenirea din acel apel. E simplu dacă datele pentru un apel se organizează într-un record, un apel însemnând introducerea în stivă a unui record, revenirea, extragerea lui.
Se prezintă eliminarea recursivităţii pentru un program simplu, care citeşte caracterele tastate pe o linie, tipărindu-le apoi în ordine inversă.
program var_recursivă; procedure prel_car; var car:char; begin
read(car); if not eoln then prel_car; write(car)
end; begin prel_car end.
program var_nerecursivă; begin *iniţializează stivă while not eoln do
begin read(car); push(car)
end; while not stiva_goală do
begin pop(car); write(car)
end end.
1.5 Exemple de algoritmi recursivi
1.5.1 Algoritmi de traversare şi inversare a unei structuri
Traversarea şi inversarea unei structuri înseamnă efectuarea unor operaţii oarecare asupra tuturor elementelor unei structuri în ordine directă, respectiv în ordine inversă.
Deşi mai uzuale sunt variantele iterative, caz în care inversarea echivalează cu două traversări directe (o salvare în stiva urmată de parcurgerea stivei), variantele recursivesuntmai elegante şi concise. Se pot aplica structurilor de tip tablou, lista, fişier şi pot fi o soluţie pentru diverse probleme (transformarea unui întreg dintr-o bază în alta, etc).
Într-o formă generală, algoritmii se pot scrie:
procedure traversare(element:tip_element); {apelul iniţial} {al procedurii se face cu primul element al structurii} begin prelucrare(element); if element <> ultimul_din_structura then
traversare(element_următor) end;
procedure inversare(element:tip_element); {apelul iniţial} {al procedurii se face cu primul element al structurii} begin if element <> ultimul_din_structura then
traversare(element_următor); prelucrare(element) end;
De observat importantă ca parametrul formal al celor două proceduri să fie de tip valoare, pentru a nu fi alterat de apelul recursiv.
1.5.2 Algoritmi care implementează definiţii recursive
O definiţie recursivă e cea în care un obiect se defineşte prin el însuşi. Definiţia conţine o condiţie de terminare, indicând modul de părăsire a definiţiei şi o parte ce precizează definirea recursivă propriu-zisă.
Ca exemple: algoritmul lui Euclid de aflare a c.m.m.d.c., factorialul, ridicarea la o putere întreagă (prin înmulţiri repetate), definirea recursivă a unei expreşii aritmetice, curbele recursive, un mod de a privi permutările, etc.
2. Proceduri recursiveProcedurile de asemenea pot fi recursive. Ca un exemplu considerăm
algoritmul pentru transformarea întregilor zecimali în numere binare. Astfel, lui (13)10 îi corespunde (1101)2
Presupunem ca dorim să scriem o procedura care tipareste astfel de rezultate pentru orice n pozitiv, mai mare ca maxint.
Alegem o procedura şi nu o functie deoarece noi cautam mai mult decât un raspuns - mai multe cifre binare: 1, 1, 0, 1 în exemplul ales.
O problema care intervine în scrierea acestei proceduri este aceea ca entitatile (1, 1, 0, 1) trebuie tiparite în sens invers (prima valoare obtinuta trebuie tiparita ultima).
O primă solutie ar fi aceea de a utiliza o imprimanta care poate tipari de la dreapta la stânga, dar este putin probabil ca veti gasi! Alta solutie ar fi să scriem o rutina complicata care într-un fel supraimprima aceeasi linie a output-ului fara a permite orice interventie înapoi, dar aceasta solutie nu este nici eleganta, nici eficienta!
Am putea salva aceste cifre într-un masiv (ARRAY) dar scopul nostru, pentru acest exemplu este acela de a arata ca putem folosi recursivitatea.
Asadar, să... navigam! Priviti din nou la 13 scris în binar: 1101. Observati ca primele 3 cifre, 110, sunt evaluate la 6. Adaugam un 0 în dreapta oricarui numar binar, valoarea să se dubleaza, astfel încât 1100 este 12.
În aceeasi idee, 13=(6x2)+1. În mod corespunzator, un numar par, cum ar fi 20 poate fi exprimat ca (10x2)+0.
Observatie!
Cifra după semnul plus va fi 0 pentru numere pare şi 1 pentru numere impare. Ea poate fi uşor obtinută, pentru orice n folosind relaţia: n MOD 2.
Acum priviti la primul cât obtinut în împartirea succesiva folosita pentru transformarea lui 13 din zecimal --> binar. Este 6, nu? Asadar, acum avem baza unui algoritm:
IF n<2 THEN
reprezentarea binara a lui n este n {conditia bootstrap}
ELSE {se aplica pasul inductiv}
{reprezentarea binara a lui n este reprezentarea binara a lui n div 2 adaugând n mod 2}
Să testam acest algoritm numai pentru câteva cazuri simple. Conditia bootstrap este aceea ca reprezentarea binara a lui 0 este 0 şi reprezentarea binara a lui 1 este 1. Deocamdata este bine. Pentru a obtine reprezentarea binara a lui 2, avem nevoie să aplicam pasul inductiv o data.
Astfel (2)10 --> (10)2. Pentru 5, pasul inductiv va fi aplicat de doua ori, folosind rezultatul anterior (pentru 2). Astfel (5)10 --> (101)2.
Reprezentarea binara a lui 2= reprezentarea binara a lui 2 div 2 adaugând 2 mod 2
(2)10=(10)2
Reprezentarea binara a lui 5= reprezentarea binara a lui 5 div 2 adaugând 5 mod 2
(5)10=(101)2
Implementarea (Borland) PASCAL a acestui algoritm recursiv este programul binar.
PROGRAM binar; {Afiseaza echivalentul binar al întregilor zecimali} VAR n:integer; PROCEDURE binary(n:integer); {Conversie recursiva a lui n zecimal în forma binara} BEGIN IF n<2 THEN write(n:2) ELSE {aplica pasul inductiv:} BEGIN binary (n div 2);write(n mod 2) END; END {binary}; BEGIN {principal} WHILE NOT eof DO BEGIN write('Intoduceti un numar zecimal întreg pozitiv’);
readln(n); write('zecimal ',n:2, ' binar '); binary(n); writeln END; END {binar}.
Tiparirea cifrelor a fost... amânata în exemplul precedent. Aceasta tehnica are numeroase aplicatii. În programul tipar (exemplul urmator), procedura recursiva flipcon pregateste pentru editare o secventa de caractere (care intra) pâna când conditia eof este detectata şi apoi, şi numai apoi, tipareste caracterele citite în ordine inversa.
PROGRAM tipar; {Citeste propozitiile până la eof dupa care tipareste propozitia în sens invers} PROCEDURE flipcar; {Inverseaza recursiv caracterele până la eoln} VAR ch:char; BEGIN read(ch); IF eoln THEN write(ch) ELSE BEGIN {pasul inductiv} flipcar; write(ch) END END {flipcar}; BEGIN {principal} WHILE NOT eof DO BEGIN writeln('Introduceti o propozitie pe o singura linie de input'); flipcar; writeln END END {tipar}.
Rezultatele execuţiei programului:
Input
AFARA PLOUA LINISTITUNIVERSITATEA DE VEST ESTE ÎN TIMISOARAAM FOST ÎN BUCURESTI
Output
TITSINIL AUOLP ARAFAARAOSIMIT NI ETSE TSEV ED AETATISREVINUITSERUCUB NI TSOF MA
Problema: Turnurile din Hanoi.
Presupunem că avem cinci discuri (turnuri), găurite în centru, ca în exemplul următor (numărul de ace este trei întotdeauna, dar numărul de discuri poate varia). Ce se doreşte? Să mutăm discurile (turnurile) unul câte unul, de la acul 1 la acul 3, folosind acul 2 ca... gazdă temporară, în condiţiile în care la fiecare mutare se deplasează un singur disc, şi în nici o etapă nu este admis că un disc mai mare să stea pe un disc mai mic. Răspunsul dorit este o listă de mutări, de genul: "Muta un disc de la acul 1 la acul 3".
Configuraţia pentru cinci discuri (turnurile din Hanoi):
Desigur, vă veţi întreba unde intervine recursivitatea? Analizând problema observăm că pentru cele 5 discuri, am fi capabili să mutăm ultimul disc numai dacă, într-un mod oarecare am putea manevra cele patru discuri de deasupra, pe acul al doilea, lăsând acul al treilea liber pentru a primi discul rămas (cel mai mare) de la primul ac. Altă problemă, de aceeaşi dimensiune, este mutarea celor patru discuri la acul trei (după mutarea discului mai mare, conform descrierii anterioare). Noi generalizam problema, realizând o procedură move (n, a, b, c) care, într-un fel, ştie cum să mute n discuri, de la
acul a la acul b prin intermediul acului c şi care listează toate mutările necesare pentru... atingerea obiectivului. Dacă procedura move lucrează corect, soluţia la problema cu cinci discuri este cea ilustrata în continuare.
MOVE(4,1,3,2); {Mută 4 discuri de la acul 1 la 3 prin intermediul acului 2} Writeln('Muta un disc de la acul 1 la acul 3'); MOVE(4,3,2,1); {Mută 4 discuri de la acul 3 la acul 2 prin intermediul acului 1 pentru a completa soluţia problemei cu 5 discuri}
Cum procedăm să realizăm primul şi al treilea pas? Recursivitatea directă: problema cu cinci discuri poate fi rezolvată dacă soluţionam problema cu patru discuri şi aşa mai departe, până la problema care nu implică nici un disc. Problema cu nici un disc este uşor de rezolvat şi furnizează bootstrap-ul: pentru n=0, nu se face nimic!
Funcţia cheie move (vezi programul de mai jos) este folosită în cadrul unui program care permite utilizatorului să introducă numărul de discuri ce trebuie mutate. Testaţi funcţia pentru valori mici, cum ar fi n=7 dar, atenţie la valori mari, deoarece ele tind să consume foarte mult timp!
PROGRAM turnuri; TYPE Inputdisk=integer; Inputac=1..3; VAR Inputndisk:integer; PROCEDURE MOVE(n:disk;a,b,c:ac); {Mută n disk-uri de la acul a la acul b,via c} BEGIN InputIF n>0 THEN {se aplică pasul inductiv} InputBEGIN InputInputMOVE(n-1, a,c,b); InputInputwriteln('Muta un disc de la',a:2,'la',b:2); InputInputMOVE(n-1,c,b,a)
InputEND END {MOVE}; BEGIN {principal} InputWHILE NOT eof DO InputBEGIN InputInputwrite('Introduceti numarul de discuri ce trebuie mutate:') InputInputreadln(ndisk);
InputInputwriteln; InputInputMOVE(ndisk,1,3,2); InputInputwriteln InputEND END {turnuri}.
Remarcă! În descrierea originala a problemei turnurilor din Hanoi se
spune ca un grup de calugari au fost... provocati să mute 64 de discuri de aur utilizând o platforma de alama cu trei ace de diamant. Legendele sustin ca preotii joaca acest joc în mod curent şi ca sfârsitul jocului va însemna sfârsitul lumii!
3. Funcţii recursiveUna din cele mai simple funcţii matematice este, fără îndoiala funcţia
factorial.
Din moment ce (Borland) PASCAL-ul nu are o funcţie (de bibliotecă) standard pentru calculul factorialului, va trebui să scriem noi una. Definirea lui n! (se citeşte "n factorial") este produsul: n x (n-1) x (n-2) x...x 3 x 2 x 1 (pentru un întreg mai mare ca 0; 0!=1).
Aceasta definiţie poate fi implementata în (Borland) PASCAL prin funcţia descrisă în continuare:
Exemplu: FUNCTION fact(n:integer):integer; VAR i,t:integer; BEGIN
Introduceti numarul de discuri ce trebuie mutate:3Muta un disc de la 1 la 3Muta un disc de la 1 la 2Muta un disc de la 3 la 2Muta un disc de la 1 la 3Muta un disc de la 2 la 1Muta un disc de la 2 la 3Muta un disc de la 1 la 3
t:=1; FOR i:=n downto 2 DO t:=t*i; fact:=t END {fact};
Când vrem să subliniem că o funcţie nu este recursivă (dar ar fi putut fi !) noi o numim funcţie iterativă. Remarcaţi că enunţul iterativ folosit (o buclă FOR) nu este executat niciodată pentru n mai mic ca 2 - funcţia returnează valoarea 1 atât pentru 1! cât şi pentru 0!. Variabilă de control al buclei (i) ia valori până la 2, nu până la 1 pentru a evita o înmulţire inutilă cu 1 în final. Variabilă (de stare) t este necesară pentru a evita folosirea lui fact (numele funcţiei) în partea dreaptă a enunţului de atribuire t:=t*i. Compilatorul (Borland) PASCAL se aşteaptă ca un nume de funcţie să apară numai în partea dreaptă a enunţului de atribuire, acela care leagă numele funcţiei de o valoare particulară. Iată în exemplul următor o alternativă de definire a lui n! care este mai degrabă recursiva decât iterativa.
IF n=0 THEN fact:=1 ELSE fact:=n*fact(n-1)
Clauza IF este extrem de importantă, din moment ce fără ea secvenţa va... curge, indefinit:
.3!= 3x2!
...= 3x2x1!
...= 3x2x1x0!
...= 3x2x1x0x(-1)!
...= 3x2x1x0x(-1)!x(-2)!
......
Testul care previne o asemenea recursivitate nedefinită se numeşte bootstrap condition şi reprezintă un element esenţial al oricărei rutine recursive. Aici, bootstrap condition este <IF n=0 THEN fact:=1> care opreşte calculul lui n! de la o rulare nedefinită. Iată funcţia recursivă (Borland) PASCAL pentru calculul lui n!
FUNCTION fact(n:integer):integer; {funcţia recursivă pentru calculul lui n!} BEGIN IF n=0 THEN fact:=1 ELSE fact:=n*fact(n-1) END {fact};
Cele două apariţii ale lui fact în partea stânga a enunţurilor de atribuire respecta regulă prin care unei funcţii i se atribuie o valoare particulară. Ceea ce face ca fact să fie o funcţie recursivă este prezenţa lui fact (n-1) în membrul
drept al enunţului fact:=n*fact (n-1). Asocierea lui fact cu argumentul n-1, presupune că atunci când implicăm funcţia fact, ea se va apela pe ea însăşi.
Aşa cum a trebuit să învăţăm cum să scriem bucle care se termină după un număr finit de iteraţii, trebuie să învăţăm să construim funcţii recursive care se termină cu succes după o serie finită de referiri la sine.
Învăţarea modului de folosire a recursivităţii este mai importantă decât înţelegerea modului cum lucrează. Prezentăm două reguli simple, dar esenţiale.
Reguli:
1) Orice funcţie sau procedura recursivă trebuie să aibă cel puţin o bootstrap condition, care specifică răspunsul corect sau acţiunea pentru cea mai simplă situaţie imaginabilă, în general una corespunzătoare celei mai mici valori parametru (cea de final);
2) Orice funcţie sau procedura recursivă trebuie să aibă un pas inductiv (inductive step) care leagă problemă ce trebuie rezolvată de cea mai simplă versiune.
Pentru funcţia factorial (fact recursivă), bootstrap condition este 0!=1, iar inductive step (pasul inductiv) leagă pe n! de (n-1)! care rămâne închis la bootstrap.
La prima vedere, funcţia factorial - fact recursiva pare să aibă nevoie de mai puţină memorie decât omoloaga să nerecursiva deoarece este folosită variabilă nontemporara (stare) t, dar aceasta este o iluzie. În spatele ... scenei, o rutină recursivă trebuie să salveze una sau mai multe valori intermediare ori de câte ori ea se apelează pe ea însăşi. Ea salvează aceste valori în formă de stack, o structură de date în care ultimul item salvat este primul ce poate fi rechemat.
Remarcă!
Alte nume pentru stack sunt pushdown stack şi lifo list (lifo este prescurtarea de la "last în, first ouţ").
Altă posibilă operaţie recursivă este an - a ridicat la puterea n (unde n >= 0).
Ceea ce urmează este o soluţie nerecursiva, bazată pe multiplicarea lui a cu el însuşi de n ori.
FUNCTION putere (a:real; n:integer):real; {O funcţie iterativă pentru calculul lui a la puterea n} VAR t:real; i:integer; BEGIN t:=1;
FOR i:=1 TO n DO t:=t*a; putere:=t END {putere};
Pentru n=0, bucla FOR nu se va executa, generând a0=1, valoare evident corectă. Pentru n>=1, t devine în ordine a, a2, a3 şi tot aşa până la an.
Definirea recursivă a lui an este:
IF n=0 THEN an:=1; unde an =a*an-1
Condiţia bootstrap este a0=1. Pasul inductiv (inductive step) an=a*an-1, leagă problemă generală an de problema an-1, care rămâne pe loc la bootstrap.
Traducerea (Borland) PASCAL a acestei definiţii este ilustrata în secvenţa următoare:
FUNCTION putere (a:real; n:integer):real; BEGIN IF n=0 THEN putere:=1 ELSE putere:=a*putere(a,n-1) END {putere};
Există ceva dezorganizat în ambele versiuni ale lui putere. Aţi calculat a16, făcând 15 înmulţiri ? Probabil că nu; aţi observat că a16 =(a8)2 şi că a8
=(a4)2 şi tot aşa mai departe. Astfel, în realitate avem nevoie de 4 înmulţiri pentru a calcula a16. Evident, aceasta înjumătăţire maximă nu va lucra la fel, dacă n este impar. În consecinţă, un algoritm recursiv îmbunătăţit trebuie să fie structurat astfel:
IF n=0 THEN an=1 ELSE IF n îs odd THEN an=a*an-1 ELSE an=(an/2)2
Aceasta definire are doi paşi inductivi, unul folosit pentru n impar, celălalt utilizat pentru n par. Aşa cum s-a cerut, ambii pasi inductivi leagă problemă de o dimensiune dată, de una care rămâne închisa la bootstrap. Programul (Borland) PASCAL ce codifică acest algoritm îmbunătăţit este prezentat în continuare:
Exemplu: FUNCTION putere (a:real;n:integer):real; BEGIN IF n=0 THEN putere:=1 ELSE IF odd(n) THEN putere:=a*putere(a,n-1) ELSE {chiar pentru n} putere:=sqr(putere(a,n div 2)) END {putere};
Pentru valori mari ale lui n, această versiune a lui putere foloseşte mai degrabă un număr de înmulţiri egal cu log2n decât cu n-1, ca în versiunea
precedenta. Pentru n=64, unde log264=6, aceasta reprezintă o economie înzecita.
Observaţie!
Remarcaţi că întrucât exista o mică diferenţă între numărul de enunţuri (Borland) PASCAL folosite pentru versiunile recursiva, respectiv iterativa ale lui fact sau pentru primele două versiuni (ineficiente) ale lui putere, este pe undeva prea dificil să recodificam versiunea eficientă a lui putere fără a folosi recursivitatea.
Implementarea recursivă a unui algoritm este adesea mult mai naturală şi mult mai lizibila decât implementarea iterativă echivalentă.
Unul dintre cei mai cunoscuţi algoritmi este algoritmul lui Euclid, care calculează cel mai mare divizor comun (gcd) a doi întregi pozitivi, nenuli m şi n. De exemplu, dacă m este 45 şi n este 30, c.m.m.d.c. al lor este 15; dacă m este 8 şi n este 12, atunci c.m.m.d.c. este 4.
Pentru a calcula c.m.m.d.c. reamintim algoritmul lui Euclid. Dacă m=n, atunci c.m.m.d.c. este m (sau n); în caz contrar, se înlocuieşte numărul mai mare cu diferenţa celor două numere şi procesul se repetă.
Funcţia iterativă (Borland) PASCAL care corespunde acestei definiţii este ilustrată de:
FUNCTION gcd1(m,n:integer):integer; BEGIN WHILE m<>n DO IF m>n THEN m:=m-n ELSE n:=n-m; gcd1:=m END {gcd1};
Versiunea recursivă, cu aceeaşi logică, este prezentată în continuare:
FUNCTION gcd2(m,n:integer):integer; BEGIN IF m=n THEN gcd2:=m ELSE IF m>n THEN gcd2:=gcd2(m-n,n) ELSE gcd2:=gcd2(m,n-m) END {gcd2};
Remarcă!
Cele două versiuni sunt foarte ineficiente când diferenţa dintre m şi n este mare , deoarece determina un număr considerabil de scăderi succesive până când numerele sunt aduse în acord. Dar o asemenea scădere repetată se
constituie într-un paravan; un algoritm recursiv mult mai bun poate fi codificat folosind operatorul mod.
FUNCTION gcd(m,n:integer):integer; {Returnează c.m.m.d.c. al lui m şi n>0} VAR r:integer; BEGIN r:=m mod n; IF r=0 THEN gcd:=n ELSE gcd:=gcd(n,r){Din moment ce n este divizibil prin n,al doilea argument mai vechi este acum primul} END {gcd};
4. Backtracking recursivÎn acest capitol prezentăm rutină de backtracking recursivă. Procedurile şi
funcţiile folosite sunt în general aceleaşi ca la backtracking, cu două mici excepţii:
-SUCCESOR nu mai este procedura ci funcţie booleana ;-rutina backtracking se transformă în procedura,care se
apelează prin BACK(1)Principiul de funcţionare al procedurii BACK,corespunzător unui nivel k
este următorul:-in situaţia în care avem o soluţie,o tipărim şi revenim pe nivelul anterior-in caz contrar se iniţializează nivelul şi se cauta un succesor-cand am găsit unul verificăm dacă este valid;procedura se autoapeleaza
pentru (k+1) , în caz contrar urmând a se continua căutarea succesorului;-daca nu avem succesor,se trece pe nivel inferior (k-1) prin ieşirea din
procedură BACK
Vom explica în continuare utilizarea backtrackingului recursiv prin generarea permutărilor:
type stivă=array[1..9] of integer;var st:stivă; ev:boolean;n,k:integer;procedure init(k:integer;var st:stivă);beginst[k]:=0;end;function succesor(var st:stivă;k:integer):boolean;
beginif st[k]<n thenbeginst[k]:=st[k]+1;succesor:=true;endelse succesor:=false;end;procedure valid(var ev:boolean;st:stivă;k:integer);var i:integer;beginev:=true;for i:=1 to k-1 do if st[i]=st[k] then ev:=false;end;function soluţie(k:integer):boolean;beginsoluţie:=(k=n+1);end;procedure tipar;var i:integer;beginfor i:=1 to n do writeln(st[i]);writeln;end; procedure back(k:integer);beginif soluţie (k) then tiparelse begininit(k,st);while succesor(st,k) do beginvalid(ev,st,k);if ev then back(k+1);end; end;end;beginwrite('n=');readln(n);back(1);end.
Desigur orice problemă care admite rezolvare backtracking,poate fi rezolvată în acest mod.Însă,de multe ori, aceeaşi problemă se poate rezolva scriind mai puţin, dacă renunţăm la standardizare.
5. Funcţii Forward. Referinţe forward
O funcţie sau o procedură nu poate fi recursiva numai intrinsec, ea poate deveni de asemenea recursiva indirect prin interacţiunea cu alte proceduri sau funcţii care nu au fost încă declarate. De exemplu, p1 şi p2 pot forma o pereche recursivă mutuală (mutually recursive pair, în limba engleză) dacă p1 cheamă pe p2 şi p2 cheamă pe p1, sau mai multe rutine pot crea o recursivitate indirectă printr-un lanţ circular de apelări cum ar fi p1-> p2-> p3-> ...-> pn-> p1.
Considerăm următorul exemplu de recursivitate mutuală. Să presupunem că nu exista funcţiile (Borland) PASCAL de biblioteca sân şi coş şi că dorim să implementăm o pereche care să se cheme sine şi cosine. Considerăm identităţile trigonometrice cunoscute.
sân(x)=2 sin(x/2)cos(x/2) cos(x)=cos2(x/2)-sin2(x/2)
Pentru că ambele identităţi să constituie baza rutinelor sine şi cosine trebuie să observăm următoarele:
· atât sine cât şi cosine se apelează pe el însele, deci sunt recursive;
· fiecare funcţie apelează pe cealaltă, astfel ele formează o pereche mutuală recursivă;
· condiţiile bootstrap sunt necesare pentru a duce la bun sfârşit programul;
· indiferent de ordinea de scriere a rutinelor, compilatorul (Borland) PASCAL va obiectă, în mod normal la întâlnirea unei referiri la o funcţie al cărei cod se afla mai departe (în continuare).
Primele două puncte sunt numai observaţii. Ultimele două sunt probleme ce trebuie rezolvate.
Pentru început, să abordăm problema condiţiilor bootstrap. Întrucât sin(x) şi cos(x) folosesc ca argumente unghiul pe jumătate care în interiorul... cuibului recursiv devin din ce în ce mai mici, am putea avea propriile noastre bootstrap-uri.
Pentru valori mici ale lui x este aproape adevărat că sin x şi cos x au valorile definite de primii doi termeni: (x-x3/6), respectiv 1-x2/2 dintr-o serie infinită.
sinx @ x-x3/6 cosx @ 1-x2/2
Ne întrebam: cât de mic trebuie să fie x pentru a ne permite nouă să ne bazăm pe aceste aproximaţii. Aceasta depinde de cât de multe zecimale ne vom aştepta la răspunsurile date. Un matematician ne-ar răspunde că pentru x < 0.02 aproximarea lui cos x poate fi făcută cu 8 zecimale, iar pentru sinx este chiar mai bună.
În rutinele pe care le vom prezenta, valorile mai mici decât 0.02 şi 0.01 servesc ca bootstrap-uri şi sunt numite epsilon. În fiecare rutină epsilon este declarat că o constantă astfel încât valoarea să poate fi uşor modificată, în funcţie de experiment .
Impedimentul final îl constituie situaţia "chicken-and-egg" (gaina-şi-oul) referitoare la ordinea relativă a lui sine şi cosine din interiorul codului sursa. Din fericire, un pas de compilare în (Borland) PASCAL cere ca numai o procedură sau o funcţie să poată fi alimentate cu elementele pentru header-ul rutinii apelate.
Când este definit un asemenea header, includerea cuvântului rezervat forward va anunţa compilatorul (Borland) PASCAL ca întreg corpul logic al rutinei împreuna cu toate declaraţiile sale vor apărea mai târziu în program. În cazul nostru, vom scrie următorul header:
FUNCTION cosine(x:real): real; forward;
după care vom proceda la fel pentru funcţia sine.
FUNCTION cosine(x:real):real;forward; FUNCTION sine(x:real):real;
Prezentăm în cele ce urmează funcţiile mutuale complet recursive cosine şi sine:
FUNCTION cosine(x:real):real;forward; FUNCTION sine(x:real):real; CONST epsilon=0.01; BEGIN IF abs(x)<epsilon THEN sine:=x*(1-x*x/6) ELSE sine:=2*sine(x/2)*cosine(x/2) END {sine}; FUNCTION cosine(x:real):real; CONST epsilon=0.02; BEGIN IF abs(x)<epsilon THEN cosine:=1-x*x/2 ELSE cosine:=sqr(cosine(x/2))-sqr(sine(x/2))
END {cosine};
5. Probleme recursive5.1. Recursivitatea în prelucrarea datelor elementare
1. Să se scrie un subprogram recursiv care apelat într-un program principal să conducă la afişarea următorului triunghi de steluţe, pentru citirea de la tastatură a valorii n=4.** ** * ** * * *
var n:integer;procedure rec(k:integer);var i: integer;beginif k=n then for i:=1 to k do write(’* ’)else begin
for i:=1 to k do write(’* ’); writeln;
rec(k+1) end;end;begin {pp} write(’n= ’); readln(n); rec(1); readkeyend.
2.Să se scrie un program care să utilizeze recursivitatea şi care pentru citirea de la tastatură a valorii n=5, să afişeze următorul triunghi de numere:
54 53 4 52 3 4 51 2 3 4 5
var n: integer;procedure tiplinie(l:integer);begin
if l=1 then write(n-l+1,’ ’)else begin
write(n-l+1,’ ’);tiplinie(l-1);
endend ;procedure rec(k:integer);begin
if k=n then tiplinie(n)else begin
tiplinie(k)writeln;rec(k+1)
endend;begin{pp}
write(’n= ’);rec(1);readkey
end.
3. Se citesc de la tastatură coeficienţii reali a,b,c,d, a≠0 ai ecuaţiei: ax?+bx?+cx+d=0. Notăm cu x1,x2,x3 rădăcinile acestei ecuaţii. Pentru un n natural şi strict pozitiv citit de la tastatură, să se scrie un program ce utilizează recursivitatea pentru calculul sumei: Sn= x1
n+x2n+x3
n
S0=x10+x2
0+x30=3
S1=x1+x2+x3= -b/aS2=x1
2+x22+x3
2= (x1+x2+x3)2-2(x1x2+x1x3+x2x3)=S12-2c/a
…avem că a∙ Sn+b∙Sn-1+c∙Sn-2+d∙Sn-3=0, adică
Sn=-b/a∙Sn-1 - c/a∙Sn-2 - d/a∙Sn-3
(am folosit relaţiile lui Viete pentru ecuaţia de gradul al II-lea)
var a,b,c,d: real; n:integer;function s(k:integer):real;begin
if k=0 then s:=3 else if k=1 then s:=-b/a
else if k=2 then s:= sqr(b)/sqr(a)-2*c/a else s: =-b/a*s(k-1) - c/a*s(k-2) - d/a*s(k-3);
end;begin {pp}write(’a= ’);readln(a);write(’b= ’);readln(b);write(’c= ’);readln(c);write(’d= ’);readln(d);write(’n= ’);readln(n);writeln(’Suma este: ’, s(n):6:3);readkeyend.
4. Se citeşte de la tastatură un număr natural ce va fi memorat într-o variabilă de tipul longint. Se cere să se scrie un subprogram recursiv care să afişeze numărul format cu cifrele sale inversate.
var n:longint ;procedure invers(k:longint);begin if k<>0 then begin
write (k mod 10);invers(k div 10);
end;end;beginwrite(’n= ’);readln(n);invers(n);readkeyend.
5. Să se calculeze cel mai mare divizor comun a două numere naturale citite de la tastatură.
Vom folosi următoarea formulă recursivă:
cmmdc(a,b)=
restîn b), mod acmmdc(b,
0b dacã a,
0a dacã b,
0b si 0a dacã existã,nu
var a,b,c: integer;function cmmdc(x,y:integer):integer;begin
if (x=0) and (y=0) then cmmdc:=0else if y=0 then cmmdc:=x
else if x=0 then cmmdc:=yelse cmmdc:=cmmdc(y,x mod y)
end ;begin
write(‘a= ’);readln(a);write(‘b= ’);readln(b);c:=cmmdc(a,b);
if c=0 then writeln (‘cmmdc(0,0) nu este definit’)else writeln(cmmdc(‘, a,’,’,b,’)= ’,c);
readkeyend.
6. Se citeşte de la tastatură un număr natural n>0. Să se afişeze, utilizând recursivitatea, descompunerea lui n în factori primi.
Vom scrie un subprogram recursiv, care primind ca argument un număr natural K, determină cel mai mic divizor al său precum şi puterea la care acest divizor apare în cadrul descompunerii în factori primi. Apoi, subprogramul se va apela recursiv pentru numărul obţinut prin împărţirea lui k la numărul obţinut prin ridicarea la putere a divizorului la factorul lui.
var n,s: integer;procedure descompunere(k:integer);var divizor, putere: integer;begin if k>1 then
begin divizor:=s+1; while k mod divizor <>0 do
divizor:=divizor+1; putere:=0; while k mod divizor=0 do begin
putere:=putere+1;k:=k div
divizor;end;
writeln(divizor,’ ^ ‘,putere); s:=divizor; descompunere(k);end;
end;begin write(‘n= ’); readln(n); s:=1; if n<>1 then descompunere(n) else write(n); readkeyend.
7. Să se scrie un subprogram recursiv care calculează Ckn , utilizând
formula de recurenţă:
Ckn = rest in , C + C
1=k dacã n,
0=k dacã 1,
1-k1-n
k1-n
var n,k: longint;
function comb(n,k:longint):longint;begin if k=0 then comb:=1 else if k>n then comb:=0
else comb:=comb(n-1,k)+comb(n-1,k-1)end;begin write(‘n= ’); readln(n); write(‘k= ‘); readln(k); writeln(‘comb(‘,n,’,’,k,’)= ’, comb(n,k)); readkeyend.
5.2.Recursivitatea în prelucrarea tablourilor unidimensionale
1. Să se scrie un subprogram recursiv care determină minimul dintre componentele unui vector citit de la tastatură.
type vect=array[1..10] of integer;var v:vect; n,i: integer;function min(a,b:integer):integer;begin if a>=b then min:=b else min:=aend;function minvect(n:integer):integer;begin if n=1 then minvect:=v[1] else if n=2 then minvect:=min(v[1],v[2])
else minvect:=min(v[n],minvect(n-1))end;begin write(‘Introduceti dimensiunea vectorului: ‘); readln(n); for i:=1 to n do begin write(‘v[‘,i,’]= ’);
readln(v[i]); end; write(‘minimul este: ’, minvect(n)); readkeyend.
2. Să se scrie un program care determină recursiv media aritmetică a componentelor unui vector citit de la tastatură.
type vect=array[1..10] of real;var v:vect; n,i:integer;function suma(k:integer):real;begin if k=1 then suma:=v[1]; else suma:=v[k]+suma(k-1);end;begin write(‘Intoduceti dimensiunea vectorului: ’); readln(n); for i:=1 to n do begin
write(‘v[‘,i,’]= ’); readln(v[i]); end; writeln(‘Media aritmetica a elementelor vectorului este: ’, (suma(n)/n):6:2); readkeyend.
3.Să se scrie un program care determină recursiv produsul scalar a doi vectori de numere întregi citiţi de la tastatură.
type vect=array[1..10] of longint;var a,b:vect; n,i:integer;function prods(k:integer):longint;beginif k=n then prods:=a[n]*b[n] else prods:=a[k]*b[k]+prod(k+1);
end;begin write(‘Introduceti dimensiunea vectorilor: ’) readln(n); for i:=1 to n do begin write(‘a[‘,i,’]= ’); readln(a[i]); end; writeln; for i:=1 to n do begin write(‘b[‘,i,’]= ’); readln(b[i]); end; writeln(‘Produsul scalar al vectorilor a şi b este: ’, prods(1)); readkeyend.
4. Să se scrie un program care caută existenţa unui element x citit de la tastatură într-un şir ordonat crescător, folosind metoda căutării binare. Ideea implementării metodei căutării binare este următoarea:
- se compară elementul x cu elementul din mijloc al şirului;- dacă ele sunt egale, s-a găsit elementul căutat şi algoritmul se
întrerupe;- dacă elementul x este mai mânc decât cel din mijloc, vom relua
căutarea pentru prima parte a şirului;- dacă este mai mare, căutarea se va face numai în partea dreaptă a
şirului faţă de elemntul din mijloc.
Type vect=array[1..20] of integer;Var v:vect; poz,x,n,i:integer;function cautbin(inc,sf:integer):integer;var mij:integer;begin
if inc<=sf then beginmij:=(inc+sf) div2;
if x=v[mij] then cautbin:=mij;else if x<v[mij] then
cautbin:=cautbin(inc,mij-1) else cautbin:=cautbin(mij+1,sf)
end;else cautbin:=0;
end;begin writeln(‘Introduceti elementul căutat: ‘); readln(x); write(‘Introduceti dimensiunea vectorului: ’); readln(n); for i:=1 to n do begin
write(‘v[‘,i,’]= ’); readln(v[i]); end; poz:=cautbin(1,n); if poz=0 then
writeln(‘Elementul ‘,x,’ nu se afla în sir’) else writeln (‘Elementul ‘,x,’ se găseşte în şir pe poziţia: ’,poz); readkeyend.
5. Să se rezolve recursiv problema punctului fix: fiind dat un vector ordonat de numere întregi distincte, să se determine un indice m (1<=m<=n), cu v[m]=m, dacă este posibil.
Vom folosi ideea problemei anterioare: determinăm m mijlocul vectorului şi verificăm dacă v[m]>m, cum vectorul este ordonat crescător, vom efectua căutarea în stânga, altfel în dreapta.
type vect=array[1..20] of integer;Var v:vect; poz,n,i:integer;function cautbin(inc,sf:integer):integer;var mij:integer;begin
if inc<=sf then beginmij:=(inc+sf) div2;
if x=v[mij] then cautbin:=mij;else if x<v[mij] then
cautbin:=cautbin(inc,mij-1) else cautbin:=cautbin(mij+1,sf) end;
else cautbin:=0;
end;begin write(‘Introduceti dimensiunea vectorului: ’); readln(n); for i:=1 to n do begin
write(‘v[‘,i,’]= ’); readln(v[i]); end; poz:=cautbin(1,n); if poz=0 then writeln(‘Sirul nu admite punct fix’) else writeln(‘Punctul fix se găseşte în şir pe poziţia ’,poz); readkeyend.
5.3. Alte probleme ce utilizează recursivitatea
1. Se citesc n,A1,r (numere naturale). Să se calculeze suma A1!+A2!+A3!+...+An!, unde A1,A2,…,An reprezintă termeni ai progresiei aritmetice cu prim termen A1 şi raţie r, iar K!=1*2*3*…*k.
Se folosesc următoarele funcţii recursive:- function A(n:integer):integer- calculează termenul n al progresiei
aritmetice.- function fact(n:integer):longint- calculează n!.- function suma(n:integer):integer- calculează suma primilor n termeni
din şirul cerut.Toate sunt funcţii pentru care înainte de implementare se caută o relaţie de recurenţă pentru funcţia A.
var n,a1,r :integer;function A(n:integer):integer;begin
if n=1 then A:=A1else A:=A(n-1)+r;
end;
function fact(n:integer):longint;begin
if n=1 then fact:=1else fact:=n*fact(n-1);
end;
function suma(n:integer):longint;
beginif n=0 then suma:=0else suma:=fact(A(n))+suma(n-1);
end;
beginreadln(n,A1,r);
writeln(suma(n));end.
2. Se dă un număr natural n. Să se scrie n ca sumă de numere prime. Obs! 1 se va considera număr prim.
var a,x:array[0..100] of integer ; n,I,s,m: integer;ok:boolean;function prim(n:integer):boolean;var i:integer;beginprim:=true;for i:=2 to trunc(sqrt(n)) do
if n mod i=0 thenbegin
prim:=false;break;end;
end;
procedure tipar (k:integer);var i:integer;beginfor i:=1 to k do
write(a[x[i]]);writeln;end;
procedure back(k:integer);var i:integer;beginfor i:=x[k-1]+1 to n do
beginx[k]:=I; s:=s+a[x[k]];if s<=n then if s=n then
tipar(k)else back(k+1);s:=s-a[x[k]];
end;end;
begin{main}write(‘n= ’);readln(n);m:=0;for i:=1 to n do
if prim(i) thenbegin
inc(m);a[m]:=i;
end;x[0]:=0;s:=0;back(1);readln;end.
3. Se dă un alfabet care conţine v vocale şi c consoane. Să se genereze toate cuvintele de lungime n care nu conţin trei vocale sau trei consoane alăturate.
Vocalele şi consoanele alfabetului vor fi memorate în vectorul a. Primelev elemente reprezintă vocalele, următoarele c elemente consoanele. Vectorul soluţie x=(x1,x2,…,xn) va avea ca valori indicii elementelor din a iar elementele sale vor lua valori din mulţimea {1,…,v+c}. Vocalele vor fi elemente din a din poziţiile {1,…,v} , iar consoanele elementele din a din poziţiile {v+1,…,v+c}.
Var x:array[1..20] of integer;n,i,v,c,m:integer;a:array[1..20] of char;car:char;f:text;
function cont (k:integer):boolean;var i:integer;begin cont:=true;
if k>2 then if (x[k]<=v) then
begin if (x[k-1]<=v) and (x[k-2]<=v) then
cont:=false; end
else if (x[k-1]>v) and (x[k-2]>v) then
cont:=false;end;
procedure tipar;var i:integer;beginfor i:=1 to n do write(a[x[i]]);writeln;end;
procedure back(k:integer);var i:integer;beginfor i:= 1 to v+c dobegin
x[k]:=1;if cont(k) then
if k=n thentipar
else back(k+1);
end;end;
beginassign(f’,date.in’);reset(f);readln(f,n);readln(f,v);m:=0;for i:=1 to v dobegin
read(f,car);inc(m);a[m]:=car;end;
readln(f,c);for i:=1 to c dobegin
read(f,car);inc(m);a[m]:=car;end;close(f);back(1);readln;end.
4. Se consideră n soldaţi numerotaţi de la 1 la n. Se citescde la intrare k perechi de numere (i,j) cu i<>j, 1<=i<=n, 1<=j<=n, cu semnificaţia că i este superiorul lui j. se cere să se aşeze soldaţii într-un rând, în mod ierarhic, astfel încât fiecare soldat să aibă subalternii săi situaţi după el.
Exemplu : pentru n=6, k=4 şi perechile (1,5), (4,5), (2,3), (1,4), ieşirile posibile sunt : 1 2 4 6 3 5, 2 1 4 5 3, …
Pentru a reprezenta relaţiile existente între soldaţi se va folosi un tablou bidimensional n x n, ale cărui elemente a[i,j] vor avea valorile 1 dacă i este superiorul lui j, 0 în caz contrar. Vectorul soluţie va fi x=(x1,x2,…,xn), x[k] reprezintă codificarea unui soldat, iar lementele sale or lua valori din mulţimea {1,…,n}. Un element x[k] este valid dacă sunt îndeplinite următoarele condiţii de continuare :
- este diferit de toate valorile determinate anterior x[k]<>x[i], i={1,…,k-1}- nici un element anterior x[i] nu trebuie să fie subaltern lui x[k]: a[x[k],x[i]]<>1, i={1,…,k-1}
var a:array[1..20,1..20] of integer; x,viz:array[1..20] of integer; i,n,k,p,j:integer;f:text;Function cont(k:integer):boolean;Var i:integer;BeginCont:=true;for i:=1 to k-1 do
if a[x[k],x[i]]=1 then begin cont:=false;exit:end;end;
procedure tipar;
var i:integer;beginfor i:=1 to n do
write(f,x[i]);writeln(f);end;
5. La un concurs sunt prezentate 5 melodii notate A,B,C,D,E. Să se afişeze toate posibilităţile de a prezenta cele 5 melodii în ipoteza că melodia B va fi prezentată înaintea lui A.
Melodiile vor fi codificate prin numere de la 1 la 5. Elementele vectorului soluţie x=(x1,x2,x3,…,x5) vor lua valori din mulţimea {1,2,…,5}. Vectorul soluţie trebuie să aibă toate elementele distincte, valoarea 2 trebuie să fie în vector înaintea valorii 1. Astfel, condiţiile de continuare sunt îndeplinite dacă :
- x[k]<>x[i], i={1,…,k-1}- dacă x[k]=2 atunci x[i]<>1, i={1,…,k-1}Elementele vectorului soluţie vor lua valori din mulţimea
{‘A’,’B’,’C’,’D’,’E’}. Vectorul viz ţine evidenţa valorilor utilizate. Viz[i]=0 indică faptul că valoarea I nu a fost utilizată.
var x:array[1..5] of char;viz:array[‘A’..’E’] of integer;procedure tipar;var i:integer;beginfor i:= 1 to 5 dowrite (x[i]);writeln;end;
function cont(k:integer):boolean;var i:integer;begincont:=true;if x[k]=’B’ thenfor i:=1 yo k-1 do
if x[i]=’A’ then begin cont:=false;brek;end;end;
procedure back(k:integer);var i:char;baginfor i:= ‘A’ to ‘E’ dobeginx[k]:=i;if viz[i]=0 then
if cont(k) thenbegin
viz[i]:=1;if k=5 then tiparelse back(k+1);
viz[i]:=0;end;
end;end;
beginback(1);readln;end.
6. Să se scrie un program care, citind în cuvânt şi un număr natural cuprins între 1 şi lungimea cuvântului să se afişeze toate anagramările obţinute din acest cuvânt, după eliminarea literei de pe poziţia citită.
var x,viz:array[1..10] of integer; cuv:strâng;p:integer;procedure tipar;var i:integer;baginfor i:=1 to length(cuv) do
writw(cuv[x[i]]);writeln;end;
procedure back(k:integer);var i:integer;beginfor i:=1 to length(cuv) do
if viz[i]:=0 thenbegin
x[k]:=i;
viz[i]:=1;if k=length(cuv) then
tiparelse
back(k+1);viz[i]:=0;
end;end;
beginwrite(‘dati cuvantul’); readln(cuv);reapeat
write(‘pozitia:’);readln(p);until p în [1..length(cuv)];delete(cuv,p,1);back(1);readln;end.
7. Figuri recursiveDupă cum am mai spus, recursivitatea are o mare arie de întrebuinţare şi
de aplicabilitate. În continuare, voi prezenta o folosire a recursivităţii în grafica de sub Borland Pascal prin încercarea de realizare a unor „figuri recursive”.
O astfel de figură recursivă este cea pe care o prezint mai jos.
Această figură o voi numi „diamant”. Observăm forma recursivă a acestui diamant. El este perfect caracterizat de coordonatele centrului său, precum şi de latura pătratului iniţial. Pătratele imediat următoare, au laturile de
c ori mai mici, unde c este o constantă reală oarecare, c≥1. De fapt, acest diamant se constituie dintr-un pătrat de centru (x,y) şi de latură l şi dintr-un cerc cu acelaşi centru ca pătratul iar raza egală cu diferenţa dintre latura pătratului şi jumătate din diagonala sa. Pătratul are patru diamante în colţurile sale. Aceasta este o definiţie recursivă a diamantului.
Astfel, vom putea scrie cu uşurinţă o procedură care să-l deseneze. Această procedură va desena un pătrat şi un cerc, care au acelaşi centru, apoi se va autoapela de patru ori, pentru cele patru diamante din colţurile pătratului. Trebuie să existe, însă, şi o condiţie de oprire deoarece programul ar afişa diamante din ce în ce mai mici de un număr infinit de ori, şi astfel s-ar depăşi stiva de memorie cu care lucrează Borland Pascal. De aceea vom introduce o condiţia ca diamantele să fie desenate atâta timp cât latura pătratului este mai mare strict decât 0.
În program am folosit directivele de compilare {$S-} – pentru a face compilatorul să nu ţină seama de depăşirea stivei, şi {$S+} – pentru a reveni la controlul normal al umplerii stivei.
Voi prezenta mai jos programul cu ajutorul căruia am realizat desenul anterior, cu precizarea că singurele proceduri grafice pe care le-am folosit sunt: Line şi Circle. Nu voi insista asupra utilizării graficii în Borland Pascal. Iată programul:
program FiguraRecursiva;var mg,er,d:integer;procedure patratcerc(x,y,l:integer);var l2:integer;begin
l2:=round(l/sqrt(2));line(x-l2,y,x,y-l2);line(x,y-l2,x+l2,y);line(x+l2,y,x,y+l2);line(x,y+l2,x-l2,y);circle(x,y,l-l2);
end;{$S-}procedure diamant(x,y,l:integer);const c=2.7;var l2,l3:integer;beginif l>0 then begin patratcerc(x,y,l); l2:=round(l/sqrt(2));
l3:=round(l/c); diamant(x-l2,y,l3); diamant(x,y+l2,l3); diamant(x+l2,y,l3); diamant(x,y-l2,l3);end;end;{$S+}begind:=detect;initgraph(d,mg,'c:\bp\bgi');er:=graphresult;if er<>grok thenbegin writeln('Eroare grafica :',grapherrormsg(er)); halt; end;setcolor(blue);setbkcolor(white);diamant(GetMaxX div 2, GetMaxY div 2, GetMaxY div 3);readln;closegraph;end.
Dacă am prezentat o aplicaţie grafică a recursivităţii directe, trebuie să prezentăm şi o aplicaţie a recursivităţii indirecte, realizată cu ajutorul cuvântului cheie forward, despre care am vorbit în capitolele anterioare.
Şi această aplicaţie se înscrie în seria „figurilor recursive”, şi ilustrează totodată lucrul cu mouse-ul în modul grafic, dar nu voi insista asupra acestui lucru. Precizez doar faptul că în program se foloseşte un unit pentru lucrul cu mouse-ul, unit ce cuprinde unele proceduri realizate în limbaj de asamblare (procedurile init, show, clear, done, getx, gety, etc.).
Astfel acţiunea mouse-ului este următoarea: la apăsarea butonului drept se va afişa o figură recursivă, iar la apăsarea celuilalt buton, altă figură recursivă.
Un posibil rezultat al programului pe care-l voi prezenta este următorul:
În acest exemplu am folosit de trei ori butonul drept al mouse-ului şi de patru ori pe cel stâng. Se observă că acest diamant este o figură geometrică (un cerc ori un pătrat) care are la capetele unui diametru, respectiv unei diagonale, câte un alt diamant care este de acelaşi tip cu el, iar la capetele diametrului perpendicular pe el, respectiv a celeilalte diagonale, câte un diamant care nu este de acelaşi tip cu el (diamantul realizat la apăsarea celuilalt buton al mouse-ului).
Programul este următorul:
program DesenareCuMouse;const n1=0;ns=1;nd=2;nt=3;var am:tmouse;x,y:integer;d,mg,er:integer;
procedure romb(x,y,l:integer);var l2:integer;begin
l2:=round(l/sqrt(2));line(x-l2,y,x,y-l2);line(x,y-l2,x+l2,y);line(x+l2,y,x,y+l2);line(x,y+l2,x-l2,y);
end;
procedure diamantcercuri(x,y,l:integer); forward;procedure diamantromburi(x,y,l:integer);const c=2.3;var l2,l3:integer;beginif l>0 then begin
romb(x,y,l);l2:=round(l/sqrt(2));l3:=round(l/c);diamantcercuri(x-l2,y,l3);diamantromburi(x,y-l2,l3);diamantcercuri(x+l2,y,l3);diamantromburi(x,y+l2,l3);
end;end;procedure diamantcercuri(x,y,l:integer);const c=3;var l2,l3:integer;beginif l>0 then begin
circle(x,y,l);l2:=round(l/sqrt(2));l3:=round(l/c);diamantromburi(x-l2,y,l3);diamantcercuri(x,y-l2,l3);diamantromburi(x+l2,y,l3);diamantcercuri(x,y+l2,l3);
end;end;{$S+}begin
d:=detect;initgraph(d,mg,'c:\bp\bgi');er:=graphresult;if er<>grok then
beginwriteln('Eroare grafica :',grapherrormsg(er));halt;
end;setcolor(blue);setbkcolor(white);
am.init;am.show;repeatx:=am.getx;y:=am.gety;if am.leftbutton then beginam.clear;diamantcercuri(x,y,50);am.show;end;if am.rightbutton then beginam.clear;diamantromburi(x,y,50);am.show;end;until (am.leftbutton and am.rightbutton) or keypressed;end.
Cristea Valentin, Atanasiu Irina, Iorga Valeriu, Kalisz Eugenia : ,,Tehnici de programare’’, Editura Teora, Bucureşti – 1994;
Niculescu Ştefan, Cerchez Emanuela: “Bacalaureat şi atestat în informatică”, Editura L&S Informat, Bucureşti – 1999;
Creţu Vladimir Ioan, Rodica Pintea : ’’Culegere de probleme Pascal’’ Editura Petrion, Timişoara – 1992 ; Doina Rancea: „Limbajul Pascal”, vol I şi II Editura Libris, Cluj - 1994;
Carmen Popescu: „Culegere de probleme de informatică”, Editura Donaris, Sibiu - 2002
Tudor Sorin: „Tehnici de programare” Editura Teora, Bucureşti - 1994;