072. Recursion

Processes on Linux form a tree. A process can have child processes, which have their own children. He wants to sum total RAM usage across an entire process tree.

He realizes the problem is self-similar: the total RSS of a node is its own RSS plus the total RSS of each of its children — which is the same calculation applied recursively.

def total_rss(process_tree):
    """Sum RSS across a process node and all its descendants."""
    rss = process_tree["rss_mb"]
    for child in process_tree.get("children", []):
        rss += total_rss(child)   # same function, smaller problem
    return rss

chrome = {
    "name": "chrome", "rss_mb": 100,
    "children": [
        {"name": "chrome-gpu",     "rss_mb": 60, "children": []},
        {"name": "chrome-render",  "rss_mb": 80, "children": []},
    ]
}
print(total_rss(chrome))  # → 240

The BASE CASE is a process with no children — it just returns its own RSS. The RECURSIVE CASE adds child RSS values by calling itself.

⚠️ Without a base case, Python raises RecursionError: maximum recursion depth exceeded after ~1000 frames. Always identify your stopping condition first.

Learning objectives

Identify base cases and recursive cases in recursive functions
Implement classic recursive algorithms (factorial, fibonacci)
Understand the call stack and recursion depth

Key concepts

recursion
base case
recursive case
call stack

Try it

Concept detail

Recursion = a function that calls itself on a smaller version of the problem.

Two mandatory parts:

BASE CASE — stops recursion, returns directly (no self-call)
RECURSIVE CASE — calls itself with a strictly smaller input

Example — factorial: factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 ← base case hit

What happens without a base case: factorial(-1) calls factorial(-2) calls factorial(-3) … forever Python raises RecursionError after ~1000 frames (sys.getrecursionlimit())

WHY recursion: some problems are naturally recursive — trees, file systems, JSON parsing, divide-and-conquer algorithms (merge sort, binary search). For flat iteration, a regular loop is usually faster and safer.

Python’s default recursion limit is 1000. For deeper recursion, convert to an iterative solution with an explicit stack.

Solution

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

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Tests

def test_factorial_zero():
    assert factorial(0) == 1

def test_factorial_one():
    assert factorial(1) == 1

def test_factorial_five():
    assert factorial(5) == 120

def test_factorial_ten():
    assert factorial(10) == 3628800

def test_fibonacci_base():
    assert fibonacci(0) == 0
    assert fibonacci(1) == 1

def test_fibonacci_sequence():
    assert fibonacci(6) == 8
    assert fibonacci(10) == 55