Thread: 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.

Originally Posted by laserlight

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?

Originally Posted by laserlight

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?

Thanks laserlight.... that really helped

Originally Posted by stahta01

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.

Originally Posted by stahta01

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.

Originally Posted by oogabooga

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