Informatică Programare
Probleme rezolvate cu sirul lui Fibonacci recursiv
Șirul lui Fibonacci recursiv este definit prin relația F(n) = F(n-1) + F(n-2), cu F(0) = 0 și F(1) = 1. Problemele rezolvate cu acest șir ilustrează aplicarea recursivității în C++, deși abordarea recursivă simplă este ineficientă pentru valori mari din cauza recalculărilor multiple.
Problema 1: Calculul termenului Fibonacci
- 1 Enunț Scrie o funcție recursivă care returnează al n-lea termen al șirului lui Fibonacci.
- 2 Rezolvare int fibonacci(int n) { if (n <= 1) return n; else return fibonacci(n-1) + fibonacci(n-2); }
- 3 Exemplu numeric Pentru n=5: fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5. Termenii: 0,1,1,2,3,5.
Problema 2: Afișarea primilor n termeni
- 1 Enunț Scrie un program care afișează primii n termeni ai șirului lui Fibonacci folosind o funcție recursivă.
- 2 Rezolvare Includeți #include <iostream>. Funcția fibonacci ca mai sus, apoi în main: for (int i=0; i<n; i++) std::cout << fibonacci(i) << " ";
- 3 Exemplu numeric Pentru n=6: programul afișează 0 1 1 2 3 5.
Pentru n mare, folosește memoizare sau iterație pentru a evita timpii mari de execuție ai recursivității simple.