# Fibonacci is not doing the math properly

• (2 Pages)
• 1
• 2

## 19 Replies - 619 Views - Last Post: 01 March 2018 - 02:22 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=409418&amp;s=20a726f68895d3ad50c34c532e407eb4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 StudioUAC

Reputation: 0
• Posts: 14
• Joined: 23-September 16

## Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 04:54 PM

the recursive function, i'm keeping track how many time it's called. the non recursive function i'm keeping track how many times it loops.

### #17 Skydiver

• Code herder

Reputation: 6290
• Posts: 21,618
• Joined: 05-May 12

## Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 06:20 PM

This is the output I got with that main() from post #14.
```Non-recursive version
Fib(1) = 1 loops 2
Fib(2) = 1 loops 3
Fib(3) = 2 loops 4
Fib(4) = 3 loops 5
Fib(5) = 5 loops 6
Fib(6) = 8 loops 7
Fib(7) = 13 loops 8
Fib(8) = 21 loops 9
Fib(9) = 34 loops 10
Fib(10) = 55 loops 11
Fib(11) = 89 loops 12
Fib(12) = 144 loops 13
Fib(13) = 233 loops 14
Fib(14) = 377 loops 15
Fib(15) = 610 loops 16
Fib(16) = 987 loops 17
Fib(17) = 1597 loops 18
Fib(18) = 2584 loops 19
Fib(19) = 4181 loops 20
Fib(20) = 6765 loops 21

```

Are you sure that you are compiling and running the right code?

### #18 StudioUAC

Reputation: 0
• Posts: 14
• Joined: 23-September 16

## Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 08:55 PM

this is my latest code. i compiled it and ran it on cpp.sh

```#include <iostream>
#include <time.h>

using namespace std;

long Fib(int n, long& count);
long NonFib(int n, long& count);
void Timer();

const int US_TO_SEC = 1000000;
const int MAX_FIB = 20;

int main() {

long count;
int i;

cout << "Recursive version" << endl;
for(i=1;i<=MAX_FIB;i++)
{
count = 0;
long FibTemp = Fib(i, count);

//cout <<  "COUNT CHECK  " << count << endl << endl;

cout << "Fib(" << i << ") = " << FibTemp << " calls ";
cout << count << endl;

}

//Timer();

cout << endl << "Non-recursive version" << endl;

for(i=1;i<=MAX_FIB;i++)
{
count = 0;
long NonFibTemp = NonFib(i, count);

cout << "Fib(" << i << ") = " << NonFibTemp << " loops ";
cout << count << endl;
}

// Timer();

return 0;
}

//recursive fibonacci function
long Fib(int n, long& count) {
int returnValue;

if (n == 1 or n == 2) {
count++;
returnValue = 1;

}
else {
count++;
returnValue = Fib(n-1, count) + Fib(n-2, count);

}

//cout <<  " LONG FIB COUNT CHECK  " << count << endl << endl;

return returnValue;
}

//non recursive fibonacci function
long NonFib(int n, long& count)
{
long prev = 0;
long result = 1;
long sum;
int i;

for(i = 3; i <=n; i++)
{

sum = (result + prev);
prev = result;
result = sum;
count++;
}

return result;
}

void Timer(){

clock_t start, stop, time;
long count;

start = clock();
Fib(50,count);
stop = clock();
time = stop-start;
cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;

return;
}

```

this was my output

```Recursive version
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

Non-recursive version
Fib(1) = 1 loops 0
Fib(2) = 1 loops 0
Fib(3) = 1 loops 1
Fib(4) = 2 loops 2
Fib(5) = 3 loops 3
Fib(6) = 5 loops 4
Fib(7) = 8 loops 5
Fib(8) = 13 loops 6
Fib(9) = 21 loops 7
Fib(10) = 34 loops 8
Fib(11) = 55 loops 9
Fib(12) = 89 loops 10
Fib(13) = 144 loops 11
Fib(14) = 233 loops 12
Fib(15) = 377 loops 13
Fib(16) = 610 loops 14
Fib(17) = 987 loops 15
Fib(18) = 1597 loops 16
Fib(19) = 2584 loops 17
Fib(20) = 4181 loops 18

```

### #19 Skydiver

• Code herder

Reputation: 6290
• Posts: 21,618
• Joined: 05-May 12

## Re: Fibonacci is not doing the math properly

Posted 01 March 2018 - 10:26 AM

Looks like your iterative version is not computing the right Fibonacci number.

### #20 StudioUAC

Reputation: 0
• Posts: 14
• Joined: 23-September 16

## Re: Fibonacci is not doing the math properly

Posted 01 March 2018 - 02:22 PM

i got it to work now

i had to convert it with dos2unix and change the long prev = 0; to a 1