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;