Trace Algorithm X

Scenario. Algorithm X calculates a Fibonacci number. In this exercise, the sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.

Inputs. number, a non-negative whole number. Other values are invalid.

Rules and notation. The procedure must output F(number) under the supplied definition.

Assumptions. Arithmetic can represent the result for the supplied input.

Listing 1 makes the structure for trace algorithm x explicit so you can identify its required fields and boundaries.

Listing 1: Structured example of trace algorithm x.

IF number is not a non-negative whole number
    OUTPUT Invalid input
ELSE IF number <= 1
    OUTPUT number
ELSE
    SET a TO 0
    SET b TO 1
    SET i TO 2

    WHILE i <= number
        SET next TO a + b
        SET a TO b
        SET b TO next
        SET i TO i + 1
    END WHILE

    OUTPUT b
END IF

Deliverable. Trace a, b, next, and i for number = 6. Give expected outputs for 0, 1, 2, and 6. Explain what a and b represent after each completed iteration.

Success criteria. The output for 6 is F(6) under the supplied definition, both base cases avoid the loop, the first iteration produces F(2), and the stated meaning of the variables agrees with every trace row.

TipHint

After the iteration labeled i, b contains F(i) and a contains F(i - 1).