Recursion

Recursion means solving a problem by solving smaller copies of the same problem. A recursive function calls itself with a smaller input until it reaches a case so simple that the answer is obvious. Trees, graphs, sorting, backtracking and dynamic programming in this course are all easier to understand once recursion feels natural.

If you have never written a recursive function, read Recursion in the Python course first. This lesson focuses on what DSA needs: tracing the call stack, drawing recursion trees to find the running time, the divide and conquer idea, and what to do when recursion gets too deep.

The two parts of every recursive function

Every correct recursive function has:

1. A base case: an input small enough to answer directly, without another call.
2. A recursive case: break the input into a smaller piece, call the function on it, and combine the result.

The useful mindset is to trust the recursive call. When you write factorial(n - 1), assume it returns the right answer, and only ask: "if I had that answer, how do I finish the job for n?"

Watching the call stack

Each call gets its own frame on the call stack (see Stacks). A frame stays until its call returns, so the calls finish in reverse order. This version prints with indentation so you can see the stack grow and shrink:

def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:                                   # base case
        print(f"{pad}factorial({n}) returns 1")
        return 1
    result = n * factorial(n - 1, depth + 1)     # recursive case
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Four frames were on the stack at the deepest point. Factorial does O(1) work per call and makes n calls, so it takes O(n) time and O(n) space for the stack.

Recursion trees and counting calls

When a function calls itself more than once, draw a recursion tree: each call is a box, and its children are the calls it makes. The total work is the number of boxes times the work in each box.

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, ...) are defined recursively: each is the sum of the two before it. The direct recursive code is short but makes two calls per call, so the tree roughly doubles at every level. Let us count the calls:

from functools import cache

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    calls = 0
    print(f"fib({n}) = {fib(n)} using {calls} calls")

memo_calls = 0
@cache
def fib_memo(n):
    global memo_calls
    memo_calls += 1
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(f"fib_memo(25) = {fib_memo(25)} using {memo_calls} calls")

fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(25) = 75025 using 242785 calls
fib_memo(25) = 75025 using 26 calls

Each extra 5 in n multiplies the calls by about 11, which is exponential growth, roughly O(1.6ⁿ). The reason is repeated work: fib(23) is computed again and again in different branches of the tree. functools.cache remembers each answer the first time, so every value from 0 to 25 is computed once: 26 calls. Storing answers to repeated sub-problems is called memoisation, and it is the first step of Dynamic Programming.

Divide and conquer: fast power

Divide and conquer means splitting a problem into smaller parts, solving them recursively and combining the results. Merge sort and quick sort use it. A small example is computing xⁿ. The obvious loop does n multiplications. But x¹⁰ = (x⁵)², and x⁵ = x × (x²)², so halving the exponent at each step needs only O(log n) multiplications.

mults = 0

def power(x, n):
    global mults
    if n == 0:
        return 1
    half = power(x, n // 2)        # solve the half-size problem once
    mults += 1
    result = half * half
    if n % 2 == 1:                 # odd exponent: one extra x
        mults += 1
        result *= x
    return result

for n in [10, 100, 1000]:
    mults = 0
    value = power(2, n)
    print(f"2^{n} has {len(str(value))} digits, {mults} multiplications instead of {n - 1}")
print(power(3, 13) == 3 ** 13)

2^10 has 4 digits, 6 multiplications instead of 9
2^100 has 31 digits, 10 multiplications instead of 99
2^1000 has 302 digits, 16 multiplications instead of 999
True

The key detail is calling power(x, n // 2) once and storing it in half. Writing power(x, n // 2) * power(x, n // 2) would make two calls per level and lose all the speed. Python's built-in pow(x, n, m) uses this same idea for modular powers, which is how encryption handles enormous exponents.

Recursion on nested data

Recursion fits naturally when data is nested inside itself, like folders inside folders. A folder's size is the size of its own files plus the sizes of all its sub-folders, which is a recursive definition.

project = {
    "notes.txt": 12,
    "photos": {"goa.jpg": 2400, "kochi.jpg": 1800},
    "college": {
        "dsa": {"graphs.pdf": 950, "trees.pdf": 700},
        "marks.xlsx": 40,
    },
}

def total_size(folder):
    size = 0
    for name, item in folder.items():
        if isinstance(item, dict):
            size += total_size(item)     # a sub-folder: recurse
        else:
            size += item                 # a file: base case
    return size

print("Total KB:", total_size(project))
print("College KB:", total_size(project["college"]))

Total KB: 5902
College KB: 1690

The base case here is hidden in the loop: a file returns its size without another call, and an empty folder returns 0. This is exactly how you will process Trees & Binary Trees.

When recursion gets too deep

Python limits the depth of the call stack, 1000 frames by default, to stop runaway recursion from crashing the program. Going deeper raises RecursionError. Python also does not optimise tail calls, so even a function whose last step is the recursive call still uses one frame per call.

import sys

def count_down(n):
    return 0 if n == 0 else 1 + count_down(n - 1)

print("Limit:", sys.getrecursionlimit())
print(count_down(900))
try:
    count_down(5000)
except RecursionError as err:
    print("RecursionError:", err)

def count_down_loop(n):           # the same work with a loop: no depth limit
    steps = 0
    while n > 0:
        n -= 1
        steps += 1
    return steps

print(count_down_loop(5000))

Limit: 1000
900
RecursionError: maximum recursion depth exceeded
5000

You can raise the limit with sys.setrecursionlimit(), but that only moves the problem and can crash the interpreter if the real stack runs out. For inputs that can be deep, such as a linked list of a lakh nodes, write a loop, or keep your own explicit stack (a list of work still to do). You will see the explicit stack version of graph search in Depth-First Search (DFS).

Common mistakes

• Missing or unreachable base case. If n can skip past the base case (for example, n == 0 with n going down by 2 from an odd number), the recursion never stops.
• Not making the problem smaller. f(n) calling f(n) loops forever.
• Repeating the same recursive call. Store a result in a variable instead of calling twice.
• Ignoring stack depth. Recursion that is n levels deep fails for large n in Python.

Key points

• A recursive function needs a base case and a recursive case that moves towards it.
• Each call uses a stack frame, so recursion depth costs O(depth) space.
• Draw a recursion tree and count the calls to find the time complexity.
• Repeated sub-problems make naive recursion exponential; memoisation removes the repetition.
• Divide and conquer, such as fast power, can turn O(n) work into O(log n).
• Python's default depth limit is 1000; use loops or an explicit stack for deep inputs.

from functools import cache

@cache
def count_paths(rows, cols):
    if rows == 1 or cols == 1:
        return 1
    return count_paths(rows - 1, cols) + count_paths(rows, cols - 1)

print(count_paths(3, 3))
print(count_paths(10, 10))

6
48620