Recursion Basics

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. Merge Sort and Quick Sort — which you've already coded — are both recursive. So are tree traversals, backtracking, and a large share of dynamic programming solutions still to come. Python has one sharp edge here that Java and C++ don't share quite the same way: a low default recursion limit that trips up beginners constantly. This lesson covers the fundamentals, that gotcha, and the classic naive-vs-memoized Fibonacci example.

Base Case and Recursive Case

Every correct recursive function has exactly two parts:

• Base case: the condition that stops the recursion and returns a direct answer, with no further recursive call.
• Recursive case: the step that breaks the problem into a smaller version of itself and calls the function again.

def factorial(n):
    if n == 0 or n == 1:      # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(4))  # 24

Time complexity: O(n) — one call per value from n down to 1. Space complexity: O(n) — each call adds a frame to the call stack, and n frames exist at the deepest point before any of them return.

The Call Stack, Traced Frame By Frame

Every function call — recursive or not — pushes a new stack frame onto the call stack, holding that call's local variables and its return address. A recursive call is no different from any other call in this respect; the only unusual thing is that the function keeps calling itself, so frames pile up until the base case is hit. Here's factorial(4) traced step by step.

The key idea: factorial(4) cannot compute 4 * factorial(3) until factorial(3) actually returns a value. So the call stack grows all the way down to the base case before any multiplication happens, and then the multiplications happen on the way back up, in reverse order of the calls.

Python's Default Recursion Limit — A Real Gotcha

Unlike Java's JVM, which sizes its thread stack in megabytes and lets you recurse tens of thousands of frames deep before overflowing, CPython enforces a much smaller logical limit on the number of nested Python calls, checked explicitly rather than discovered by running out of memory. You can read and change it with the sys module.

import sys

print(sys.getrecursionlimit())  # 1000 on most CPython installs -- this is a COUNT of frames, not KB

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

count_down(2000)
# RecursionError: maximum recursion depth exceeded
# -- this is a perfectly correct function, it just recurses deeper than the default 1000-frame limit

Time complexity: O(n) intended, but it never completes for n around 1000+ under the default limit. Space complexity: O(n) frames until the limit check aborts it with RecursionError instead of silently corrupting memory.

import sys

sys.setrecursionlimit(5000)  # raise it -- only do this when you've verified the recursion is genuinely bounded
count_down(2000)             # now completes fine

Time complexity: O(n) — the raised limit doesn't change the work done, only how deep the call stack is allowed to go before Python aborts it. Space complexity: O(n) — still one frame per pending call, just with a higher ceiling before RecursionError would trigger.

Python Has No Tail-Call Optimization

A recursive call is tail recursive when the recursive call is the very last operation in the function — nothing happens after it returns. Some languages (Scheme, and to a degree Kotlin/Scala with an explicit annotation) detect this pattern and rewrite it into a loop at compile time, so it runs in O(1) stack space no matter how deep the recursion goes — tail-call optimization (TCO).

# This LOOKS tail recursive: the recursive call is the last thing that happens.
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # tail call

Time complexity: O(n) — same number of calls as the non-tail version. Space complexity: O(n) — despite looking tail recursive, CPython still pushes one real stack frame per call (see below), so this has no space advantage over the original factorial.

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Time complexity: O(n) — same work as the recursive version. Space complexity: O(1) — one loop variable and one accumulator, no call stack growth, which is exactly the property tail-call optimization would have given us automatically in a language that supports it.

Worked Example: Naive vs Memoized Fibonacci

This is the classic example for showing that "correct" recursion and "efficient" recursion are not the same thing — and it sets up the motivation for dynamic programming later in this track.

# Naive: recomputes the same subproblems over and over
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

fib_naive(5) calls fib_naive(4) and fib_naive(3). But fib_naive(4) itself calls fib_naive(3) again — so fib_naive(3) gets computed twice from scratch, fib_naive(2) gets computed three times, and so on. The call tree branches into roughly 2ⁿ total calls.

Time complexity: O(2ⁿ) — the call tree has two branches at every level down to depth n, and almost all of that work is duplicate. Space complexity: O(n) — the deepest single chain of pending calls (the recursion depth), even though the total number of calls is exponential.

The manual fix mirrors Java's HashMap-based memoization exactly — a plain dict cache passed (or held onto) between calls:

# Manual dict-based memo
def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]           # already solved -- O(1) lookup, no recursion
    result = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    cache[n] = result
    return result

print(fib_memo(50))

Time complexity: O(n) — each value from 0 to n is computed exactly once and then reused from the cache for every subsequent request. Space complexity: O(n) — the cache holds one entry per subproblem, plus O(n) recursion depth.

Python offers a genuinely idiomatic shortcut that skips writing the cache by hand entirely: functools.lru_cache, a decorator that memoizes any function's return values automatically, keyed on its arguments.

from functools import lru_cache

@lru_cache(maxsize=None)  # None = unbounded cache; keep every result computed so far
def fib_lru(n):
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

print(fib_lru(50))  # instant, thanks to automatic caching
print(fib_lru.cache_info())  # CacheInfo(hits=48, misses=51, maxsize=None, currsize=51)

Time complexity: O(n) — identical to the manual memo version; lru_cache just implements the same cache-lookup-before-recomputing idea as a reusable decorator. Space complexity: O(n) — one cache entry per distinct argument value seen, plus O(n) recursion depth.

Recursion vs Iteration — Choosing Deliberately