Ad:

C++ Discussion Thread
Marked Solved
Views: 7935

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Oct 24th, 2007

fibonacci

Expand Post »

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:

C++ Syntax (Toggle Plain Text)
int fib ( int n )
{
    if ( n <= 1 )
        return 1 ;
    else
        return ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}
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?

Similar Threads

C++ Fibonacci program help in C++
I need help writing a program using Fibonacci sequence in C++
Help,Fibonacci numbers in VB.NET
Fibonacci number in C
Really Weird Error... Fibonacci Nums in C++

Duki

Reputation Points: 817

Solved Threads: 32

Nearly a Posting Virtuoso

Offline

1,474 posts
since Jun 2006

Permalink

Oct 24th, 2007

Re: fibonacci

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.

C++ Syntax (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 ;
}
#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 ;
}

Duki

Reputation Points: 817

Solved Threads: 32

Nearly a Posting Virtuoso

Offline

1,474 posts
since Jun 2006

Permalink

Oct 24th, 2007

Re: fibonacci

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?

C++ Syntax (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 ;
}
#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 ;
}

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Oct 24th, 2007

Re: fibonacci

>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:

C++ Syntax (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];
}
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.

Ptolemy

Reputation Points: 44

Solved Threads: 8

Junior Poster in Training

Offline

62 posts
since Oct 2007

Permalink

Oct 24th, 2007

Re: fibonacci

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:

C++ Syntax (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 ] ;
}

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

Duki

Reputation Points: 817

Solved Threads: 32

Nearly a Posting Virtuoso

Offline

1,474 posts
since Jun 2006

Permalink

Oct 24th, 2007

Re: fibonacci

Click to Expand / Collapse Quote 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:
C++ Syntax (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"

Duki

Reputation Points: 817

Solved Threads: 32

Nearly a Posting Virtuoso

Offline

1,474 posts
since Jun 2006

Permalink

Oct 25th, 2007

Re: fibonacci

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:

C++ Syntax (Toggle Plain Text)
int size = 5;
int arr[size];
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

vmanes

Reputation Points: 1268

Solved Threads: 228

Posting Virtuoso

Offline

1,895 posts
since Aug 2007

Permalink

Oct 25th, 2007

Re: fibonacci

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

(Toggle Plain Text)
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 ] ;
}
    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.

Duki

Reputation Points: 817

Solved Threads: 32

Nearly a Posting Virtuoso

Offline

1,474 posts
since Jun 2006

Permalink

Oct 25th, 2007

Re: fibonacci

>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:

C++ 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];
}

Ptolemy

Reputation Points: 44

Solved Threads: 8

Junior Poster in Training

Offline

62 posts
since Oct 2007

Permalink

Oct 25th, 2007

Re: fibonacci

> 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.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Page 1
2
Next

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Please Help Dynamic Memory Allocation.

Next Thread in C++ Forum Timeline: homework help

DaniWeb Message

Cancel Changes

User Name
Password