# Șirul lui Fibonacci și calculul sumelor

> Pagina: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/fibonacci-si-sume
> Markdown: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/fibonacci-si-sume.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Algoritmi clasici de BAC](https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac)
Actualizat: 2026-09-22

Șirul definit recurent, varianta iterativă vs recursivă și sume cu termen general dat.

## Șirul lui Fibonacci

Definiție recurentă:
$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}$$

Primii termeni: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

## Iterativ sau recursiv

| | Iterativ | Recursiv naiv |
|---|---|---|
| Complexitate | $O(n)$ | $O(2^n)$ |
| Memorie | $O(1)$ | $O(n)$ pe stivă |
| F(40) | instantaneu | secunde bune |
| F(50) | instantaneu | practic imposibil |

Recursivitatea naivă recalculează aceiași termeni de nenumărate ori. Pentru $F(5)$ se fac 15 apeluri; pentru $F(40)$, peste 300 de milioane.

**La BAC**, dacă se cere doar valoarea, folosește varianta **iterativă**. Recursivitatea se cere când subiectul o indică explicit sau când trebuie urmărit arborele de apeluri.

## Atenție la depășire

$F_{47}$ depășește deja `int` pe 32 de biți. Peste $n = 46$, folosește `long long` (C/C++), `int64` (Pascal). În Python nu e problemă, întregii cresc oricât.

## Sume cu termen general dat

Tiparul e mereu același:

1. inițializezi acumulatorul cu **0** pentru sumă, cu **1** pentru produs;
2. parcurgi cu un contor;
3. adaugi (sau înmulțești) termenul general.

**Exemple**:
- $S = 1 + 2 + \ldots + n$, cu verificare: $n(n+1)/2$;
- $S = 1^2 + 2^2 + \ldots + n^2$, cu verificare: $n(n+1)(2n+1)/6$;
- $S = 1 + 1/2 + \ldots + 1/n$ (suma armonică), care cere tip real.

> [!RETINE]
> Inițializarea greșită a acumulatorului e una dintre cele mai frecvente greșeli: **0 la sumă, 1 la produs**. Dacă inițializezi produsul cu 0, rezultatul rămâne 0 orice ai face.

## Greșeli frecvente

1. Se pornește șirul cu $F_1 = 1, F_2 = 1$ când problema cere $F_0 = 0$. Citește cu atenție indexarea din enunț.
2. Se folosește recursivitatea naivă pentru $n$ mare și programul depășește timpul.
3. Se uită depășirea la $n > 46$.