Recursion

Big idea

A recursive function calls itself on a smaller version of the problem, until it reaches a case so small it can answer directly — the base case.

The idea

The factorial of n, written n!, is n × (n-1) × … × 1. Notice that 5! = 5 × 4!. The problem contains a smaller copy of itself:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(1))

output
120
1

Every recursive function has two parts:

1. Base case — if n <= 1: return 1. Stops the recursion.
2. Recursive case — n * factorial(n - 1). Makes the problem smaller and calls itself.

What actually happens

Each call waits for the one it made. Python keeps the waiting calls on the call stack:

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

3
2
1
Go!

No base case, no end

def sum_to(n):
    return n + sum_to(n - 1)

print(sum_to(4))

output
10

Without a base case the calls never stop, and Python gives up with RecursionError: maximum recursion depth exceeded (about 1000 calls deep). Add if n == 0: return 0 at the top.

Recursion vs loops

Anything recursive can be written with a loop, and in Python a loop is usually faster and has no depth limit. Recursion wins when the problem is naturally self-similar — folders inside folders, trees, splitting a list in half again and again. You'll meet plenty of those in the DSA track.

Watch it

Think of it like

Russian nesting dolls. To find the smallest doll, open a doll — which is the same problem again, just smaller — until you reach one that doesn't open. That's the base case.

Key terms

• Recursion — A function calling itself.
• Base case — The case answered directly, which stops the recursion.
• Call stack — Python's record of the calls still waiting for an answer.