fibonacci

[Duki]

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:

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?

[Duki]

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.

#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 ;
}

[vmanes]

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?

#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 ;
}

[Ptolemy]

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

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.

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

#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 ] ;
}

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

#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"

[vmanes]

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:

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

[Duki]

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

#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)?

[Ptolemy]

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

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

[Salem]

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

[Duki]

Oh, ok. so changing the array to static solved everything. It's still really slow, compared to this one:

#include <ctime>
#include <iostream>
using namespace std ;

int main ( )
{
    int n ;

    cout << "Enter number of elements:  " << flush ;
    cin >> n ;

    int * fibArray = new int[ n ] ;

    clock_t start ;
    clock_t end ;

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

    fibArray[ 0 ] = 1 ;
    fibArray[ 1 ] = 1 ;

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

    for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t" ;

    cout << endl ;

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

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

    cout << endl ;

    return 0 ;
}

But that was expected; we get extra credit for programming both and timing the two.
I'm still frustrated that I can't do static int fibArray [ n ] instead of 25, or some other constant value.

[Ptolemy]

>so changing the array to static solved everything.
No, changing the array to static and actually using the values you've cached solved everything. If you don't to the latter, your code won't be any faster than the usual recursive solution.

>It's still really slow, compared to this one
Your function might be slow, but mine is a hair faster in my tests than the code you're referring to. I've included a little test below.

>I'm still frustrated that I can't do static int fibArray [ n ]
>instead of 25, or some other constant value.
A better alternative is to pass a buffer to the function rather than use a static or global array. I've made that change in the test below.

#include <ctime>
#include <iostream>

using namespace std;

int fib ( int fibArray[], int n )
{
  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 ( fibArray, n - 1 )
        + ( fib ( fibArray, n - 2 ) ) );
    }
  }

  return fibArray[n];
}

int main()
{
  int n;

  cout << "Enter number of elements:  ";
  cin >> n;

  int * fibArray = new int[n];

  clock_t start;

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

  fibArray[ 0 ] = 1;
  fibArray[ 1 ] = 1;

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

  for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t";
  cout << '\n';

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

  // Reset the array so that previous results don't make fib faster
  for ( int i = 0; i < n; i++ )
    fibArray[i] = 0;

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

  for ( int j = 0 ; j < n ; j++ )
    cout << fib ( fibArray, j ) << "\t";
  cout << '\n';

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

  return 0;
}

[Duki]

Oh ok great. thanks for the help! It's working great!