Programming Basics (Pseudocode Tracing)
What does the following function fib return when called as fib(10)?
○integer: fib(integer: n)
integer: a ← 0, b ← 1, t
for (i from 1 to n step 1)
t ← a + b
a ← b
b ← t
endfor
return a- A34
- B55
- C89
Show answer and explanation
Answer: B. 55
Each pass advances (a, b) by one pair of adjacent Fibonacci numbers: (0, 1) → (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → (8, 13) → (13, 21) → (21, 34) → (34, 55) → (55, 89). After 10 passes the function returns a = 55. After the i-th pass, a is the i-th Fibonacci number. A naive recursive version computes the same values many times, but this one needs only n passes.
- A. This is the value with one pass fewer (final value n − 1).
- B. Correct. a = 55 after 10 passes.
- C. This is the value of b, the 11th Fibonacci number.
Continue: 9 more Programming Basics (Pseudocode Tracing) questions