Generarea sirurilor recurente: Fibonacci, siruri cu pas

Un șir recurent este o listă de numere în care fiecare termen (începând de la un anumit punct) este calculat pe baza unuia sau mai multor termeni anteriori, folosind o formulă fixă numită relație de recurență. Cele mai simple exemple sunt șirul Fibonacci și șirurile cu pas constant (progresii aritmetice).

Șirul Fibonacci se definește astfel: primii doi termeni sunt 0 și 1 (sau 1 și 1, în funcție de convenție), iar fiecare termen următor este suma celor doi termeni precedenți. Formal: F(0)=0, F(1)=1, iar pentru n≥2: F(n)=F(n-1)+F(n-2). Astfel, șirul devine: 0,1,1,2,3,5,8,13,21,34,... Acest șir apare frecvent în natură (spirala melcului, aranjarea frunzelor) și în informatică (algoritmi recursivi, căutare binară).

Șirurile cu pas (sau progresii aritmetice) sunt mai simple: fiecare termen se obține adăugând o valoare fixă (pasul) la termenul anterior. De exemplu, dacă primul termen este a1=2 și pasul r=3, atunci șirul este: 2,5,8,11,14,... Relația de recurență este: a(n)=a(n-1)+r. Se poate calcula direct și termenul general: a(n)=a1+(n-1)*r.

Implementarea în programare se face de obicei prin bucle (for sau while) sau recursiv. Pentru Fibonacci iterativ: se inițializează primele două variabile, apoi se parcurge n-2 pași (dacă n>1) calculând următorul termen și actualizând cele două variabile. Pentru șirurile cu pas, se pornește de la valoarea inițială, iar în fiecare iterație se adună pasul.

Atenție la puncte importante: Indexarea termenilor (de la 0 sau de la 1) trebuie clarificată. De asemenea, pentru valori mari (n>40), recursivitatea simplă a lui Fibonacci devine extrem de ineficientă (complexitate exponențială), de aceea se preferă metoda iterativă sau programarea dinamică. Șirurile cu pas sunt liniare și nu au probleme de performanță.

În concluzie, generarea șirurilor recurente este un exercițiu fundamental de gândire algoritmică și de control al buclelor, pregătind elevii pentru teme mai avansate precum recurențe liniare, fractali sau algoritmi de optimizare.

Exemple

• Exemplul 1 (Fibonacci): Să se genereze și afișeze primii 10 termeni ai șirului Fibonacci. Rezolvare: Se inițializează a=0, b=1. Se afișează a, apoi b. Apoi pentru i de la 3 la 10: c=a+b; afișează c; a=b; b=c. Rezultat: 0,1,1,2,3,5,8,13,21,34.
• Exemplul 2 (Șir cu pas): Să se genereze primii 8 termeni ai unui șir care începe cu 7 și are pasul 4. Rezolvare: termen1=7; pentru i=2..8: termen=termen+4; afișează termenul. Rezultat: 7,11,15,19,23,27,31,35.
• Exemplul 3 (Fibonacci cu indexare de la 1): Să se calculeze al 6-lea termen Fibonacci (considerând F1=1, F2=1). Rezolvare: F1=1, F2=1, F3=2, F4=3, F5=5, F6=8. Răspuns: 8.

Concepte cheie: Șir recurent, Fibonacci, Relație de recurență, Termen general, Iterare vs. recursivitate