1. #### Is this normal?

Code:
```#include <stdio.h>

#define MAXCHAR 256

long long fibonacci(int n);

void main(void)
{
int n = 0;
int x = 0;

//declaration variables
FILE *filename; //input filename handle
char *fname = NULL;
int n = 0; //used for prompting user for size of Fibonacci series
fname = (char *)malloc(MAXCHAR * sizeof(char)); //allocate memory for size of filename (char = 1 bit)

//
//prompt user for file name and continue to do so until a valid file name is given
printf("Enter file name: ");
scanf("%s", fname);

//filename is just the handle to that file. have to go through filename for IO operation
filename = fopen(fname, "w");

//promt user for size of Fibonacci series
printf("Enter the size of the Fibonacci series to calculate: ");
scanf("%d", &n);

//print series to cmd prompt
for (x; x <= n; x++)
printf("%lld ", fibonacci(x));

}

long long fibonacci(int n)
{
//special case
if (n == 0)
{
return 0;
}
//special case
else if (n == 2 || n == 1)
{
return 1;
}
//recursive algorithm to return sum of previous 2 numbers in series
else
{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}```
Obviously I haven't implemented my fprintf( ) yet, but just printing to cmd prompt, if i choose n = 45 or something, it starts to take a while to calculate and print the numbers haha. Is this my cpu working its *** off to come up with the numbers? Is this normal?

2. Well your recursive fibonacci function is horribly inefficient.

If you count how many times the function is called for working out each answer, it looks like this!
Code:
```fib(0)=0 (calls=1)
fib(1)=1 (calls=1)
fib(2)=1 (calls=1)
fib(3)=2 (calls=3)
fib(4)=3 (calls=5)
fib(5)=5 (calls=9)
fib(6)=8 (calls=15)
fib(7)=13 (calls=25)
fib(8)=21 (calls=41)
fib(9)=34 (calls=67)
fib(10)=55 (calls=109)
fib(11)=89 (calls=177)
fib(12)=144 (calls=287)
fib(13)=233 (calls=465)
fib(14)=377 (calls=753)
fib(15)=610 (calls=1219)
fib(16)=987 (calls=1973)
fib(17)=1597 (calls=3193)
fib(18)=2584 (calls=5167)
fib(19)=4181 (calls=8361)
fib(20)=6765 (calls=13529)```
Here is a very simple loop which is much more efficient.
Code:
```long long int f2(int n) {
long long int result = 0;
long long int previous = 1;
int i;
for ( i = 0 ; i < n ; i++ ) {
long long int next = result + previous;
previous = result;
result = next;
}
return result;
}```

> I haven't tried n = 3453456 yet because I'm downloading LoL and don't anything to crash...
You're only going to get up to about 90! before being hit with rounding errors.
3. haha thats really cool. how do you know how many times it's calling the function? a debugger?

and is recursion usually inefficient? or is it just this case? what makes it so inefficient?

~Tim
4. > how do you know how many times it's calling the function? a debugger?
A crude hack.
Code:
```int count = 0;
void foo ( ) {
count++;
}```
> and is recursion usually inefficient? or is it just this case? what makes it so inefficient?
This
return fibonacci(n - 1) + fibonacci(n - 2);

Which you could also write as
return n-1 + fibonacci(n - 2) + fibonacci(n - 2);

It's basically working out the entire answer twice (as you can see from the counts).

• b49P23TIvg disagrees : formula n-1 + fibonacci(n - 2) + fibonacci(n - 2); is incorrect
5. To speed up Fibonacci calculations use memoization---in other words, store the values as you compute them, when you need a term first look it up. If it's there you're done. If not, compute the term and stash it.

Salem's non-recursive f2 is quite good.

Don Knuth may have figured out still another method.

And, of course, there's the matrix multiplication method which runs in O(log(n)) time.

See tition's posts, or look up at mathworld, or in the online handbook of integer sequences.

In j, executable Iverson notation now available for Android and IPhone
Code:
```   mp    NB. matrix product
\$:~ :(+/ .*)

F     NB. (Fib(2) Fib(1)) ,: (Fib(1) Fib(0))
1 1
1 0

NB. The "anti-diagonal" is Fib(1), Fib(2), ........................................... Fib(16)
<"2 F mp^:(<16) F    NB. creeping solution
┌───┬───┬───┬───┬───┬────┬─────┬─────┬─────┬─────┬──────┬───────┬───────┬───────┬───────┬────────┐
│1 1│2 1│3 2│5 3│8 5│13 8│21 13│34 21│55 34│89 55│144 89│233 144│377 233│610 377│987 610│1597 987│
│1 0│1 1│2 1│3 2│5 3│ 8 5│13  8│21 13│34 21│55 34│ 89 55│144  89│233 144│377 233│610 377│ 987 610│
└───┴───┴───┴───┴───┴────┴─────┴─────┴─────┴─────┴──────┴───────┴───────┴───────┴───────┴────────┘
NB. The "anti-diagonal" is Fib(1), Fib(2), Fib(4), Fib(8), Fib(16) {see agreement with above}, Fib(32 = 2^5)
<"2 mp^:(<6) F       NB. high matrix powers
┌───┬───┬───┬─────┬────────┬───────────────┐
│1 1│2 1│5 3│34 21│1597 987│3524578 2178309│
│1 0│1 1│3 2│21 13│ 987 610│2178309 1346269│
└───┴───┴───┴─────┴────────┴───────────────┘```