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.

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.

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 Sylar Persie

What do you mean by looping over the array elements?

Have you worked with arrays?

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?

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.

Thanks laserlight.... that really helped

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.

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 Sylar Persie

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.

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;
}

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

Originally Posted by Sylar Persie

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.

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;