Fibonacci Number
An easy Recursion interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Recursion
- Sheets
- 2
- Core for
- 11 roles
The problem
The Fibonacci sequence begins 0, 1, and every later term is the previous two added together: 0, 1, 1, 2, 3, 5, 8 and so on. Return the term at position n, counting the first 0 as position 0.
Example 1
- Input
- n = 4
- Output
- 3
- Why
- The sequence is 0, 1, 1, 2, 3, so F(4) = 3.
Example 2
- Input
- n = 10
- Output
- 55
- Why
- The 10th Fibonacci number is 55.
Constraints
- 0 <= n <= 30
How to think about it
Updated 2026-09-29A recurrence with two branches does not form a line; it forms an exponential binary tree where identical subproblems are solved repeatedly. To compute F(n), you do not need the full tree of past evaluations, only the boundary between the past and the future: the two most recent values.
Approaches, worst first
Naive recursive branching
time O(2^n) · space O(n)
Branch directly into F(n - 1) + F(n - 2) at every call. Demonstrates the recurrence cleanly, but duplicates subproblem solutions at an exponential rate as n grows.
Top-down memoization
time O(n) · space O(n)
Store computed Fibonacci numbers in a hash map or array keyed by n. Bounded to linear states, but retains recursion stack and table overhead.
Two-variable rollWrite this one
time O(n) · space O(1)
Start with 0 and 1, then repeatedly replace the pair with the second number and their sum. Walks from the bottom up using constant memory without recursion frames.
Where people lose marks · 2
- Missing the base case for n = 0. Returning 1 for both 0 and 1 shifts the entire sequence by one index, producing 1 instead of 0 for F(0).
- Assuming n >= 2 and initializing an array of fixed size 2 before bounds checking, which can crash or produce out-of-bounds reads when n = 0.
The theory behind it
Recursion — the ground this problem stands on. All Recursion problems
What Recursion is
Recursion is a nesting doll that opens to reveal an identical smaller doll inside. In programming, a function solves a substantial problem by delegating smaller versions of the exact same question to fresh invocations of itself. Each invocation operates on shrunken input until hitting an irreducible foundation called a base case, which returns an immediate answer and permits the waiting cascade to resolve backwards.
When to reach for it
Reach for recursion when a problem possesses self-similar subproblems, such as traversing branched tree structures, exploring graph pathways, or generating combinations. Phrases asking for all permutations, subset generation, exhaustive maze navigation, or hierarchical file system traversals signal recursive decomposition. It is natural whenever the answer to a large instance depends on assembling identical solutions for smaller subsets.
How the pattern works
Structure every recursive method around two mandatory stages: the termination stop and the shrinking recurrence. Write the base condition first so the function exits before attempting further execution. Next, trust the recursive call to return valid answers for smaller inputs without mentally unwinding every level at once. Pass accumulation state forward through parameters, or combine child return values on the ascent phase once deeper calls return.
More Recursion problems
Target Roles
Core requirement for 11 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .