ZERO / HERO
Russian dolls

Recursion

The analogy

To count nested dolls you open one and ask the same question of what is inside: "how many dolls in there?" Eventually you open a doll that is solid — that is the base case, and the answers add back up on the way out. A problem that contains a smaller copy of itself is a recursive problem.

Visualizer

Dolls inside dolls

step 1 / 11
bottom

count(doll) on a set of nested dolls. Each call will ask the same question of a smaller doll.stack depth 0

def count(doll):
    if doll.inner is None:
        return 1                 # base case
    return 1 + count(doll.inner)

import sys
sys.getrecursionlimit()   # 1000 by default
# every pending call costs a stack frame
Check yourself

What stops a recursion?