Recursivitate și iterație

Unele calcule pot fi scrise atât cu apeluri recursive, cât și cu o buclă. Factorialul lui 4 se obține prin $4\cdot 3\cdot 2\cdot 1=24$ în ambele forme. Alegerea ține de claritatea problemei, de memoria folosită și de limite: apelurile recursive ocupă stivă, pe când o buclă simplă poate folosi doar câteva variabile.

Multe calcule se pot scrie în două moduri echivalente: recursiv, cu un subprogram care se apelează pe el însuși, și iterativ, cu un ciclu. Alegerea ține de claritatea soluției, de memorie și de timp. Varianta iterativă păstrează de obicei câteva variabile și folosește spațiu auxiliar constant. Varianta recursivă păstrează câte un cadru pe stivă pentru fiecare apel activ, deci cere spațiu proporțional cu adâncimea recursiei, iar o recursie foarte adâncă poate umple stiva. În schimb, pentru definiții care au natură recursivă (arbori, divizarea problemei în subprobleme), soluția recursivă este mai scurtă și mai ușor de verificat. Orice calcul recursiv poate fi simulat iterativ cu o stivă explicită, iar orice ciclu se poate rescrie recursiv.

Exemplul 1 — factorialul în ambele forme.

#include <iostream>
using namespace std;
long long factRec(int n) { return n == 0 ? 1 : n * factRec(n - 1); }
long long factIter(int n) {
    long long p = 1;
    for (int i = 2; i <= n; ++i)
        p *= i;
    return p;
}
int main() {
    cout << factRec(4) << " " << factIter(4);
    return 0;
}

Programul afișează 24 24. Varianta recursivă face $n+1$ apeluri și păstrează $n+1$ cadre pe stivă; varianta iterativă face $n-1$ înmulțiri și folosește două variabile. Ambele au timp proporțional cu $n$, dar cea iterativă are memorie auxiliară constantă, pe când cea recursivă are memorie proporțională cu $n$.

Exemplul 2 — Fibonacci: recursie naivă contra iterație. Definiția $F(n)=F(n-1)+F(n-2)$, scrisă direct, apelează de două ori funcția și recalculează aceleași valori: pentru $F(10)$ se fac 177 de apeluri, iar pentru $F(20)$ se fac 21 891. Varianta iterativă păstrează ultimii doi termeni și face $n$ pași, deci pentru $F(20)$ face 20 de adunări, față de 21 891 de apeluri:

long long fibIter(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        long long urmator = a + b;
        a = b;
        b = urmator;
    }
    return a;
}

Pentru $n=10$ funcția întoarce 55, aceeași valoare ca recursia, dar cu zece iterații în loc de 177 de apeluri. Diferența dintre un număr exponențial și unul liniar de pași apare doar la varianta recursivă naivă; o recursie care nu repetă subproblemele, ca factorialul, are același număr de pași ca ciclul.

Exemplul 3 — suma cifrelor, recursiv și iterativ. Varianta recursivă n == 0 ? 0 : n % 10 + sumaCifre(n / 10) și ciclul while (n > 0) { s += n % 10; n /= 10; } dau amândouă 16 pentru $n=583$. Aici ciclul este mai scurt și nu cere stivă; recursia este utilă când pasul seamănă cu definiția matematică. La o problemă pe arbore, de exemplu parcurgerea tuturor nodurilor, recursia este mai simplă decât ciclul cu stivă explicită.

Exemplul 4 — cel mai mare divizor comun, cu invariant și condiție de oprire. Algoritmul lui Euclid se bazează pe egalitatea $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$, care rămâne adevărată la fiecare pas (invariantul), și se oprește când al doilea număr devine 0.

int cmmdcRec(int a, int b) { return b == 0 ? a : cmmdcRec(b, a % b); }
int cmmdcIter(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Pentru $a=48$ și $b=18$ perechile succesive sunt $(48,18)$, $(18,12)$, $(12,6)$, $(6,0)$, deci ambele funcții întorc 6. Recursia are patru apeluri active la un moment dat, iar ciclul folosește trei variabile. Apelul recursiv este ultima operație a funcției, așa că ciclul este o traducere directă a lui: parametrii noi se atribuie variabilelor, iar condiția de oprire devine negata condiției ciclului. Dacă se omite cazul b == 0, apelurile continuă până la umplerea stivei, iar programul se oprește cu eroare.

Greșeli frecvente

• Greșit: varianta recursivă este întotdeauna mai rapidă decât cea iterativă.
  Corect: de multe ori este la fel de rapidă, iar la Fibonacci naiv este exponențial mai lentă.
• Greșit: o recursie nu poate fi rescrisă cu un ciclu.
  Corect: poate fi rescrisă iterativ, uneori cu o stivă explicită.
• Greșit: recursia nu consumă memorie.
  Corect: fiecare apel activ ocupă un cadru pe stivă.

Înainte și după