Zdecyduj czy Twój ciąg rozpoczyna się od (0, 1, ....) czy od (1, 1,...). W obu funkcjach masz różnie. Najczęściej wybierana jest wersja z (0, 1, ...).
fib2(..) można bez problemu napisać bez użycia jakiejkolwiek tablicy. Spada wtedy zużycie pamięci. Jeśli chodzi o fib(...), poprawiłem go dla ciągu (0, 1, ...).
#include <stdio.h>
#include <time.h>
long int fib(int n) /* rekurencyjna */
{
return n < 2 ? n: fib(n - 1) + fib(n - 2);
}
long int fib2(int n) /* iteracyjna */
{
int x0 = 0;
int x1 = 1;
for(int i = 0; i < n; ++i) {
int temp = x0 + x1;
x0 = x1;
x1 = temp;
}
return x0;
}
void checkTime(long int (*func)(int), int arg) {
clock_t startTime = clock();
func(arg);
clock_t stopTime = clock();
printf("Czas wykonania funkcji to %.2f ms.\n",
1000.0 * (stopTime - startTime) / CLOCKS_PER_SEC);
}
int main(void) {
puts("Dla wersji rekurencyjnej:");
checkTime(fib, 45);
puts("Dla wersji iteracyjnej:");
checkTime(fib2, 45);
return 0;
}
Oczywiście pomiar tylko jednego wykonania nie jest miarodajny. Ale do celów ćwiczebnych i przy takich różnicach czasów akceptowalny :-)