fibonacci using recursion?

This is a discussion on fibonacci using recursion? within the C Programming forums, part of the General Programming Boards category; I know its not a good idea to generate fibonacci series using recursion technique... i can generate fibonacci series using ...

  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 05: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
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  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
    21,990
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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, 08:45 PM
  3. Fibonacci series using recursion
    By IPCHU in forum C Programming
    Replies: 1
    Last Post: 12-07-2006, 05: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, 09:56 AM

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