EvenFlow

10-29-2001, 07:03 AM

I was fooling around with a fibonacci program whereby a recursive call is used.

#include <stdio.h>

long fibonacci(long);

int main (void)

{

long result, number;

printf("Fibonacci Program\n\n");

printf("Enter an integer please: ");

scanf("%d", &number);

result = fibonacci(number);

printf("Fibonacci %ld = %ld\n", number, result);

return 0;

}

long fibonacci(long n)

{

if (n == 0 || n == 1)

return n;

else

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

}

This program does its job for any integer from 1 - 26, without slowing down. The number of recursive calls that get executed to calculate the nth fibonacci number is on the order of 2n. Say you entered 20 - this would require 220 calls (about a million or so).

Interestingly enough, I ran this on one of the computers at university (1GHz Pentiums). Entering in 40 it still took quite some time to process (at least 10-12 seconds by my count).

I guess it is easy to see that even though most modern CPUs are incredibly fast, it is interesting to see that no matter how fast they are, a program such as this (or any that isn't optimised) still runs slowly. Hence my point - optimising code is still important and shouldn't be neglected.

#include <stdio.h>

long fibonacci(long);

int main (void)

{

long result, number;

printf("Fibonacci Program\n\n");

printf("Enter an integer please: ");

scanf("%d", &number);

result = fibonacci(number);

printf("Fibonacci %ld = %ld\n", number, result);

return 0;

}

long fibonacci(long n)

{

if (n == 0 || n == 1)

return n;

else

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

}

This program does its job for any integer from 1 - 26, without slowing down. The number of recursive calls that get executed to calculate the nth fibonacci number is on the order of 2n. Say you entered 20 - this would require 220 calls (about a million or so).

Interestingly enough, I ran this on one of the computers at university (1GHz Pentiums). Entering in 40 it still took quite some time to process (at least 10-12 seconds by my count).

I guess it is easy to see that even though most modern CPUs are incredibly fast, it is interesting to see that no matter how fast they are, a program such as this (or any that isn't optimised) still runs slowly. Hence my point - optimising code is still important and shouldn't be neglected.