Know this before you start: “Base case: where the calls stop”
The base case: where the calls stop
The is the input small enough to answer directly, without another call. Without one, or if you can't reach it, the calls never stop.
The idea
Every recursive function has two parts: the base case, answered on the spot, and the recursive case, which calls itself on something smaller.
Pick the smallest input that still makes sense: an empty string, 0, a missing tree . Then check that every recursive call heads toward it.
Write the base case first, at the top of the function. If you can't say what the smallest input returns, you don't understand the problem yet.
Worked example
How many 7s are in 7177?
- Base case: count(0) = 0, a number with no digits left has no 7s.
- count(7177): last digit 7 → 1 + count(717). count(717): 1 + count(71). count(71): last digit 1 → 0 + count(7).
- count(7): 1 + count(0) = 1 + 0. Back up: 1, 1, 2, 3. Answer 3.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
n = 7177
call stack
Solution · Pythonline 4
def count_sevens(n):if n == 0: # base case: no digits leftreturn 0last = 1 if n % 10 == 7 else 0return last + count_sevens(n // 10) # drop the last digit def factorial(n):if n <= 1: # 0! = 1! = 1return 1return n * factorial(n - 1) print(count_sevens(7177), count_sevens(0)) # 3 0print(factorial(5)) # 120Step 1 of 10· line 4
n = 7177: the last digit is 7, a 7 → 1. Then ask count_sevens(717) about the rest.
- match / answer
- just added
Here O(number of digits) calls. In general: (number of calls) × (work per call).
When you'll use it
- Every recursive function, every time: write it before anything else.
In the wild · Folders and JSON: Finding every file in a folder means listing the folder and doing the same for each folder inside it. Code that reads nested JSON walks it the same way.
Common mistakes
- A base case that's never reached: (-1) with only n == 0 as the base recurses forever.
- Answering 0 when the smallest case should be 1 (an empty product, the one way to climb zero stairs).