ITPEC FE Subject B April 2024 Question 7

Topic: Math & Numbers

From the answer group below, select the correct combination of answers to be inserted into A and B in the program.

The Fibonacci sequence is a sequence in which each number is equal to the sum of the two preceding numbers. In this question, the sequence starts with 0 and 1. The first 10 values in the sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. For example, the 8-th number 13 is the sum of the two preceding numbers 5 and 8.

The function fibo takes an integer value n as the argument and returns the value at the n-th position. Here, n reflects the position of the number in the sequence, starting with 1 (one). When n is 9, the function returns 21.

[Program]
○ integer: fibo(integer: n)
if (A)
return n - 1
else
return B
endif

Answer group

OptionAB

Explanation

A: (n = 1) or (n = 2), B: fibo(n-1) + fibo(n-2) — the first two positions are returned directly as n − 1, and every later one is the sum of the two before it.

  • •The base branch returns n - 1, which is right for position 1 (0) and position 2 (1) only; position 3 would give 2 instead of 1. So A must catch exactly n = 1 and n = 2.
  • •From position 3 on, each number is the sum of the two preceding ones: B is fibo(n-1) + fibo(n-2).
  • •Every chain of calls ends at position 1 or 2: fibo(3) calls fibo(2) and fibo(1), so the recursion always stops.

Check: fibo(9) is fibo(8) + fibo(7) = 13 + 8 = 21, as the question states.

Answer (i)

Why not others:

  • •(c) — A n = 1 alone lets fibo(2) call fibo(0), which no base case catches, so the recursion runs on through negative n without end
  • •(d), (e) and (f) — A n > 1 inverts the test: every n from 2 up returns n − 1 directly (fibo(9) gives 8), and fibo(1) recurses into fibo(0) without end
  • •(a) and (g) — B fibo(n-1) + 1 adds 1 per step, so every position returns n − 1: fibo(4) gives 3 instead of 2, and fibo(9) gives 8
  • •(b) and (h) — B fibo(n-1) + n adds the position instead of a sequence value: fibo(9) gives 44 in (b) and 43 in (h)

Key rule: A recursion that looks back k steps needs k base cases, and the base-case test must hold exactly where the direct formula is valid.

Math & Numbers · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.