Bitkernel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Interviewed for a software engineering role at Bitkernel and got hit with a recursive function tracing question. Not the most complex thing in the world but I definitely fumbled the execution a bit.

Questions Asked (1)

Given a recursive function where x(n) returns 1 if n <= 3, otherwise returns x(n-2) + x(n-4) + 1, how many total calls to x are made when computing x(8), counting the initial call?

Algorithms & Data Structures

Author's notes

I started tracing the call tree on paper which was the right move, but I kept losing track of branches halfway through.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Draw the recursion tree for x(8), expanding each call until reaching base cases (n <= 3). Count every node in the tree, including the initial call, to get the total number of calls. Alternatively, use memoization to avoid redundant counting, but for this small n, manual counting is straightforward.

Pro tip: Mention that without memoization, the number of calls grows exponentially, but for n=8 it's manageable. Also, note that the base cases are n=1,2,3, and for n<=0 the function is not defined, so ensure you only consider valid inputs.

1. Understand the recurrence

Identify that x(n) returns 1 for n <= 3, and for n > 3, it recursively calls x(n-2) and x(n-4) and adds 1. This means each non-base call spawns two recursive calls.

2. Draw the recursion tree

Start with x(8) as the root. For each node with n > 3, create two children: x(n-2) and x(n-4). Continue until all leaves are base cases (n <= 3).

3. Count the nodes

Count every node in the tree, including the root. Each node represents one call to x. Sum them up to get the total number of calls.

4. Verify with memoization (optional)

If time permits, compute the number of unique calls using memoization and compare. This helps confirm the total count and shows awareness of optimization.

Key Points to Mention

Base case: x(n) = 1 for n <= 3, so no further recursion.
Recursive case: x(n) = x(n-2) + x(n-4) + 1 for n > 3.
The recursion tree for x(8) has multiple overlapping subproblems (e.g., x(4) appears multiple times).
Total calls include the initial call to x(8).
Without memoization, the number of calls grows exponentially with n.
For n=8, the total number of calls is 15 (as computed by summing nodes in the tree).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.