Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Recursivitate

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Sortare
Constante in virgula mobila
LISTE - Sortare prin interclasare
Functii de citire si scriere a caracterelor
Instructiunea break
Identificatori
TEHNICA BACKTRACKING - PREZENTAREA TEHNICII BACKTRACKING
Functii membru virtuale
Codificarea arborilor
Apelul functiilor

TERMENI importanti pentru acest document

Recursivitate

Prezentare generala




Intr-un limbaj de programare, o subrutina este o functie sau o procedura. In algoritmica, prin procedura se intelege o functie care nu returneaza nici o valoare. Un subprogram recursiv este un subprogram care se autoapeleaza. Recursivitatea este un mecanism utilizat in elaborarea programelor pentru algoritmii recursivi. Deci, recursivitatea a aparut, in special, din necesitatea transcrierii directe a formulelor matematice recursive.

Pentru a putea implementa recursivitatea se foloseste structura de date stiva. Stiva este folosita atat in cazul apelurilor nerecursive, cat si in cazul apelurilor recursive. De data aceasta, stiva este gestionata de limbaj. La apelul recursiv al unei subrutine se depun in stiva :

valorile parametrilor transmisi prin valoare;

adresele parametrilor transmisi prin referinta;

valorile variabilelor locale (declarate la nivelul subprogramului).

Probleme rezolvate

Problema R1

Sa luam ca prim exemplu functia factorial, a carei definitie matematica recurenta este:

f1(n) = 

Rezolvare

In pseudocod, aceasta functie se transcrie astfel :

FUNCTIE f1(n);

BEGIN

IF n = 0 THEN

f:= 1

ELSE

f:= n* f1(n-1);

ENDIF;

END;

Se observa in linia (6) apelul recursiv al functiei (apelul din corpul functiei tot la ea, pana cand conditia n = 0 este indeplinita). Sa vedem functionarea functiei pentru n = 3; prin s notam stiva :

iteratia 1: n := 3, s := (3);

iteratia 2: n := 2, s := (2, 3);

iteratia 3: n := 1, s := (1, 2, 3);

iteratia 4: n := 0, s := (0, 1, 2, 3);

f1 = 1 si 0 este eliminat din stiva; f1 = 1*1 = 1 si 1 este eliminat din stiva; f1 = 2*1 = 2 si 2 este eliminat din stiva; f1 = 3*2 = 6 si 3 este eliminat din stiva; s = si se revine in programul apelant.

Codul sursa al programului este:

#include<stdio.h>

int factorial(int n)

void main()

Varianta iterativa a factorialului este urmatoarea:

In pseudocod se transcrie astfel :

FUNCTIE f1(n);

BEGIN

f:= 1;

IF n > 0 THEN

FOR i := 2 TO N DO

f:= f1 i;

ENDFOR;

ENDIF;

END;

Codul sursa al programului este:

#include<stdio.h>

int factorial(int n)

void main()

Problema R2

Sa se determine al n-lea element al sirului lui Fibonacci, care este definit recurent astfel:

Rezolvare

In pseudocod formula de mai sus se transcrie in modul urmator:

FUNCTIE f2(n);

BEGIN

IF n = 0 THEN f2 := 1

ELSE

IF n = 1 THEN f2 := 1

ELSE f2 := f2(n1) + f2(n2);

ENDIF;

ENDIF;

END;

Textul sursa al programului este:

#include<stdio.h>

int fibo(int n)

void main()

Sa vedem modul in care se realizeaza calculul recursiv al celui de-al n-lea element al sirului lui Fibonacci pentru n = 5. Modul de calcul este reprezentat sugestiv pe arborele binar din figura 4.1


Pentru calculul lui f2(5) este necesar sa se cunoasca f2(4) si f2(3). Parametrii acestor doua functii sunt depusi in stiva. Procedeul continua pana cand este calculat f2(4) (subarborele stang al nodului radacina etichetat cu 8 = f2(5)), apoi se reia calculul pentru f2(3) (subarborele drept al nodului radacina). Este evident ca multe calcule se repeta inutil. De aceea, cand avem de rezolvat o astfel de problema este bine sa analizam oportunitatea folosirii unei metode recursive sau a uneia iterative. In cazul sirului Fibonacci este recomandat sa se foloseasca un program care calculeaza f2(n) iterativ. Varianta iterativa este urmatoarea:

FUNCTIE f2(n) ;

BEGIN

IF n = 0 THEN f2 := 1

ELSE

IF n = 1 THEN f2 := 1

ELSE

BEGIN

f20 := 1; f21 := 1;

FOR i := 2 TO n DO

f:= f20 + f21; f20 := f21; f21 := f2;

