Ce este recursivitatea?

O funcție care se apelează pe ea însăși pentru un caz mai mic al aceleiași probleme, cu un caz de bază la care se oprește.

O funcție este recursivă când se apelează pe ea însăși, pentru un caz mai mic al aceleiași probleme:

int factorial(int n) {
    if (n == 0) return 1;           // cazul de bază
    return n * factorial(n - 1);    // pasul recursiv
}

Orice funcție recursivă are două părți obligatorii. Cazul de bază se rezolvă direct, fără alt apel. Pasul recursiv reduce problema la una mai mică, mai aproape de cazul de bază. Fără caz de bază, apelurile continuă la nesfârșit și programul se oprește brusc.

La Subiectul I, întrebarea tipică este ce afișează un apel. Răspunsul depinde de un detaliu: dacă lucrul (afișarea, înmulțirea) se face înainte sau după apelul recursiv. cout << n; f(n-1); afișează descrescător, iar f(n-1); cout << n; afișează crescător. Urmărește apelurile desenându-le indentat, nu din memorie.

Lecția Recursivitate are schema de urmărit și avertismentul despre Fibonacci recursiv.

Lecția care merge mai departe: Recursivitate