recursion to iteration

[Willie7772]

i was wondering if you guys could point me in the right direction for changing this loop to an iterative statement


for( int i=0; i<40; i++ )
{
a[i] = getFibonacciNumber( i );

}

i'm assuming that an iterative statement will make it run faster...

[jpeg]

nvm, misunderstood the question.

[helios]

Um...
A loop is iterative.

Do you mean how to make the function iterative?

[Willie7772]

yea, im just looking for a way to make the function go quicker than using a for loop, i know how to put it together with if statements, but i dont want 40 if statements...

[helios]

Well, how about posting the function, then? I can't just guess what it looks like.
Okay, I can. But I won't.

[Willie7772]

im sending u a private message

[helios]

Don't send PMs needlessly. PMs can't be searched so other people won't be compelled to not ask the same question.

long getFibonacciNumber( long n )
{
	// expect that n is a positive number.
	assert( n >= 0 );

	// Base Case: where n < 2, i.e. 0 and 1, we return the first two numbers in 
	// the sequence.
	if( n < 2 )
		return n;

	// Inductive Step: if we know the two preceding numbers (n-1 and n-2) in the 
	// sequence, then we can use them to compute the n'th number. 
	return getFibonacciNumber( n - 1 ) + getFibonacciNumber( n - 2 );
}

getFibonacciNumber() is incorrect. The first two numbers in the series are 1 and 1, not 1 and 2.
Don't use an assert() for that. IIRC, assert()s are removed once a certain #declared constant is un#declared. Possibly _DEBUG.

To make the function iterative, you'll need three variables: one stores fib[i], another stores fib[i-1], and yet another stores fib[i-2].

You should now have enough information to do it.

[Willie7772]

the code i gave you works, but it takes a few seconds to complete,im looking for a way to do it instantly...

[helios]

Oh, I read that as n<=2. My bad.

I already gave you the information you need to do it. It's just a matter of using the variables as though they were a fixed size queue.

[Duthomhas]

A loop is iterative.

Exactly what I was going to say (but FF crashed --yeah, wow-- and I've only now come back)

The only time it makes a difference is with unpruned trees.

If your F(n) function is purely functional, then you are recursing 2F(n+1)-2 times... (a big, honking, unpruned binary tree).

From what it looks like you want to do an iterative generator:

unsigned long generate_fibonaccis( int n, unsigned long results[ 48 ] )
  {
  if (n > 47) throw "n is too big (without bignums)".

  results[ 0 ] = 0;  // F(0) --> 0
  results[ 1 ] = 1;  // F(1) --> 1

  // F(x) --> F(x-1) + F(x-2)
  for (int x = ?; x ? n; x++)
    results[ x ] = ? ? ?;

  return results[ n ];
  }

You will have to fill-in the question marks.

Hope this helps.

[edit] I suppose I really ought to learn to use that "refresh" button...
[edit] http://c.comsci.us/examples/fibonacci/

[Willie7772]

you guys still have me at a loss here