Recursivitate: funcții care se autoapelează

Ce este recursivitatea

O funcție este recursivă dacă se apelează pe ea însăși. Orice funcție recursivă corectă are:

1. cazul de bază: condiția de oprire, fără autoapel;
2. cazul general: autoapelul pe o problemă MAI MICĂ.

Exemplul fundamental: factorialul

$n! = n \cdot (n-1)! \qquad 0! = 1$

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

int main() {
    cout << fact(5);
    return 0;
}

Urmărirea pentru fact(4): $4 \cdot fact(3) = 4 \cdot 3 \cdot fact(2) = 4 \cdot 3 \cdot 2 \cdot fact(1) = 4 \cdot 3 \cdot 2 \cdot 1 \cdot fact(0) = 24$.

Alte exemple clasice

Suma cifrelor:

#include <iostream>
using namespace std;

int sc(int n) {
    if (n == 0) return 0;
    return n % 10 + sc(n / 10);
}

int main() {
    cout << sc(4729);
    return 0;
}

sc(275) = 5 + sc(27) = 5 + 7 + sc(2) = 5 + 7 + 2 + sc(0) = 14.

Cel mai mare divizor comun (Euclid):

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    if (b == 0) return a;
    return cmmdc(b, a % b);
}

int main() {
    cout << cmmdc(48, 18);
    return 0;
}

cmmdc(24, 36) = cmmdc(36, 24) = cmmdc(24, 12) = cmmdc(12, 0) = 12.

Cum urmărești un apel la BAC

1. Scrie fiecare apel pe un rând, cu argumentele lui.
2. Coboară până la cazul de bază.
3. Urcă înapoi înlocuind fiecare apel cu valoarea returnată.

Greșeli frecvente

1. Ordinea contează: return n * fact(n-1) înmulțește DUPĂ întoarcerea din apel.
2. La afișări recursive, instrucțiunile de DINAINTE de autoapel se execută la coborâre, cele de DUPĂ la întoarcere: de aici apar afișările "inversate".
3. fact(0) este 1, nu 0.