er, just don't recalculate the new number from the beginning in every frame.

use two local variables that store the last two values. new value = sum of previous 2. old old value becomes old value. old value becomes new value. repeat. O(1) rather than O(n).

Thanks for the swift replies, will try out your solutions.

One last question, when the nextFib() value exceeds the maximum integer size, what's the best way of resetting the f() values so the sequence can start again?

Quote:


No one has mentioned this so I will. Recursion is an extremely powerful technique but should be used with caution. When covering recursion the classic problem used to demonstrate when it can be used is the Factorial calculation. (The factorial of a positive integer is that number multiplied by every positive integer smaller than itself i.e. factorial 5 = 5 x 4 x 3 x 2 x 1

The classic problem to demonstrate when not to use recursion is the calculation of the Fibonacci sequence! The reason for this is not just the amount of memory used but the amount of duplicate calculations.

For instance the calculation of fib(7) would be

fib(7) = fib(6) + fib(5)
Calculating the first part:   fib(6) + fib(5)
the call to fib(6) would call fib(5) and fib(4)
the call to fib(5) would call fib(4) and fib(3)
the call to fib(4) would call fib(3) and fib(2)
etc.
Calculating the second part:  fib(6) + fib(5)
the call to fib(5) would call fib(4) and fib(3)
the call to fib(4) would call fib(3) and fib(2)
etc.
Notice the multiple calls to fib(4) and fib(3) this only gets worse with larger numbers.
In fact the calculation is of order O(eⁿ) i.e. exponential.

There are always iterative alternatives to recursion and they are shown in this thread but sometimes the easiest solution can be a simple lookup table.

The following code uses a lookup table and displays the next Fibonacci number in the sequence every second reseting when they get to big.

Hope this is of interest.

Code:

int[] fibs;
final int FIBLIMIT = 47; // 93;
int nextFib = 1;
long etime;
long ftime = 1000;

int nextFib(){
  if(nextFib >= FIBLIMIT)
    nextFib = 1;
  return fibs[nextFib++];
}

void makeFibs(){
  fibs = new int[FIBLIMIT];
  fibs[1] = fibs[2] = 1;
  for(int i = 3; i < FIBLIMIT; i++){
    fibs[i] = fibs[i-1] + fibs[i-2];
   }
  nextFib = 1;
}

void setup(){
  makeFibs();
  etime = millis();

}

void draw(){
  if(millis() - etime > ftime){
    println(""+nextFib());
    etime = millis();
  }
}