Does anybody know a fibonacci (recursive) function that doesn't become exponentially complex?

Question

I just need to know a way to generate fibonacci numbers other than using the old recursive method:
if(in==1||in==2)
return 1;
return fib(in-1)+fib(in-2);
Which exponentially "explodes" (16th fibbonacci number requires exactly 256 function calls)

Thank You!

Answer 1

unsigned int fibb_stright(unsigned int n) {
double phi = 0.5 + sqrt(1.25);

double appox = (pow(phi, n) / sqrt(5)) + 0.5;

return floor(appox);
}

unsigned int fibb_recurse(unsigned int n) {
if (n < 1) return 0;
else if (n == 1) return 1;
else {
unsigned int n1 = 0, n2 = 1;
unsigned int i, value;

for (i = 2; i <=n; ++i) {
value = n1 + n2;
n1 = n2;
n2 = value;
}
return value;
}
}

In my x64 machine, the return values match up to n = 48 when the stright implementation overflows.

The stright implementation is O(1), while the other one is O(n)

Answer 2

The standard recursive algorithm for Fibonacci numbers is tail-recursive, meaning that you can also do the computation in a loop and get O(n) rather than O(2^n) performance.

int n = ( whatever fib number you want )

int f1 = 1
int f2 = 1
int f3;

for ( int i = 3; i <= n; ++i ){
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}

cout << f3;

Answer 3

I imagine something like this would work (VB.NET)

Dim i, j, result As Integer
Dim last As Integer = 0
Dim last2 As Integer = 0
i = 15

For j = 1 To i
If j = 1 Then
result = 1
Else
result = last + last2
End If

last2 = last
last = result
Next