1. Originally Posted by QuantumPete
I just tested it and though it should be an "<=" instead of just "<", it does work properly and returns immediately.

QuantumPete
Wow. You are correct (except the first number is 0...).

Using this loop to produce the first 45 (I think it wraps after that) did take more than a minute tho, whereas the iteritive one is instant:

Code:
```int main (int argc, char *argv[]) {

for (i=1;i<=atoi(argv[1]);i++) {
}
}```

2. Originally Posted by MK27
Using this loop to produce the first 45 (I think it wraps after that) did take more than a minute tho, whereas the iteritive one is instant:
Of course, my code only provides you with a final answer. It's not designed to print out all the fibonacci numbers along the way. That very much depends on the requirements for the program!

QuantumPete

3. I think we are ALL saying the same thing: don't use recursion alone to calculate fibonaccie sequences. If you only need the ONE value, then calculate it iteratively - it's almost instant for small and large n (at least as long as n is 32-bit integer). If you want a list of the first X numbers, then you will need to store the results as you go along into an array. I wrote a recursive array variant:
Code:
```#define SIZE 5000000

int fibarr[SIZE];
int maxn = -1;

int fib2(int n)
{
if (n <= maxn)
{
return fibarr[n];
}
if (n == 0)
return fibarr[0] = 0;

if (n <= 2)
{
fibarr[n] = 1;
return 1;
}
fibarr[n] = fib2(n-1) + fib2(n-2);
if (maxn < n)
maxn = n;

return fibarr[n];
}```
--
Mats

4. Originally Posted by QuantumPete
Of course, my code only provides you with a final answer.
Really it's useless, since you might as well use the iterative approach and just limit the output to the final loop (as matsp just noted).

But it's very clever -- I could not even have thought that one up, and am still staring at it and inserting printf's to figure out what's going on. My eyes tell me it should have either looped forever, or always returned 2.

5. Originally Posted by MK27
Really it's useless, since you might as well use the iterative approach and just limit the output to the final loop (as matsp just noted).
That's "useless" too, since you might as well use the formula

6. Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats

7. This is similar to what matsp posted, except it will take arbitrary numbers:
Code:
```typedef unsigned long long ull;

ull fib_t (int num, ull * precalc) {
if (num <= 2) {
return 1;
}
if (precalc[num] == 0) {
precalc[num] =  fib_t(num-1, precalc) + fib_t (num-2, precalc);
printf ("&#37;d = %llu\n", num, precalc[num]);
}
return precalc[num];
}

int main (int argc, char ** argv) {
int num = 0;
ull * table = 0;
if (argc != 2) {
printf ("You must specifiy a number\n");
return 1;
}

num = atoi (argv[1]);
table = calloc (num+1, sizeof (ull));
if (table == 0) {
printf ("malloc failed!\n");
return 1;
}

printf ("Fibonacci Number for %d = %llu\n", num, fib_t(num, table));
free (table);
return 0;
}```
It even prints out all the numbers as it computes them

QuantumPete

8. Originally Posted by MK27
But it's very clever -- I could not even have thought that one up, and am still staring at it and inserting printf's to figure out what's going on. My eyes tell me it should have either looped forever, or always returned 2.
Checking the Wikipedia entry on the Fibonacci numbers, I see that one can actually derive it directly from the recurrence relation presented there. I also recall that it was the introductory example of at least one algorithms textbook. Consequently, I suggest that you work through such a text to help you understand recursion better.

Originally Posted by matsp
Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...
Yes, I think so too.

9. Originally Posted by matsp
Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats
True, but why use an approximation, when a computed-table approach will get you the result almost as fast?

QuantumPete

10. Originally Posted by QuantumPete
True, but why use an approximation, when a computed-table approach will get you the result almost as fast?
If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.

11. Originally Posted by laserlight
If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.
But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?

QuantumPete

12. Originally Posted by QuantumPete
But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?
Mathematically, the formula is indeed another way to compute the nth number in the original Fibonacci series, but in practice, it is an approximation since we do not have infinite precision floating point arithmetic. On the other hand, the approximation can be accurate, since we are dealing with integers in the end.

13. Okay, I'm really busted by this one! Short of reading the recommended book, can anyone help explain it? I used the following

Code:
```#include <stdio.h>

int fib (int num) {
int x, y;
printf("fib: %d\n", num);
if (num <= 2) {
return 1;
}
x=fib(num-1); y=fib(num-2);
printf("x: %d y: %d\n", num);
fflush(stdout);
return x+y;
}

int main (int argc, char *argv[]) {

for (i=1;i<=atoi(argv[1]);i++) {
printf("\nto fib: %d\n", i);
}
}```
./a.out 3
to fib: 1
fib: 1

to fib: 2
fib: 2

to fib: 3
fib: 3
fib: 2
fib: 1
x: 3 y: 0

How does x end up as 3, y as 0, and the answer as 2?

14. Because your printf isn't being given the right data:
Code:
`printf("x: %d y: %d\n", num);`
If it's gcc, -Wall will tell you that you have one too few arguments, even if it is not telling you that num isn't x or y.

--
Mats

15. Yeah that was dumb. I'm staring at the real output now.