Relații de recurență — un termen din cei dinainte

Ce este o relație de recurență

O relație de recurență este o formulă care exprimă un termen al unui șir în funcție de termenii anteriori. În loc să dai o formulă directă pentru termenul de rang n, spui cum se construiește el din cei dinainte.

Forma generală arată așa:

termen(n) = f(termen(n-1), termen(n-2), ...)

Dar o regulă care trimite mereu spre termeni mai mici trebuie să se oprească undeva. De aceea orice recurență are două părți obligatorii:

1. Cazurile inițiale (de bază) — primii termeni, dați direct, fără formulă;
2. Pasul recurent — regula care leagă termen(n) de cei anteriori.

Fără cazuri inițiale, lanțul nu se închide niciodată — ca o recursivitate fără caz de bază.

Exemplu pas cu pas: Fibonacci și factorial

Cel mai cunoscut exemplu este șirul lui Fibonacci. Cazurile inițiale sunt F(0) = 0 și F(1) = 1, iar pasul recurent este:

F(n) = F(n-1) + F(n-2),  pentru n >= 2

Construim termenii unul câte unul, fiecare ca sumă a celor doi dinainte:

• F(0) = 0 (caz inițial)
• F(1) = 1 (caz inițial)
• F(2) = F(1) + F(0) = 1 + 0 = 1
• F(3) = F(2) + F(1) = 1 + 1 = 2
• F(4) = F(3) + F(2) = 2 + 1 = 3
• F(5) = F(4) + F(3) = 3 + 2 = 5
• F(6) = F(5) + F(4) = 5 + 3 = 8

Așa obținem șirul: 0 1 1 2 3 5 8 .... Observă cum fiecare termen se sprijină pe cei doi vecini din stânga.

Factorialul este tot o recurență, dar mai simplă — depinde de un singur termen anterior. Cazul inițial este 0! = 1, iar pasul recurent leagă n! de (n-1)!:

n! = n * (n-1)!,  pentru n >= 1

Deci 5! = 5 * 4!, 4! = 4 * 3! și tot așa până la 0! = 1. Diferența față de Fibonacci: factorialul cheamă un termen anterior, Fibonacci cheamă doi.

Implementare C++

Odată ce ai scris recurența pe hârtie, traducerea în cod este aproape mecanică: cazurile inițiale devin condiții de oprire, iar pasul recurent devine o expresie.

Versiunea recursivă naivă copiază formula literă cu literă:

#include <iostream>
using namespace std;

long long fibRecursiv(int n) {
    if (n < 2) return n;                          // cazuri initiale: F(0)=0, F(1)=1
    return fibRecursiv(n - 1) + fibRecursiv(n - 2); // pasul recurent
}

int main() {
    cout << fibRecursiv(7) << "\n";  // F(7)=13
    return 0;
}

E elegantă, dar lentă: pentru n mare recalculează la nesfârșit aceiași termeni mici. Versiunea iterativă păstrează doar ultimii doi termeni și construiește șirul o singură dată, de la mic la mare:

#include <iostream>
using namespace std;

long long fibIterativ(int n) {
    if (n < 2) return n;          // cazuri initiale
    long long a = 0, b = 1;       // a = F(0), b = F(1)
    for (int i = 2; i <= n; i++) {
        long long c = a + b;      // urmatorul termen = suma celor doi dinainte
        a = b;                    // gliseaza fereastra de doi termeni
        b = c;
    }
    return b;
}

int main() {
    cout << fibIterativ(7) << "\n";   // F(7)=13
    cout << fibIterativ(50) << "\n";  // F(50)=12586269025
    return 0;
}

Aceeași recurență, două traduceri: una urmează formula direct, cealaltă o desfășoară pas cu pas. Rezultat identic, viteză foarte diferită.

Complexitate

Diferența nu e cosmetică: pentru fibRecursiv(50) ai aștepta minute bune, în timp ce fibIterativ(50) răspunde instant. La factorial recursivitatea e ieftină (un singur apel pe pas, deci O(n)) — problema explozivă apare doar când recurența se ramifică, ca la Fibonacci.

Diagrama șirului

Primii opt termeni Fibonacci, cu indicele fiecăruia sub celulă. Urmărește cum celula evidențiată (F(7) = 13) este suma celor două dinaintea ei:

Recapitulare

• O relație de recurență exprimă termen(n) în funcție de termenii anteriori, plus cazurile inițiale care opresc lanțul.
• Aceeași recurență se poate traduce recursiv (urmează formula direct) sau iterativ (o desfășoară de la mic la mare); pentru Fibonacci, iterativul e O(n), recursivul naiv O(2^n).
• Atenție la cazurile inițiale, la ordinea calculului și la long long, pentru că termenii cresc repede.