Thread: Recursive Fibonacci, some help needed

1. Recursive Fibonacci, some help needed

Hey guys,

This is a hmwk problem of mine that I've been caught up in for a while now.... I need some suggestions to help me figure out what I'm missing, I'm sure it's a minor detail...

Just so I get everyone on the same page :

-This program needs to request from the user the 'x' number or Fibonacci numbers that need to be printed.

-Uses a recursive function to compute the fist 'x' fibonacci numbers

- Prints the first 'x' fibonacci numbers.

Here is what I have up to this point. (I HAVE looked at other examples on this site, but they differ from what I am trying to do... I do not like to blend other codes into mine, as it leads to confusion on my end, and I do want to know what the hell is going on. Any help would be great, thx guys.)

You will notice I have commented a while loop and index with question marks.... I really don't know if I need these or not, all I know it that i can't get my fibonacci functions to print out... (I am limiting the user to enter only the 1st 20 numbers)

I am pretty sure my function is correct, but my main function is screwy...

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

double fib(int num)
{
if(num<0) {
return 0;
}
else if(num==0) {
return 1;
}
else if(num<=20) {
return (fib(num-1)+fib(num-2));
}
else {
printf("The integer you gave is too large\n");
return 0;
}
}

int main()
{
double num;
/* ?? int index=0; ?? */

printf("Give an integer from 0 to 20:");
scanf("%d", &num);

/* ??? while(num>=0)
index++; 	??? */

printf("The first %d fibonacci numbers are:\n", num);
printf("fibonacci(%d) = %1.01f\n", num, fib(num));
}```

2. Why wold there be any double's in your program - what's wrong with 'int'?
'%d' is wrong for doubles anyway.

3. 
Why wold there be any double's in your program - what's wrong with 'int'?
Well, the 20th Fibonacci number could easily be outside the range of an int if an int was 16 bits, as is allowed by the standard. A long or an unsigned long would probably be able to handle it, though. [/edit]

I'm pretty sure that both the first and the second numbers in the Fibonacci sequence are defined as 1, but you only return 1 for num==0.

I think you need to put this code into a loop:
Code:
`printf("fibonacci(&#37;d) = %1.01f\n", num, fib(num));`
Say, a for loop that loops from 1 (or 0) to num, inclusive.

Oh and by the way, %1.01f is redundant. First of all, the '0' is useless there as far as I know. (It's only before the decimal place that it does anything.) Also, specifying 1 digit (before the decimal) is kind of useless. And you allow one digit to the right of the decimal place, whereas Fibonacci numbers are integers.

If you want to simply discard the fractional part of the number, use
Code:
`%.0f`
Also, num itself is a double, so don't try to use %d on it (as you did in the printf() and the scanf()). Use %f for the printf(), and %lf for the scanf(), for doubles. Note the lowercase 'L' in the scanf specifier.

4. Your method is completely flawed conceptually seen. Fib number n is equal to fib numbers n-1 + fib number n-2, not the two numbers below it added together.

Difference?

First few fib numbers:

1 1 2 3 5 8

8 = 5 + 3

Not 7 + 6.

Wikipedia has some info on it. Look it up - If I'm not wrong, they might actually have a recursive example. If not, well, there are ........loads on the web anyway. It's a popular way to teach recursion.

5. Okay, I'm not the C programming master, but would somethng like this work

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

unsigned long fib(unsigned n)
{
if (n > 2)
return (fib(n - 1) + fib(n - 2));
else
return 1;
}

int main(void)
{
int i=0;
int num;
unsigned long val;

printf("Give an integer from 0 to 20:");
if((scanf("&#37;d", &num))!=1)
printf("input error\n");
if(num > 20){
printf("outside of range\n");
return 0;
}
for(i=1; i<num+1; i++) {
val = fib(i);
printf("The fibonacci numbers are:%u\n", val);
}

return 0;
}```

6. Well, first of all I want to say "Hi" to all members at this community. Here is mine solution:

Code:
```int F(int n) {
if (n <= 1)
return 1;
else
return F(n-2) + F(n-1);
}```
F is function calculating fibonnaci number.

7. Thanks for the advise guys, I did get the program to run. I was not aware that I had a lot missing. Took me a couple hours of toying around with it, but it came out. Thanks again.

8. Originally Posted by IceDane
Your method is completely flawed conceptually seen. Fib number n is equal to fib numbers n-1 + fib number n-2, not the two numbers below it added together.

Difference?

First few fib numbers:

1 1 2 3 5 8

8 = 5 + 3

Not 7 + 6.
Read his code again. It does make resursive calls to fib to calculate it properly and does not simply add the two numbers less than it. It does however calculate a lots of fibonnaci numbers twice in the process.

Using doubles gives a little more range, but then it hides when you run into loss of precision and the inability to even represent whole numbers accurately. This leads to wrong answers that you don't know are wrong. At least with ints you'll overflow and go negative.

9. Originally Posted by IceDane
Your method is completely flawed conceptually seen. Fib number n is equal to fib numbers n-1 + fib number n-2, not the two numbers below it added together.
Which is not what the code is doing. The code, as far as computing Fibonacci numbers, is correct.