Recursion: Functions That Call Themselves
Lesson 4 of 5 · View course roadmap
Learn the idea
A recursive function solves a problem by solving a smaller copy of the same problem. Every correct one has exactly two parts:
- Base case — an input so small the answer is immediate:
if n < 10: return n - Recursive step — shrink the input and delegate:
return n % 10 + digit_sum(n // 10)
The mental model: trust the recursive call. Don't trace every level — assume digit_sum(198) already works, and just add the last digit. If the base case is right and each step genuinely shrinks the input, the whole thing is right.
Recursion is the natural language of nested things: folders inside folders, JSON inside JSON, comments replying to comments.
Where you'll use this
File-tree walkers, JSON serialisers, comment threads, org charts, compilers — anything nested is naturally recursive. os.walk and json.dumps are recursion you already use.
Common mistakes
- No reachable base case → RecursionError at ~1000 frames.
- Forgetting
returnon the recursive call:digit_sum(n // 10)computes the value and throws it away — you needreturn n % 10 + digit_sum(...). - Recursing on the same input instead of a smaller one — shrinkage is what guarantees termination.
Pro tip
Trust the recursive call. Verify the base case, verify one step, and stop mentally unrolling five levels — that discipline is what makes recursion easy.
Try it yourself
The lesson example is loaded and ready — press Run, then change something and run it again. Breaking it is part of learning. Want a clean slate? Tap “New blank”.
Output appears here…
Pass the challenge +40 XP
Write a recursive digit_sum(n) that adds up the digits of a non-negative number (digit_sum(1984) → 1+9+8+4 = 22). Print digit_sum(1984) and digit_sum(7).
22 7
n % 10 is the last digit; n // 10 is the number without it. Base case: if n < 10: return n.
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
print(digit_sum(1984))
print(digit_sum(7))
Run your code to check it…
Check your understanding
Your notes (saved on this device)
Tip: use ← and → to move between lessons, ⌘K to search everything.