Recursivitate
Subprograme — subprograme recursive, stiva de apeluri, exemple clasice
- Recunoașterea cazului de bază și a pasului recursiv într-un subprogram dat și justificarea opririi apelurilor.
- Determinarea valorii returnate sau a rezultatului afișat de un apel recursiv, prin urmărirea stivei de apeluri.
- Scrierea subprogramelor recursive pentru factorial, ridicare la putere, cel mai mare divizor comun, suma cifrelor și șirul lui Fibonacci.
- O funcție recursivă se apelează pe ea însăși și are obligatoriu un caz de bază plus un pas recursiv care se apropie de el.
- Apelurile se păstrează pe stivă: ultimul apel început este primul care se încheie, iar fiecare apel are propriile variabile locale.
- Valoarea returnată se determină coborând până la cazul de bază, apoi urcând și înlocuind fiecare apel cu valoarea lui.
fact(n) = n * fact(n - 1),gcd(a, b) = gcd(b, a % b),digitSum(n) = n % 10 + digitSum(n / 10),fib(n) = fib(n - 1) + fib(n - 2).- Fibonacci are două cazuri de bază, iar varianta recursivă directă face
2 * fib(n + 1) - 1apeluri, deci este exponențială. - Un
coutscris înainte de apelul recursiv afișează la coborâre; scris după apel, afișează la urcare, în ordine inversă. - Recursivitatea scurtează codul, dar nu îl face mai rapid decât o structură repetitivă echivalentă.