Recursion depth and the call stack

Intermediate Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

Every recursive call consumes a stack frame in CPython: local variables, return address, and bookkeeping. Depth d means d frames simultaneously—fine when d is the logarithm of n (balanced divide-and-conquer), painful when d is proportional to n (deep chains of nested dicts or skewed trees).

sys.setrecursionlimit exists but is a band-aid: it does not change algorithmic depth, only how late the interpreter gives up. For data pipelines that process huge sequential structures, prefer loops, iterators, or chunked processing.

Euclidean GCD is a classic example of logarithmic-depth recursion: arguments shrink quickly. Naive recursion down a linked list of length one million is not.

sys.setrecursionlimit reference: [1].

Sources

[1]https://docs.python.org/3/library/sys.html#sys.setrecursionlimit Return to text

University approvals: 0

Tasks

Question 1

What happens when Python recursion exceeds the interpreter limit?

Hint

CPython protects the C stack with a recursion depth check.

Python silently switches every call to iteration

RecursionError is raised

The process always segfaults immediately

Stack memory grows without bound on 64-bit systems

Question 2

You recurse down a deeply nested JSON list-of-lists mirroring millions of CSV rows. What is the most robust engineering response?

Hint

Depth tracks size → avoid linear recursion depth.

Set recursion limit to 10⁹

Use an explicit stack or iterative traversal for linear-depth chains

Switch to R

Store JSON as a single string and use regex only

Question 3

Implement gcd(a, b) for non-negative ints using recursion: gcd(a, 0) == a; else gcd(b, a % b). Negative inputs → ValueError.

Hint

Euclidean algorithm: remainder strictly decreases.

def gcd(a: int, b: int) -> int:
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Recursion & structural decomposition
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel