De ce contează?
Fiecare domino dintr-un lanț cade pentru că cel dinainte l-a împins. Dacă știi starea ultimelor 1–2 piese, poți prezice exact ce urmează. Asta e esența unui șir recurent: fiecare termen este calculat din câțiva predecesori după o regulă fixă — fără formulă directă, pas cu pas.
Ce este o recurență?
O recurență este o regulă care exprimă termenul a[n] în funcție de câțiva termeni anteriori. Spre deosebire de un șir aritmetic sau geometric, nu există o formulă directă pentru termenul n — trebuie să calculezi pas cu pas, pornind de la valorile inițiale.
Ordin 1 (depinde de un singur predecesor):
a[n] = a[n-1] * 2, cu a[0] = 1:
| a | 1 | 2 | 4 | 8 | 16 | 32 |
| n | 0 | 1 | 2 | 3 | 4 | 5 |
Ordin 2 (depinde de doi predecesori — ca Fibonacci):
a[n] = a[n-1] + a[n-2] + 1, cu a[0] = 1, a[1] = 2:
| a | 1 | 2 | 4 | 7 | 12 | 20 |
| n | 0 | 1 | 2 | 3 | 4 | 5 |
a | b |
Algoritmul general
// Ordin k: a[n] depinde de a[n-1], ..., a[n-k]
// Stocam toti termenii intr-un vector
a[0] = valoare_initiala_0;
a[1] = valoare_initiala_1; // daca ordin >= 2
// ...
for (int i = k; i < n; i++) {
a[i] = f(a[i-1], a[i-2], ...); // aplica regula
}Implementare C++ — recurență de ordin 2
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long a[1000];
a[0] = 1;
a[1] = 2;
for (int i = 2; i < n; i++) {
a[i] = a[i-1] + a[i-2] + 1; // regula sirului
}
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}Exemplu: Input 6 → 1 2 4 7 12 20
Recurență de ordin 1 — fără vector
Dacă termenul depinde doar de precedentul, nu ai nevoie de vector:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long termen = 1; // a[0] = 1
for (int i = 0; i < n; i++) {
cout << termen << " ";
termen = termen * 2 + i; // regula: a[i+1] = 2*a[i] + i
}
cout << endl;
return 0;
}Un șir recurent de ordin k are nevoie de exact k valori inițiale. Fibonacci este de ordin 2: ai nevoie de F(0) și F(1). Un șir de ordin 3 — de exemplu tribonacci, a[n] = a[n-1] + a[n-2] + a[n-3] — are nevoie de a[0], a[1], a[2]. Fără toate valorile inițiale, șirul nu poate fi generat.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Ordin 1 (2 variabile) | O(n) | O(1) |
| Ordin k (vector) | O(n) | O(n) |
Greșeala 1: Accesezi a[i-2] când i = 0 sau i = 1. Bucla trebuie să înceapă de la indexul k (ordinul recurenței), nu de la 0.
Greșeala 2: Uiți câte valori inițiale are nevoie recurența. Un șir de ordin 2 cu o singură valoare inițială va accesa a[-1] — comportament nedefinit.
Greșeala 3: Overflow silențios la recurențe care cresc rapid. Un șir de tipul a[n] = a[n-1]^2 explodează după câțiva pași. Verifică ce tip de date e necesar pentru n-ul maxim din problemă.