AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumrecursioncounting

~105s

Counting recursive calls

The naive recursion fib(n) = fib(n − 1) + fib(n − 2), with fib(0) and fib(1) returned directly, is used to compute fib(5). How many calls to fib are made in total, including the first one?

Show the answer and the worked solution

Correct answer: C.

15

Worked solution

  1. Let T(n) be the total number of calls. T(0) = T(1) = 1, since those return without recursing.
  2. Otherwise T(n) = 1 + T(n − 1) + T(n − 2), counting the call itself.
  3. T(2) = 1 + 1 + 1 = 3 and T(3) = 1 + 3 + 1 = 5.
  4. T(4) = 1 + 5 + 3 = 9.
  5. T(5) = 1 + 9 + 5 = 15.

Answer: 15.

The idea

The call count is 2·fib(n + 1) − 1, so it grows exponentially — the standard argument for memoising the recursion or rewriting it as a loop.

Shortcut. Every non-base call has exactly two children, so calls = 2 × leaves − 1; the leaves are the fib(1) and fib(0) calls, fib(6) = 8 of them, giving 15.

Common trap. 8 counts only the base-case calls at the leaves of the call tree and forgets the 7 internal calls that spawned them.

Data Structures & Algorithms

39 of 40

Level

Medium

Target time

~105s

PreviousNext
AI InterviewGet started

Counting recursive calls — Aptitude Question

Counting recursive calls: The naive recursion fib(n) = fib(n − 1) + fib(n − 2), with fib(0) and fib(1) returned… Answer and worked solution on CodeKairo.

Question

The naive recursion fib(n) = fib(n − 1) + fib(n − 2), with fib(0) and fib(1) returned directly, is used to compute fib(5). How many calls to fib are made in total, including the first one?

Options

  1. 8
  2. 9
  3. 15
  4. 25
Show the answer and the worked solution

Correct answer: C. 15

Worked solution

  1. Let T(n) be the total number of calls. T(0) = T(1) = 1, since those return without recursing.
  2. Otherwise T(n) = 1 + T(n − 1) + T(n − 2), counting the call itself.
  3. T(2) = 1 + 1 + 1 = 3 and T(3) = 1 + 3 + 1 = 5.
  4. T(4) = 1 + 5 + 3 = 9.
  5. T(5) = 1 + 9 + 5 = 15.

Answer: 15.

The idea

The call count is 2·fib(n + 1) − 1, so it grows exponentially — the standard argument for memoising the recursion or rewriting it as a loop.

Shortcut. Every non-base call has exactly two children, so calls = 2 × leaves − 1; the leaves are the fib(1) and fib(0) calls, fib(6) = 8 of them, giving 15.

Common trap. 8 counts only the base-case calls at the leaves of the call tree and forgets the 7 internal calls that spawned them.

All Data Structures & Algorithms questions · placement mock tests