just a fibonacci algorithm, how do i print every number of fibonacci sequence without repeat every step?
Does recursive functions is a good use in any way? I know it is more legible, but there is a visible delay in this simple algorithm if i put n = 40, whereas the iterative way of doing it is instantaneous.
int fib(int n)
{
if (n == 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
return fib(n - 1) + fib(n - 2);
}
You can easily optimize the recursive solution by memoizing the already-computed values:
int fib(int n) {
static int cache[48] = {0}; // should be enough to hold all int fibs
if(n < 2) return n; // initial conditions
else if(cache[n]) return cache[n]; // a value already computed and memoized
else return cache[n] = fib(n - 1) + fib(n - 2); // the largest so far
}
Should speed up the computation by, uh, some factor.
fib taking too long at large argument valued.Imperative languages like C do not always map well to functional definitions of algorithms.
Non-recursive is generally faster because both the compiler and processor can more easily optimize/parallel'ize the execution and you're not wasting energy, needlessly pushing and popping the stack. Either way, all you need are the previous two fib values to calculate the next one:
void PrintNFibs(unsigned n)
{
size_t a = 1;
size_t b = 1;
size_t sum;
printf("0\n1\n1\n");
while ( n-- )
{
sum = a + b;
printf("%zu\n", sum);
a = b;
b = sum;
}
}
It's one thing to define an algorithm in terms of itself (recursion) and another to implement it efficiently in C. For something as simple as Fibonacci however, I would not use recursion, but here's one anyway:
void PrintNFibsR(unsigned n)
{
static size_t a = 0;
static size_t b = 1;
static size_t sum;
sum = a + b;
if ( a == 0 )
{
printf("0\n1\n");
}
printf("%zu\n", sum);
if ( n > 1 )
{
a = b;
b = sum;
PrintNFibsR(n - 1);
}
}
Notice that all we're really doing here is passing the loop counter. Wasteful but technically recursive, if not actually functional. The problem with writing C code that looks just like the recursive Fibonacci algorithm definition, is it burns energy and stack space for no good reason. The only way you can print the values in the correct order without calculating and storing each one of them in advance, is to alter the algorithm.
fib(40)once, but that means calculatingfib(39)once andfib(38)once. Calculatingfib(39)means calculatingfib(38)andfib(37)— so that's two lots offib(38)that will be calculated. Of course, each of those also calculatesfib(37)andfib(36), sofib(37)is calculated 3 times, and … it quickly builds up to a lot of recursive function calls, which is why the recursive solution takes more time than the iterative solution. No: (naïve) recursive Fibonacci sequence is a bad idea. A not-so-naive version stashes values as it goes.