Recursion & Nested Playlists
Tunebox lets people put playlists inside playlists. "Road Trip" holds "Morning" and "Night", "Night" holds "Late", and nobody promised it stops there. One loop handles one level; two nested loops handle two. A recursive function handles any depth — it deals with one level and hands every sub-playlist to itself.
Two cases: stop, or shrink
Every recursive function has two parts:
- a base case — an input small enough to answer directly, with no further call;
- a recursive case — do a little work, then call the same function on a smaller input.
The smaller call has to move toward the base case. Leave the base case out and nothing ever stops it:
def tracks_left(n):
return 1 + tracks_left(n - 1)
print(tracks_left(3))The call stack
Each call gets its own frame — its own private n — and the caller waits
on the line that made the call. Frames pile onto the call stack on the way
down and come off it, one at a time, on the way back up.
Step through it. factorial(3) can't finish 3 * … until factorial(2)
returns, and that waits on factorial(1). Only the base case returns without
waiting — then the answers flow back up: 1, then 2 * 1, then 3 * 2.
That also means code placed after the recursive call runs on the way back up:
def echo(n):
if n == 0:
return
print(n, end=" ")
echo(n - 1)
print(n, end=" ")
echo(3)❓ Cross-question — "Why doesn't
factorial(2)overwrite thenthatfactorial(3)is still using?" Every call has its own local variables in its own frame. Thenin one frame and thenin the next are different variables that share a name — exactly why two ordinary calls to any function never clash.
Depth, and Python's limit
Recursion depth is how many frames are on the stack at once. Python caps it — 1000 by default — so a runaway fails with a clear error instead of crashing.
Python also has no tail-call optimisation: even a call that is the very last thing a function does still costs a frame. So recursion that goes one level deeper per item — walking a 10,000-track list one track at a time — will hit the limit. Recursion that goes one level deeper per level of nesting won't: nobody nests playlists a thousand deep.
Coming from Java/JS: Java throws
StackOverflowError, JS throwsRangeError: Maximum call stack size exceeded. Same idea — but Python's limit is deliberately low.sys.setrecursionlimit()can raise it; needing to is usually a sign the problem wanted a loop.
Tree-shaped recursion
A nested playlist is a tree. Every item is either a title (a leaf) or a sub-playlist (a branch). The function answers leaves directly and hands branches to itself:
Where's the base case? There is no if for it. A playlist of plain titles makes
no recursive call, so its loop just ends and returns — the base case is hiding
in the shape of the data.
Some recursions branch into two calls every time, and the work explodes:
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(5)
print(calls)Flattening is the same walk, collecting titles instead of counting them. This version is one word away from right:
This should print one flat list of four titles. It prints the sub-playlist as a list nested inside the result.
Recursion vs iteration
Anything recursion does, a loop can do — with an explicit stack standing in for the call stack:
| the problem is… | reach for |
|---|---|
| a straight line — count down, walk a list | a loop |
| branching or nested — playlists, folders, JSON, trees | recursion |
| nested and possibly very deep (input you don't control) | a loop with an explicit stack |
❓ Cross-question — "Isn't recursion slower?" A little — each call pays for a frame. That overhead is rarely what matters. What matters is the shape of the work, and that's what the table below counts.
| function | time | extra space |
|---|---|---|
countdown(n), factorial(n) |
O(n) | O(n) — n frames |
naive fib(n) |
O(2ⁿ) | O(n) — the deepest chain |
count_tracks(playlist) |
O(t) — every item once | O(d) — d = nesting depth |
flatten with extend |
O(t · d) worst case — each level copies titles up | O(t + d) |
Idioms & real-world patterns
Pass the result down instead of copying it up
out.extend(flatten(item)) copies each title once per level it climbs. A helper
that appends into one shared list does no copying at all:
Don't recurse on slices
plays[1:] builds a brand-new list, so plays[0] + total(plays[1:]) is O(n²)
and n frames deep. Pass an index instead — or admit it's a loop:
⚡ Advanced — recursive generators with yield from
A generator can recurse too. yield from passes along everything the inner call
yields, so titles stream out without building a list at every level:
⚡ Advanced — remember answers with lru_cache
Naive fib recomputes the same calls again and again. functools.lru_cache
stores each result the first time, turning O(2ⁿ) into O(n) — the first step
toward dynamic programming:
🎯 Your turn
Write flatten_playlist(node). A playlist is a list whose items are titles
(strings) or nested playlists (lists), to any depth. Return one flat list of
titles in play order:
flatten_playlist(["a", ["b", "c"], "d"])→["a", "b", "c", "d"]flatten_playlist([])→[]
Hint — loop the items: a list means recurse and extend, anything else is a
title to append.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