Задача. Составить функцию для вычисления чисел Фибоначчи fi, которые задаются так:

1.  f0 = 0, f1 = 1.

2.   fi = fi-1 + fi-2  для i > 1.

Решение.

int Fib ( int n )

{

if ( n == 0 ) return 0;

if ( n == 1 ) return 1;

return Fib(n-1) + Fib(n-2);

}