Like Tree1Likes

Print fiibonacci series using recursion(print in recursive function,do not use loops)

This is a discussion on Print fiibonacci series using recursion(print in recursive function,do not use loops) within the C Programming forums, part of the General Programming Boards category; I am required to print the fibonacci series using a recursive function int fib(int n) where n is the number ...

  1. #1
    Registered User
    Join Date
    Jun 2012
    Posts
    25

    Print fiibonacci series using recursion(print in recursive function,do not use loops)

    I am required to print the fibonacci series using a recursive function
    int fib(int n) where n is the number of elements in the series.I pass this through main.And i am not allowed to use any loops in main,such as
    Code:
    int b=0;
    for(c=0;c<n;c++)
    {
        b=fib(n);
        printf("%d",b);
    }
    I am supposed to print the elements of the series in the recurssive function itself.And i should print only the elements of the series and nothing else.I have tried a program and it works fine.But is there a much simpler code than this.Also,any tips for improving my coding style is abolutely welcome.This is my code
    Code:
    #include<stdio.h>
    static int r=0;
    int fib(int n);
    int main(void)
    {
        int n=0;
        printf("enter the number of elements");
        scanf("%d",&n);
        fib(n);
    }
    int fib(int n)
    {
    
    
        int p=0;
        if(n<0)
        {
            printf("enter a number greater than 0");
            return -1;
        }
        if(n==1)
        {
            if(r==0)
            {
                printf("%d\n",0);
                r++;
                return 0;
            }
            else
            {
                return 0;
            }
        }
        else if(n==2)
        {
            if(r==1)
            {
                printf("%d\n",1);
                r++;
                return 1;
            }
            else
            {
                return 1;
            }
    
    
        }
        else if(n%2==1)
        {
            if(n>r)
            {
                p=fib(n-2)+fib(n-1);
                printf("%d\n",p);
                r=n;
                return p;
            }
            else
            {
                p=fib(n-2)+fib(n-1);
                return p;
            }
    
    
        }
        else if(n%2==0)
        {
            if(n>r)
            {
                p=fib(n-1)+fib(n-2);
                printf("%d\n",p);
                r=n;
                return p;
            }
            else
            {
                p=fib(n-1)+fib(n-2);
                return p;
            }
    
    
    
    
            }
            return 0;
        }
    Thanks.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    There are only something like 47 such numbers that can fit into a 32-bit int. So, one way is to pre-compute them, then use just recursion to loop over the array elements

    Of course, your instructor will probably call this "cheating". A similiar but less "cheating" approach would be to use the array to do memoisation, then you use recursion both to loop over the array elements and to compute the next element's value. However, this might require the use of a helper function.
    dmh2000 likes this.
    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

  3. #3
    Registered User
    Join Date
    Jun 2012
    Posts
    25
    Quote Originally Posted by laserlight View Post
    There are only something like 47 such numbers that can fit into a 32-bit int. So, one way is to pre-compute them, then use just recursion to loop over the array elements

    Of course, your instructor will probably call this "cheating". A similiar but less "cheating" approach would be to use the array to do memoisation, then you use recursion both to loop over the array elements and to compute the next element's value. However, this might require the use of a helper function.
    I'm sorry,but im fairly new to programming in c.What do you mean by looping over the array elements?Could you explain with an example,if it's ok?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    Quote Originally Posted by Sylar Persie
    What do you mean by looping over the array elements?
    Have you worked with arrays?
    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

  5. #5
    Registered User
    Join Date
    Jun 2012
    Posts
    25
    Quote Originally Posted by laserlight View Post
    Have you worked with arrays?

    Yes, I have.But I can't understand the idea of "using recursion to loop over array elements".What exactly is that?

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    Quote Originally Posted by Sylar Persie
    But I can't understand the idea of "using recursion to loop over array elements".What exactly is that
    For example:
    Code:
    #include <stdio.h>
    
    void print(int *numbers, int n)
    {
        if (n > 0)
        {
            printf("%d\n", *numbers);
            print(numbers + 1, n - 1);
        }
    }
    
    int main(void)
    {
        int numbers[] = {1, 2, 3};
        print(numbers, 3);
        return 0;
    }
    But this is just one way; there are other ways too, depending on your requirements. It is just a general idea of how you might use recursion to loop through a sequence.
    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

  7. #7
    Registered User
    Join Date
    Jun 2012
    Posts
    25
    Thanks laserlight.... that really helped

  8. #8
    Registered User
    Join Date
    May 2009
    Posts
    2,521
    Figured out the solution the teacher likely wants.

    I wrote two recursive functions.
    One had printf statement(s) in it; called fib.
    The other one did not; called fib_noprint.

    The one with printf statements called changed the following line
    Code:
    p=fib(n-1)+fib(n-2);
    to
    Code:
    p=fib(n-1)+fib_noprint(n-2);
    NOTE: That was one of many changes I did to your code.

    Tim S.

    PS: I hope this does not count as too much help.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  9. #9
    Registered User
    Join Date
    Jun 2012
    Posts
    25

    Unhappy

    Quote Originally Posted by stahta01 View Post
    Figured out the solution the teacher likely wants.

    I wrote two recursive functions.
    One had printf statement(s) in it; called fib.
    The other one did not; called fib_noprint.

    The one with printf statements called changed the following line
    Code:
    p=fib(n-1)+fib(n-2);
    to
    Code:
    p=fib(n-1)+fib_noprint(n-2);
    NOTE: That was one of many changes I did to your code.

    Tim S.

    PS: I hope this does not count as too much help.

    I thought of it first too,but he said that i must print it all within this single function int fib(int n) recursively.Nothing extra.

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    2,521
    Quote Originally Posted by Sylar Persie View Post
    I thought of it first too,but he said that i must print it all within this single function int fib(int n) recursively.Nothing extra.
    Did he tell you that you could not write a helper function?

    Because all the printing is done within the fib function.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Here's another possibility. However, it ignores the return value (i.e., it would work just as well with a void return), so it might also be considered "cheating".
    Code:
    #include <stdio.h>
    
    int fib(int n) {
        static int f1, f2; // last two fibs
        int old_f1;
    
        if (n <= 0) {
            f1 = 0;        // init static vars
            f2 = 1;
            return 0;
        }
    
        fib(n-1);          // stack up n calls
    
        printf("%d\n", f1);
    
        old_f1 = f1;       // calc next fibs
        f1 = f2;
        f2 = old_f1 + f2;
    
        return 0;
    }
    
    int main(void) {
        fib(5);
        putchar('\n');
        fib(10);
        return 0;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  12. #12
    Registered User
    Join Date
    Jun 2012
    Posts
    25
    Quote Originally Posted by stahta01 View Post
    Did he tell you that you could not write a helper function?

    Because all the printing is done within the fib function.

    Tim S.

    Yes..he said that we are not supposed to use them.

  13. #13
    Registered User
    Join Date
    Jun 2012
    Posts
    25
    Quote Originally Posted by oogabooga View Post
    Here's another possibility. However, it ignores the return value (i.e., it would work just as well with a void return), so it might also be considered "cheating".
    Code:
    #include <stdio.h>
    
    int fib(int n) {
        static int f1, f2; // last two fibs
        int old_f1;
    
        if (n <= 0) {
            f1 = 0;        // init static vars
            f2 = 1;
            return 0;
        }
    
        fib(n-1);          // stack up n calls
    
        printf("%d\n", f1);
    
        old_f1 = f1;       // calc next fibs
        f1 = f2;
        f2 = old_f1 + f2;
    
        return 0;
    }
    
    int main(void) {
        fib(5);
        putchar('\n');
        fib(10);
        return 0;
    }
    Thanks oogabooga...seems like this code might be the one he asked for

  14. #14
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Sylar Persie View Post
    Thanks oogabooga...seems like this code might be the one he asked for
    I doubt it, since (as I mentioned) the return value of fib is unused.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  15. #15
    Registered User
    Join Date
    May 2009
    Posts
    2,521
    I added this line of code to my fib function to turn off printing

    static int print = 1;

    No longer needs a helper function. I set print to zero before the fib(n-2) call.

    Tim S.

    Code:
    int fib(int n) {
        static int print = 1;
    
        int save_print = print;
    
        int result = 0;
    
        /* complex if statement removed */
    
        if (print == 1){
            printf("%d\n",result);
        }
        return result;
    }
    Some of the code inside my complex if statement.
    Code:
            print = 0;
            result = fib(n-2);
            print = save_print;
    Last edited by stahta01; 06-13-2012 at 12:57 PM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a program recursive print from 1 to 2^n
    By abbaskhan in forum C Programming
    Replies: 18
    Last Post: 01-11-2012, 07:06 AM
  2. Replies: 10
    Last Post: 02-19-2010, 06:50 PM
  3. Recursive print every time...
    By BobDole11 in forum C Programming
    Replies: 5
    Last Post: 10-27-2008, 12:42 AM
  4. print first and print last function
    By RawleyMacias in forum C Programming
    Replies: 6
    Last Post: 02-14-2002, 09:28 PM
  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