Not the exercise, just the two parts every recursive function has. Read it as "to count down from n, say n, then count down from n - 1".
def countdown(n):
if n == 0: # the base case: nothing left, stop
print("lift off")
return
print(n)
countdown(n - 1) # the same job, one step smaller
countdown(3)
# 3
# 2
# 1
# lift off
- A base case that does not recurse
When n is 0 the function answers directly. Without that, it would call itself forever, and Python stops it with a RecursionError after about a thousand calls.
- Each call gets a smaller problem
countdown(3) hands countdown(2) the rest of the work. Every call is a step closer to the base case, which is the guarantee that it ends.
- Trust the smaller call
When you write countdown(n - 1), assume it works. You do not trace every level in your head; you check the base case and one step, and the rest follows.
Look at one element at a time. If it is not a list, it goes straight into the result. If it is a list, flattening it is the same job you are already doing, only smaller.
Build a result list. For each element: isinstance(element, list) decides which of the two things to do. For a list, call flatten on it and add everything it returns.
result = []; loop; if it is a list, result.extend(flatten(element)); otherwise result.append(element); return result. The base case is hidden in plain sight: a list with no nested lists never recurses.
def flatten(items): result = [] for element in items: if isinstance(element, ____): result.extend(____(element)) else: result.____(element) return result
def flatten(items):
result = []
for element in items:
if isinstance(element, list):
result.extend(flatten(element))
else:
result.append(element)
return result
There is no `if not items: return []` at the top, and there does not need to be. A list whose elements are all plain values never calls flatten again, and an empty list skips the loop entirely. The recursion stops on its own.
flatten(element) returns a list. append would put that whole list in as one item and undo the work; extend adds its items one by one.
The tempting test is "can I loop over it?", but strings pass that test and would be split into characters, and each character is itself a one-character string, which recursion would split again forever. Saying exactly which type nests is what keeps this safe.
Python stops recursing at about a thousand levels deep. Real data nested that deep is rare, but data built by a program can be, and there a loop with your own stack (a list you push inner lists onto) does the same job with no limit. For one level only, [x for sub in items for x in sub] is shorter and says so.
- Flatten without recursion, using a list as a stack of work still to do, and keep the order the same.
- Add a depth argument so flatten(items, depth=1) only unpacks one level, the way numpy’s and JavaScript’s versions do.
- Count how deep the deepest list goes, with the same shape of function.