Know this before you start: “A function that calls itself, and the call stack”
Recursion and the call stack
A recursive function solves a problem by calling itself on a smaller piece. Each call waits on a until the one it made returns, then finishes its own work.
The idea
Recursion is trusting a smaller version of the same question: to reverse “abc”, reverse “bc” and put “a” at the end. You only write how one step turns a smaller answer into this one.
Every call gets its own copy of its variables and sits on the . The newest call is on top; when it returns, the call below picks up exactly where it left off.
So work written after the recursive call happens on the way back up, in reverse order. That's what makes reversing, and later tree , so short.
Worked example
reverse("abc")
- reverse("abc") waits on reverse("bc"), which waits on reverse("c"), which waits on reverse("").
- reverse("") returns "". Back up: reverse("c") returns "" + "c" = "c".
- reverse("bc") returns "c" + "b" = "cb"; reverse("abc") returns "cb" + "a" = "cba". Four calls deep, then unwound.
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
s = "abc"
call stack
Solution · Pythonline 4
def reverse(s):if s == "": # nothing left: stop herereturn ""return reverse(s[1:]) + s[0] # the rest reversed, then the first letter def show_stack(n, depth=0):print(" " * depth + f"call {n}")if n > 0:show_stack(n - 1, depth + 1)print(" " * depth + f"return {n}") # runs on the way back up print(reverse("abc")) # cbashow_stack(2)Step 1 of 8· line 4
reverse("abc") can't answer yet: it calls reverse("bc") and waits, holding on to "a".
- looking at now
- just added
- inside the window
n nested calls use stack space. Python stops at about 1,000 levels deep (RecursionError).
When you'll use it
- Anything defined in terms of a smaller copy of itself: trees, nested lists, divide and conquer, .
- When the loop version would need you to manage your own stack.
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
- Expecting work after the recursive call to run before it: it runs on the way back.
- Recursing a million levels deep in Python: use a loop or an explicit stack for long linear chains.