În plus față de răspunsul @Harry.
Tipuri de recursiune
Funcțiile recursive pot fi împărțite în mai multe tipuri:
- regresie liniară. în care apelul recursiv pe orice felie recursiv este inițiată nu mai mult de un apeluri recursive ulterioare. (ca în exemplul din @Harry)
- reversiune coada (un caz special de recursiune liniară), în care apare un apel de funcție recursivă la sfârșitul funcționării sale. (ca în exemplul lui Harry).
- regresie neliniară sau paralelă. în care apelurile recursive pe orice felie recursivă declanșează mai mult de un apel recursiv ulterior.
Un exemplu bun de acest tip este calculul celui de-al n-lea membru al seriei Fibonacci:
- reciprocă sau indirectă. în care un apel recursiv al unei funcții date vine de la o altă funcție care este ea însăși chemată din funcția dată.
Când trebuie să folosesc recursiunea?
Utilizați recursiunea dacă:
- problema este împărțită în copii mai mici ale ei înșiși și nu există nici o modalitate evidentă de ao rezolva scriind un ciclu;
- Lucrați cu o structură de date recursivă, de exemplu, cu liste legate
DAR: Dacă sarcina poate fi rezolvată iterativ, utilizați iterația.
Cum să evitați reapariția?
- Trebuie să existe o condiție pentru ieșirea din recurs.
- Dacă regula 1 este îndeplinită, dar există încă o depășire, atunci ar trebui să abandonați recursul și să implementați algoritmul iterativ. (cicluri și programări dinamice pentru a vă ajuta)
Un exemplu factorial iterativ:
În sfârșit, o mai bună înțelegere a teoriei este realizată prin aplicarea acesteia în practică.