fibonacci

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 456,560 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 3,470 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Please support our C++ advertiser: Programming Forums

Thread Tools Display Modes

Views: 2573 | Replies: 12 | Solved

Page 1 of 2

•

Join Date: Jun 2006

Location: USA

Posts: 1,082

Reputation: Duki has a spectacular aura about

Rep Power: 7

Solved Threads: 4

Duki

Offline

Veteran Poster

fibonacci

Oct 24th, 2007

Hey guys,

I'm supposed to write a program that will calculate the Nth fibonacci number, without using recursion.

I have the recursion problem written already, but am having a hard time doing the iterative one.

here's my recursion function:

Help with Code Tags

(Toggle Plain Text)

int fib ( int n )
{
    if ( n <= 1 )
        return 1 ;
    else
        return ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}

any help with getting me started on the iterative one?

It is practically impossible to teach good programming style to students that have had prior exposure to Basic; as potential programmers they are mentally mutilated beyond hope of regeneration.

-Edsger Dijkstra

•

Join Date: Jun 2006

Location: USA

Posts: 1,082

Reputation: Duki has a spectacular aura about

Rep Power: 7

Solved Threads: 4

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

Nevermind, I got it working. Didn't think to use an array; well I thought about it, but didn't think it would make the problem easier. Here's my fibonacci sequence, written iteratively.

Help with Code Tags

(Toggle Plain Text)

#include <iostream>
using namespace std ;

int main ( )
{
    int fibArray[25] ; //max fib number
    fibArray[0] = 1 ;
    fibArray[1] = 1 ;

    for ( int i = 2 ; i < 25 ; i ++ )
        fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ] ;

    cout << fibArray[4] << "\t" << fibArray[7] << "\t" << fibArray[24] << endl ;

    return 0 ;
}

•

Join Date: Aug 2007

Location: South Dakota

Posts: 993

Reputation: vmanes is a jewel in the rough

Rep Power: 6

Solved Threads: 97

vmanes

Offline

Posting Shark

Re: fibonacci

Oct 24th, 2007

Your array based solution is limiting in that you have set the array size to the number of values to display.

What about a purely iterative solution, that does not need the excess memory, and is not logically limited in the number of values to display?

Help with Code Tags

(Toggle Plain Text)

#include <iostream>
using namespace std ;

int main ( )
{
    unsigned int fib ; //current fibonnaci value
    unsigned int n1 = 1 ;
    unsigned int n2 = 1 ;

    int max_fib;

     cout << "Enter number of term for Fibonacci series: " ;
     cin >> max_fib;

    cout << n1 << '\t' << n2 << '\t';

    for ( int i = 2 ; i < max_fib; i ++ )
	{
		fib = n1 + n2;
		n1 = n2;
		n2 = fib;
	        cout << fib <<  "\t" ;

		if( i % 5 == 0 )	//five numbers per line
			cout << endl;
	}

    return 0 ;
}

I am in mourning for my country.

•

Join Date: Oct 2007

Posts: 62

Reputation: Ptolemy is an unknown quantity at this point

Rep Power: 2

Solved Threads: 8

Ptolemy

Offline

Junior Poster in Training

Re: fibonacci

Oct 24th, 2007

>What about a purely iterative solution, that does not need the excess
>memory, and is not logically limited in the number of values to display?
That's fine for just printing the sequence. The array is more open to extension though. Let's say you want to write fib(x) where x is the number and the function returns $F^N$ . With the array you can do this:

Help with Code Tags

(Toggle Plain Text)

int fib ( int x )
{
  static const int max = 25;
  static int n = 2;
  static int fibArray[max] = {1,1};

  while ( n < x ) {
    fibArray[n] = fibArray[n - 1] + fibArray[n - 2];
    ++n;
  }

  return fibArray[x];
}

At the (minor, in this case) cost of extra storage, you avoid recalculating parts of the sequence that you've already calculated. That's the principle behind the dynamic recursive algorithm.

•

Join Date: Jun 2006

Location: USA

Posts: 1,082

Reputation: Duki has a spectacular aura about

Rep Power: 7

Solved Threads: 4

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

seeing as this is being discussed still, I would like to pose another question: How do I use an array using recursion? This will be more efficient, no? Here is my current code:

Help with Code Tags

(Toggle Plain Text)

#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
int i = fib ( 5 ) ;
cout << i << endl ;

return 0 ;
}

int fib ( int n )
{
int fibArray [ const n ] ;

if ( <= 1 )
return 1 ;
else
{
fibArray[ 0 ] = 1 ;
fibArray[ 1 ] = 1 ;

for ( int i = 2 ; i < 25 ; i++ )
fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}

return fibArray[ n ] ;
}

Last edited by Duki : Oct 24th, 2007 at 9:31 pm.

•

Join Date: Jun 2006

Location: USA

Posts: 1,082

Reputation: Duki has a spectacular aura about

Rep Power: 7

Solved Threads: 4

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

•

Originally Posted by Duki

seeing as this is being discussed still, I would like to pose another question: How do I use an array using recursion? This will be more efficient, no? Here is my current code:
Help with Code Tags

(Toggle Plain Text)
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
int i = fib ( 5 ) ;
cout << i << endl ;

return 0 ;
}

int fib ( int n )
{
int fibArray [ const n ] ;

if ( <= 1 )
return 1 ;
else
{
fibArray[ 0 ] = 1 ;
fibArray[ 1 ] = 1 ;

for ( int i = 2 ; i < 25 ; i++ )
fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}

return fibArray[ n ] ;
}
#include <iostream> using namespace std ; int fib ( int ) ; int main ( ) { int i = fib ( 5 ) ; cout << i << endl ; return 0 ; } int fib ( int n ) { int fibArray [ const n ] ; if ( <= 1 ) return 1 ; else { fibArray[ 0 ] = 1 ; fibArray[ 1 ] = 1 ; for ( int i = 2 ; i < 25 ; i++ ) fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ; } return fibArray[ n ] ; }

