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")

  1. reverse("abc") waits on reverse("bc"), which waits on reverse("c"), which waits on reverse("").
  2. reverse("") returns "". Back up: reverse("c") returns "" + "c" = "c".
  3. 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.

reverse(s):
if s is empty: return ""
return reverse(s without its first letter) + first letter
each call waits on the stack until the one it made returns

See it run

The worked example, step by step, beside the Python. The highlighted line is the one running.

Step-by-step

s = "abc"

0a
1b
2c

call stack

reverse("abc")◀ top

Solution · Pythonline 4

def reverse(s):
if s == "": # nothing left: stop here
return ""
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")) # cba
show_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.

Practise it · before the Recursion problems

Reverse a string, recursively

Return s backwards. Solve it with : no loops and no built-in reverse.

Input s = "abc"

Output "cba"

Input s = ""

Output ""

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?