Question

Buna!
Imi puteti da niste sfaturi ca sa pot crea solutii pentru problemele recursive? Stiu teoria din spate cu memoria stack, dar cumva imi e foarte greu sa impart problelemele pe probleme mai mici si mai apoi sa le pun cap la cap..

Answer 1

Te gandesti la o formula care sa fie valabila pentru toate elementele, mai putin pentru primul. La acesta solutia ar trebui sa fie banala.

Exemplu :

1. Factorial

Cat e factorial din n ?

n! = n * (n-1)!

Dar acum cat face factorial din n-1 ?

Pai n = n-1, deci e aceasi formula.

Pentru ce element formula nu mai merge ? Pentru n = 0. In cazul asta trebuie sa returnam

Deci avem

int factorial(int n){

if (n==0) retrun 1;

else return n*factorial(n-);

}

2. Suma Gauss

Cat e suma primelor 5 numere naturale ( suma(5) ) ?

Pai e n + suma(4)

Cat e suma primelor 4 numere naturale ?

Pai e n+ suma(3)

Deci formula e :

n + suma(n-1)

Cand suma nu mai merge calculata dupa formula aia ? Cand se ajunge la n = 0, caz in care returnam 0

int suma(int n){

if (n==0) return 0;

else return n + suma(n-1);

}

Stiu ca e dificil la inceput, lucreaza mai multe probleme si o sa iti dai seama pana la urma.