why can i not do int fibArray [ n ] ? It says "expected constant"

•

Join Date: Aug 2007

Location: South Dakota

Posts: 993

Reputation: vmanes is a jewel in the rough

Rep Power: 6

Solved Threads: 97

vmanes

Offline

Posting Shark

Re: fibonacci

Oct 25th, 2007

That's a compiler dependent problem now.

Previously, any declaration of a local array had to be done with a constant expression as the size. The latest C standard (C99) has changed that restriction, but not all compilers have adopted that. And remember, the C++ standard includes the C standard, more or less.

So, legally speaking:

Help with Code Tags

(Toggle Plain Text)

int size = 5;
int arr[size];

is now a legitimate construct. Current version of gcc supports this. Visual C++ does not.

Now I have to go change my lesson plans.....
Val

I am in mourning for my country.

•

Join Date: Jun 2006

Location: USA

Posts: 1,082

Reputation: Duki has a spectacular aura about

Rep Power: 7

Solved Threads: 4

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 25th, 2007

Ok, I got it to work using a pointer. Here's my code.

 Help with Code Tags 
(Toggle Plain Text)
 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <ctime>
#include <iostream>
using namespace std ;
 
int fib ( int ) ;
 
int main ( )
{
    clock_t start ;
    clock_t end ;
 
    cout << "Beginning timer..." << endl ;
    start = clock() ;
 
    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }
 
    cout << endl ;
 
    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;
 
    cout << "\n\n-- Done --\n\n" ;
 
    return 0 ;
}
 
int fib ( int n )
{
    int * fibArray = new int[ n ] ;
 
    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;
 
        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
 
    }
 
    return fibArray[ n ] ;
}
#include <ctime>
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
    clock_t start ;
    clock_t end ;

    cout << "Beginning timer..." << endl ;
    start = clock() ;

    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }

    cout << endl ;

    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;

    cout << "\n\n-- Done --\n\n" ;

    return 0 ;
}

int fib ( int n )
{
    int * fibArray = new int[ n ] ;

    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;

        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;

    }

    return fibArray[ n ] ;
}
   Help with Code Tags   c++ Syntax (Toggle Plain Text)    #include <ctime>#include <iostream>using namespace std ; int fib ( int ) ; int main ( ){    clock_t start ;    clock_t end ;     cout << "Beginning timer..." << endl ;    start = clock() ;     cout << endl ;    for ( int k = 0 ; k < 12 ; k++ )    {    int i = fib ( k ) ;    cout << i << "\t" ;    }     cout << endl ;     end = clock() ;    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;     cout << "\n\n-- Done --\n\n" ;     return 0 ;} int fib ( int n ){    int * fibArray = new int[ n ] ;     if ( n <= 1 )        return 1 ;    else    {        fibArray[ 0 ] = 1 ;        fibArray[ 1 ] = 1 ;         for ( int i = 2 ; i <= n ; i++ )        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;     }     return fibArray[ n ] ;} #include <ctime>
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
    clock_t start ;
    clock_t end ;

    cout << "Beginning timer..." << endl ;
    start = clock() ;

    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }

    cout << endl ;

    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;

    cout << "\n\n-- Done --\n\n" ;

    return 0 ;
}

int fib ( int n )
{
    int * fibArray = new int[ n ] ;

    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;

        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;

    }

    return fibArray[ n ] ;
}  

I can't get it to work with numbers >=12; it gives a system error that it failed unexpectedly. I'm guessing it's a stack issue, but is there a way around it? Is my program the best it can be (using recursion and arrays)?

Last edited by Duki : Oct 25th, 2007 at 1:44 am.

•

Join Date: Oct 2007

Posts: 62

Reputation: Ptolemy is an unknown quantity at this point

Rep Power: 2

Solved Threads: 8

Ptolemy

Offline

Junior Poster in Training

Re: fibonacci

Oct 25th, 2007

>And remember, the C++ standard includes the C standard, more or less.
Standard C++ currently maintains compatibility with C89, not C99. So you can't use VLAs in C++

>Is my program the best it can be (using recursion and arrays)?
No. The entire point of using an array with recursion is to avoid recalculating everything all the time. This is especially true with the Fibonacci sequence, where a lot of the numbers have to be recalculated. You use an array, but you don't take advantage of it, so your function is just a slower, more wasteful version of the original recursive algorithm.

What you need is for the array to persist between function calls and be able to tell if a number has been calculated or not. If it has, you don't need to go through the recursive chain. This is where you'll see performance improvements:

 Help with Code Tags 
 cplusplus Syntax (Toggle Plain Text) 
int fib ( int n )
{
  static int fibArray[25] = {0};
 
  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;
 
    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) );
    }
  }
 
  return fibArray[n];
}
int fib ( int n )
{
  static int fibArray[25] = {0};

  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;

    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) );
    }
  }

  return fibArray[n];
}

•

Join Date: Dec 2005

Posts: 3,834

Reputation: Salem has much to be proud of

Rep Power: 23

Solved Threads: 436

Salem

Offline

banned

Re: fibonacci

#10

Oct 25th, 2007

> I can't get it to work with numbers >=12; it gives a system error that it failed unexpectedly.
1. You don't free the memory you allocate. Eventually, you'll run out of memory.

2. You run off the end of the memory allocated.
for ( int i = 2 ; i <= n ; i++ )
If you want <= n, then you need to allocate n+1 items.
It was always wrong, you just got caught with your hand in the cookie jar at n >= 12.

3. Unlike Ptolemy's answer, your array serves no purpose.