Ciąg Fibonacciego opisujemy wzorem:
fib(n) = fib(n-2) + fib(n-1)
przy założeniu, że:
fib(1) = fib(2) = 1
Algorytm wyznaczania n-tego wyrazu tego ciągu będzie się składał z funkcji fib, która będzie otrzymywała jako parametr wyraz ciągu, który ma zwrócić. Funkcja sprawdzi, czy chodzi o pierwszy lub drugi wyraz (i wtedy zwróci 1), czy też należy wykonać rekurencyjnie samą siebie w następujący sposób:
fib(n) = fib(n-2) + fib(n-1)
Kompletny kod w języku C++ wygląda następująco:
#include <iostream>using namespace std;int fib(int n){switch (n){case 1:return 1;break;case 2:return 1;break;default:return fib(n-2) + fib(n-1);}}int main(){int wej;cout << "Ktory wyraz ciagu Fibonacciego podac?\n";cin >> wej;cout << fib(wej) << "\n";}