Recursive Fibonacci, some help needed

This is a discussion on Recursive Fibonacci, some help needed within the C Programming forums, part of the General Programming Boards category; Hey guys, This is a hmwk problem of mine that I've been caught up in for a while now.... I ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    8

    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. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Why wold there be any double's in your program - what's wrong with 'int'?
    '%d' is wrong for doubles anyway.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    [edit]
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    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. #5
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329
    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. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    2
    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. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    8
    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. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by IceDane View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by IceDane View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci prime
    By dbzx in forum C Programming
    Replies: 5
    Last Post: 04-17-2009, 11:13 AM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM
  5. Fibonacci series using a recursive function
    By Dargoth in forum C++ Programming
    Replies: 3
    Last Post: 02-04-2002, 11:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21