Thread: fibonacci using recursion?

  1. #1
    Registered User n3cr0_l0rd's Avatar
    Join Date
    Feb 2009
    Posts
    62

    fibonacci using recursion?

    I know its not a good idea to generate fibonacci series using recursion technique...
    i can generate fibonacci series using loop but i cant do it using recursion...
    i dunno how to return many numbers in series... any help would be appreciated... i searched over the net and found how to do it but i couldnt understand...

    Code:
    int main(void)
    int fibonacci(int num);
    {
      printf("Enter the value of n : ");
      scanf("%d",&n);
      printf("%d  ",fibonacci[n]);
      getch();
      return (0);
    }
    
    int fibonacci(int number)
    {
      if ( ( number == 0 ) || ( number == 1 ) )
        return num;
      else 
        return fibonacci( num - 1 ) + fibonacci( num - 2 );
    }
    I had crush on her, before that crush could CRUSH me, i CRUSHED that crush !!! Fun time over, Lets find a way to not to blow off the whole leg !

    __________________________________________________ __________________________________________________ _______________

    In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg.
    - Bjarne Stroustrup

  2. #2
    Registered User n3cr0_l0rd's Avatar
    Join Date
    Feb 2009
    Posts
    62
    the above code was what i did after looking over the net....
    I had crush on her, before that crush could CRUSH me, i CRUSHED that crush !!! Fun time over, Lets find a way to not to blow off the whole leg !

    __________________________________________________ __________________________________________________ _______________

    In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg.
    - Bjarne Stroustrup

  3. #3
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    That's not exactly right, but very close.

    Your main doesn't have a body, so I'm guessing you haven't run that.
    It should work if you replace the first "fibonacci" function with main. Also in the second fibonacci function, you need to return "number", not "num" and pass "number" to the recursive calls.
    Other than that it looks OK to me.

    QuantumPete
    P.S. The only reason it's not a good idea to use recursion is because you're constantly re-calculating the same fibonacci numbers. You can improve the efficiency with some additional code, where you store previously calculated results and thereby short-cut 90% of recursive calls.
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  4. #4
    Registered User n3cr0_l0rd's Avatar
    Join Date
    Feb 2009
    Posts
    62
    oh that was all messed up ... i will correct them quickly and see if it works..
    I had crush on her, before that crush could CRUSH me, i CRUSHED that crush !!! Fun time over, Lets find a way to not to blow off the whole leg !

    __________________________________________________ __________________________________________________ _______________

    In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg.
    - Bjarne Stroustrup

  5. #5
    Registered User n3cr0_l0rd's Avatar
    Join Date
    Feb 2009
    Posts
    62
    Code:
    #include <stdio.h>
    #include <conio.h>
    int fibonacci(int number);
    int main(void)
    {
      int n;
      printf("Enter the value of n : ");
      scanf("%d",&n);
      printf("%d  ",fibonacci[n]); 
      getch();
      return (0);
    }
    
    int fibonacci(int number)
    {
      if ( ( number == 0 ) || ( number == 1 ) )
        return number;
      else
        return fibonacci( number - 1 ) + fibonacci( number - 2 );
    }
    thats what i have done now...
    Error: subscripted value is neither array nor pointer|


    edit : and one more question, do i need to put the line 9 inside a loop?

    edit 2:
    Code:
    for(i=0;i<n;i++)
        printf("%d  ",fibonacci(i);
    now i get error : syntax error before ';' token|

    edit 3:
    lol... minor misses and the i was getting errors... all fixed thx..
    Code:
    for(i=0;i<n;i++)
        printf("%d  ",fibonacci(i));
    Last edited by n3cr0_l0rd; 02-25-2009 at 06:45 AM.
    I had crush on her, before that crush could CRUSH me, i CRUSHED that crush !!! Fun time over, Lets find a way to not to blow off the whole leg !

    __________________________________________________ __________________________________________________ _______________

    In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg.
    - Bjarne Stroustrup

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    In case the OP went for breakfast and really can't spot this:
    Code:
      printf("%d  ",fibonacci(n));
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User n3cr0_l0rd's Avatar
    Join Date
    Feb 2009
    Posts
    62
    i already spotted that and corrected it.. but that was very silly of me! btw, what is OP???
    I had crush on her, before that crush could CRUSH me, i CRUSHED that crush !!! Fun time over, Lets find a way to not to blow off the whole leg !

    __________________________________________________ __________________________________________________ _______________

    In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg.
    - Bjarne Stroustrup

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by n3cr0_l0rd View Post
    what is OP???
    Original Post or
    Original Poster

    In this kind of recursion each member of the sequence is calculated at least twice
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Ps.
    I know its not a good idea to generate fibonacci series using recursion technique...
    Maybe not -- recursion is not as efficient as iteration.

    BUT I thought the fibonacci sequence trip was interesting to do via recursion, it's probably the most straightforward way to demonstrate what recursive branching is.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by MK27 View Post
    Maybe not -- recursion is not as efficient as iteration.
    Depends on how it's implemented:

    Code:
    typedef unsigned long long ull;
    
    ull fib_t (int num, ull * precalc) {
        if (num == 0) {
            return 0;
        }
        if (num <= 2) {
            return 1;
        }
        if (precalc[num] == 0) {
            precalc[num] =  fib_t(num-1, precalc) + fib_t (num-2, precalc);
            /* printf ("%d = %llu\n", num, precalc[num]); */
        }
        return precalc[num];
    }
    
    int main (int argc, char ** argv) {
        int num = 0;
        ull * table = NULL; 
        if (argc != 2) {
            printf ("You must specifiy a number\n");
            return 1;
        }
    
        num = atoi (argv[1]);
        table = calloc (num+1, sizeof (ull));
        if (table == NULL) {
            printf ("malloc failed!\n");
            return 1;
        }
    
        printf ("Fibonacci Number for %d = %llu\n", num, fib_t(num, table));
        free (table);
        return 0;
    }
    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Depends on how it's implemented
    I think that will be a tough sell on the fib sequence tho. I was just looking at my old code for doing this iteratively:
    Code:
    #include <stdio.h>
    
    int main () {
    	int a=0, b=1, n=a+b,i,ii;
    	puts("Number of iterations");
    	scanf("%d",&ii);
    	printf("%d %d ",a,b);
    	for (i=0;i<ii;i++) {
    		n=a+b;
    		printf("%d ",n);
    		a=b;b=n;
    	}
    }
    Which the output is from another angle than the OP, however.

    Of course recursion will always be more fun!
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by QuantumPete
    Depends on how it's implemented:
    Memoisation for the recursive version takes up space proportional to the size of the input, at least in the implementations I have seen, and your implementation is no different. We could have an iterative version that has the same space requirements, but the typical iterative equivalent is already memoised with constant space consumption, and does not have the overhead of recursion.

    On the other hand, I recall a Fibonacci formula (other than the constant time formula that some dismiss as mere estimation) that would be more easily implemented recursively, and the resulting algorithm is more efficient than the naive algorithm, whether it is implemented iteratively or recursively.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    On the other hand, I recall a Fibonacci formula (other than the constant time formula that some dismiss as mere estimation) that would be more easily implemented recursively, and the resulting algorithm is more efficient than the naive algorithm, whether it is implemented iteratively or recursively.
    You're such a tease.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

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. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  3. Fibonacci series using recursion
    By IPCHU in forum C Programming
    Replies: 1
    Last Post: 12-07-2006, 06:05 AM
  4. Fibonacci using Recursion
    By jazzistoobad in forum C Programming
    Replies: 21
    Last Post: 10-04-2004, 11:06 PM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM