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

the above code was what i did after looking over the net....

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.

oh that was all messed up ... i will correct them quickly and see if it works..

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

In case the OP went for breakfast and really can't spot this:

Code:

  printf("%d  ",fibonacci(n));

i already spotted that and corrected it.. but that was very silly of me! btw, what is OP???

Originally Posted by n3cr0_l0rd

what is OP???

Original Post or
Original Poster

In this kind of recursion each member of the sequence is calculated at least twice

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.

Originally Posted by MK27

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

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!

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.

Originally Posted by laserlight

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.