What is recursion and what is a base case? | Interview Question

Q: What is recursion and what is a base case?

**Target Audience:** Complete beginners preparing for coding interviews — you only need to know what a function is. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain words first, then tagged with `📌 Interview term:` so you also learn the exact vocabulary an interviewer expects. Every trace, count and error message on this page comes from running the Python code shown, and the **Verified** section quotes that output. ## 1. Why This Even Matters — A Story First You are sitting in a dark cinema and want to know which row you are in. You cannot see the row numbers, so you tap the person in front of you and ask, "Which row are you in?" They do not know either, so they ask the person in front of *them*. The question travels forward, row by row, until it reaches someone in the front row. They do not need to ask anyone: they *know* they are in row 1. Then the answers travel back. "Row 1" becomes "row 2" for the person behind, "row 3" f

The problem

Question presented to candidate: "What is recursion, and what is a base case? Write a small recursive function in Python — say factorial or the sum of a list — point to the base case, and tell me what happens if it is missing."

What a strong answer should cover:

Recursion: a function that solves a problem by calling itself on a smaller instance of the same problem.
The base case: the smallest input, answered directly without another call; the recursive case: reduces the problem and calls itself.
Every call must make progress toward the base case; a missing or unreachable base case recurses until the stack overflows.
The call stack: calls wind down to the base case, then results unwind back up; stack space is the maximum depth, time is the number of calls times the work per call.
Python specifics: a missing base case ends in RecursionError (default limit 1000), recursing on slices copies data, and functools.lru_cache memoises a recursion in one line.

Code / implementation expected: Yes — a short recursive Python function (factorial, sum, palindrome) with its base case, and its cost.

recursion

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Complete beginners preparing for coding interviews — you only need to know what a function is. Difficulty: Easy Language: Python 3

How to read this doc: Each idea is explained in plain words first, then tagged with 📌 Interview term: so you also learn the exact vocabulary an interviewer expects. Every trace, count and error message on this page comes from running the Python code shown, and the Verified section quotes that output.

1. Why This Even Matters — A Story First

You are sitting in a dark cinema and want to know which row you are in. You cannot see the row numbers, so you tap the person in front of you and ask, "Which row are you in?" They do not know either, so they ask the person in front of them. The question travels forward, row by row, until it reaches someone in the front row. They do not need to ask anyone: they know they a

The solution is hidden so you can try first

9 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTrace factorial(4): calls going down, returns coming back up

Practice

PythonFive small recursions, each with its base case

Practice

PythonBase-case bugs, and naive vs memoised Fibonacci

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.