Base case & the call stack
In one line
A recursive function solves a problem by calling itself on a smaller input until it reaches a base case it can answer directly, and the call stack remembers every unfinished call along the way.
What it is
Recursion is when a function calls itself. Every correct recursive function has two parts: a base case, which is an input small enough to answer directly (like factorial(1) = 1), and a recursive case, which reduces the problem to a smaller version of itself (factorial(n) = n * factorial(n - 1)).
Each call gets its own stack frame holding its arguments, local variables and the place to resume. Frames pile up as calls go deeper and are removed as calls return. The maximum depth of that pile is the extra memory recursion uses, and if it grows too large the program crashes with a stack overflow (a RecursionError in Python, whose default limit is 1000 frames).
Why interviewers ask
Recursion is the backbone of tree and graph traversal, divide and conquer, backtracking and top-down dynamic programming. Interviewers check that you can state a clear base case, trust the recursive call to solve the smaller problem (the leap of faith), and reason about stack depth, since a missing base case or a depth of a million will crash the solution.
How it works
- 1Define what the function returns for an input, in one sentence. For list_sum(nums, i): the sum of nums from index i to the end.
- 2Write the base case first: the smallest input you can answer without recursion, such as i == len(nums) returning 0.
- 3Write the recursive case: do a little work and call the function on a strictly smaller input, such as nums[i] + list_sum(nums, i + 1).
- 4Check that every path makes progress toward the base case; otherwise the recursion never stops.
- 5When the base case returns, each waiting frame resumes in reverse order, finishes its own work and returns its result to the frame below.
Worked example · Tracing factorial(4) on the call stack
- factorial(4) is not a base case, so it needs 4 * factorial(3) and pauses. Stack: [f(4)].
- factorial(3) pauses waiting for factorial(2). Stack: [f(4), f(3)].
- factorial(2) pauses waiting for factorial(1). Stack: [f(4), f(3), f(2)].
- factorial(1) hits the base case and returns 1. Stack depth peaked at 4 frames.
- f(2) resumes: 2 * 1 = 2, returns. f(3) resumes: 3 * 2 = 6, returns. f(4) resumes: 4 * 6 = 24, returns. The stack is empty and the answer is 24.
Picture it
Recursion is like a stack of plates in a cafeteria where each plate holds a note saying what to do once the plate above is cleared. You keep adding plates (calls) until one note says 'done, the answer is 1', then you clear plates from the top, each one finishing its note using the answer from the plate above it.
Reference code
def factorial(n):
if n <= 1: # base case: stop here
return 1
return n * factorial(n - 1) # smaller copy of the same problem
def list_sum(nums, i=0):
if i == len(nums): # nothing left to add
return 0
return nums[i] + list_sum(nums, i + 1)
def power(x, n):
# x^n in O(log n) calls by halving n
if n == 0:
return 1
half = power(x, n // 2)
return half * half if n % 2 == 0 else half * half * x
print(factorial(5)) # 120
print(list_sum([3, 1, 4])) # 8
print(power(2, 10)) # 1024
import sys
print(sys.getrecursionlimit()) # 1000 by default in CPython
Each function states its base case first, then makes a call on a strictly smaller input. factorial and list_sum have depth n; power halves n each time, so its depth is only about log2(n).
Key patterns
Linear recursion
When: Processing a list or string one element at a time
How: Handle the first element, recurse on the rest. Depth is n, so prefer a loop in Python for large n.
Tree recursion
When: Trees, nested structures, file systems
How: Base case is an empty node or leaf; combine the results from each child.
Halving recursion
When: Fast power, binary search
How: Recurse on n // 2 so depth is only O(log n), as in power(x, n) using power(x, n // 2).
Accumulator parameter
When: You want to build a result while descending
How: Pass the partial result (a running total or path list) as an argument, and return it at the base case.
Real-world use
Parsers in compilers
Clang and the GCC C and C++ front ends use hand-written recursive descent parsers: a function to parse an expression calls the function to parse a term, which may call back into expression for parentheses, matching the nested grammar.
JSON parsing
Python's json module parses nested objects and arrays recursively, which is why json.loads on input nested thousands of levels deep raises a RecursionError instead of returning a result.
File system tools
Commands like rm -r and du walk a directory, then repeat the same work on each subdirectory, with an empty directory or a plain file as the base case.
UI component trees
Rendering a page means rendering a component, then its children, then theirs. React, Flutter and the browser DOM all describe UIs as trees that are naturally processed recursively.
In a project
Your team's commenting feature allows replies to replies, and the API must return a thread with its total reply count and maximum nesting depth so the app can collapse deep threads.
- Model each comment as a node with a list of child replies.
- Write count(comment) = 1 + sum of count(child) for each child, with a comment that has no replies as the base case.
- Write depth(comment) = 1 + max depth of its children, or 1 when there are none.
- Cap nesting at, say, 50 levels when replies are created, so the recursion depth on reads is bounded and can never hit the stack limit.
Impact: The logic is two short functions that match the shape of the data, making it easy to review and test. Bounding the depth turns a possible production crash from malicious deeply nested input into a clean validation error.
Trade-offs
Use it when
- The data is naturally nested: trees, graphs, JSON, file systems
- The problem splits into smaller copies of itself
- The recursive version is much clearer than managing a stack by hand
Avoid it when
- Depth can reach tens of thousands, such as recursing over a long list or linked list in Python
- A simple loop does the same job, as with sum or factorial in production code
- The same subproblems repeat many times without memoization
Cost: Time = number of calls times the work per call. Extra space = maximum recursion depth times the frame size, for example O(n) for factorial and O(log n) for fast power.
Common mistakes
- Missing or unreachable base case, causing infinite recursion and a stack overflow.
- Recursing on an input that is not smaller, such as calling f(n) from f(n).
- Forgetting to return the recursive result, so the function returns None in Python.
- Ignoring the stack: saying recursion uses O(1) space when it uses O(depth).
- Mutating a shared list during recursion without undoing the change when the call returns.
Interview questions
Quick revision
- Every recursion needs a base case and progress toward it.
- Write the base case first, then trust the smaller call.
- Each call = one stack frame; space = O(max depth).
- Python default recursion limit: 1000 (RecursionError).
- Halving the input gives O(log n) depth.
- Return the recursive result; do not just call it.
- Deep linear recursion in Python: use a loop instead.
Check yourself
1. What is the maximum stack depth when computing factorial(5) with the standard recursive definition (base case n <= 1)?
2. What is most likely wrong if a recursive function raises RecursionError on a small input?
3. How much extra space does power(x, n) use when it recurses on n // 2?
4. In list_sum(nums, i) = nums[i] + list_sum(nums, i + 1), what is the best base case?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.