ENDFOR;

END;

ENDIF;

ENDIF;

END;

Codul sursa al programului este:

#include<stdio.h>

int fibo(int n)

return f2;

void main()

In algoritmica exista urmatorul rezultat de exceptie: pentru orice algoritm iterativ, exista unul recursiv echivalent (rezolva aceeasi problema) si invers, pentru orice algoritm recursiv, exista unul iterativ echivalent.

Sunt probleme pentru care elaborarea unui algoritm recursiv duce la un timp de calcul foarte mare, iar daca se elaboreaza un algoritm iterativ, timpul necesar de calcul este cu mult mai mic, asa cum s-a vazut in exemplul anterior. Pe de alta parte, implementarea unui algoritm recursiv conduce la un text sursa extrem de scurt si de cele mai multe ori, clar. Depinde de priceperea programatorului daca pentru o problema data elaboreaza un algoritm recursiv, sau unul iterativ.

Recursivitatea poate fi utilizata si in elaborarea algoritmilor recursivi care nu descriu formule matematice recurente. Sa consideram urmatorul exemplu:

Problema R3

Trecerea unui numar natural n, n ≥ 2, din baza 10 in baza 2.

Rezolvare

Dupa cum se stie n se imparte la 2 si se retine restul; catul se imparte la 2 si se retine restul, si asa mai departe se retin resturile obtinute prin impartirea catului la 2 pana cand catul devine 0. Numarul n in baza 2 se obtine considerand toate resturile in ordinea inversa a impartirilor.

Formula recursiva este urmatoarea:

t(n) = t(n div 2) + w(n div 2)

unde w inseamna WRITE.

In pseudocod aceasta formulare se transcrie astfel:

FUNCTIE t(n);

BEGIN

r := n mod 2;

IF n > 0 THEN



t(n div 2);

WRITE r;

ENDIF;

END;

Codul sursa al programului este:

#include<stdio.h>

void transf(int n)

void main()

Deoarece r este variabila locala, valorile ei vor fi salvate in stiva.

Daca k log n + 1 atunci varianta iterativa a problemei se transcrie in pseudocod astfel:

FUNCTIE t(n, k);

BEGIN

ARRAY r(k)

FOR i := 1 TO k DO

r[ k i + 1 ] := n mod 2;

n := n div 2;

ENDFOR;

WRITE r;

END;

Codul sursa al programului este:

#include<stdio.h>

#include<math.h>

void t(int n, int k)

for(i=1;i<=k;i++)

printf('%d',r[i]);

void main()

Problema R4

Se da o matrice A cu n linii si n coloane. Sa se afiseze parcurgerea matricei in spirala dupa cum se vede in figura urmatoare.

 


Rezolvare

O matrice de dimensiune n are (n + 1) div 2 patrate concentrice. Fiecare patrat va fi parcurs in felul urmator: linia de sus de la stanga spre dreapta, coloana din dreapta de sus in jos, linia de jos de la dreapta spre stanga, coloana din stanga de jos in sus. Fiecare din cele patru parcurgeri se face in cate un subprogram recursiv. Parcurgerea in spirala a matricei se realizeaza tot intr-un subprogram recursiv.

In pseudocod aceste subprograme se transcriu astfel:

SUBPROGRAM SUS(I, J);

BEGIN

IF J ≤ N I + 1 THEN

WRITE AIJ ;

SUS(I, J + 1);

ENDIF;

END;

SUBPROGRAM DREAPTA(I, J);

BEGIN

IF I ≤ J THEN

WRITE AIJ ;

DREAPTA(I + 1, J);

ENDIF;

END;

SUBPROGRAM JOS(I, J);

BEGIN

IF J ≥ N I + 1 THEN

WRITE AIJ ;

JOS(I, J 1);

ENDIF;

END;

SUBPROGRAM STANGA(I, J);

BEGIN

IF I ≥ J + 1 THEN

WRITE AIJ ;

STANGA(I 1, J);

ENDIF;

END;

SUBPROGRAM SPIRALA(K);

BEGIN

IF K ≤ (N + 1) DIV 2 THEN

SUS(K, K);

DREAPTA(K + 1, N K + 1);

JOS(N K + 1, N K);

STANGA(N K, K);

SPIRALA(K + 1);

ENDIF;

END;

Codul sursa al programului este:

#include<stdio.h>

void sus(int a[20][20], int n, int i, int j)

void dreapta(int a[20][20], int n, int i, int j)

void jos(int a[20][20], int n, int i, int j)

void stanga(int a[20][20], int n, int i, int j)

void spirala(int a[20][20], int n, int k)

void main()

spirala(a, n, 1);






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 923
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site