Sams Teach Yourself C++ in 21 Days

More on Program Flow 197

7

25: if (n < 3)

26: return 1;

27:

28: for (n -= 3; n != 0; n--)

29: {

30: minusTwo = minusOne;

31: minusOne = answer;

32: answer = minusOne + minusTwo;

33: }

34:

35: return answer;

36: }

Which position? 4

3 is the 4th Fibonacci number.

Which position? 5

5 is the 5th Fibonacci number.

Which position? 20

6765 is the 20th Fibonacci number.

Which position? 100

3314859971 is the 100th Fibonacci number.

Listing 7.15 solves the Fibonacci series using iteration rather than recursion. This

approach is faster and uses less memory than the recursive solution.

On line 11, the user is asked for the position to check. The function fib()is called,

which evaluates the position. If the position is less than 3, the function returns the value

1. Starting with position 3, the function iterates using the following algorithm:

1. Establish the starting position: Fill variable answerwith 2,minusTwowith 1, and
   minusOnewith 1. Decrement the position by 3 because the first two numbers are
   handled by the starting position.


2. For every number, count up the Fibonacci series. This is done by
   a. Putting the value currently in minusOneinto minusTwo
   b. Putting the value currently in answerinto minusOne
   c. Adding minusOneand minusTwoand putting the sum in answer
   d. Decrementing n


3. When nreaches 0, return the answer.
   This is exactly how you would solve this problem with pencil and paper. If you were
   asked for the fifth Fibonacci number, you would write
   1, 1, 2,

OUTPUT

LISTING7.15 continued

ANALYSIS