Program liczy wyraz na n-tej pozycji w ciągu Fibonacciego, a także liczbę wywołań rekurencyjnych funkcji. Widać, że np. już przy liczeniu 50 wyrazu program drastycznie zwalnia z obliczeniami przez dużą liczbę wywołań rekurencyjnych.

Projekt uruchamiany pod Visual Studio 2008.



// ciag_fibonacciego.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

//=========================================================
int suma;
int fib(int n) {
int liczba;

if(n==0) {
liczba = 0;
} else if(n==1) {
liczba = 1;
} else {
liczba = fib(n-1)+fib(n-2);
}

//cout<<liczba<<", ";

suma += liczba;
return liczba;
}

//=========================================================
int wywolan;

int fibonacci(int n) {
wywolan++;
int fib;
if(n==0) {
fib=0;
} else if(n==1) {
fib=1;
} else {
fib=fibonacci(n-1)+fibonacci(n-2);
}
return fib;
}

//=========================================================

int _tmain(int argc, _TCHAR* argv[])
{
//fib(4);
//cout<<"nsuma: "<<suma;

int n;
cout<<"Podaj liczbe: ";
cin>>n;
cout<<"nfib("<<n<<") = "<<fibonacci(n);
cout<<"nwywolan: "<<wywolan;

cout<<"nn";
system("pause");
return 0;
}