Programming Fundamentals Questions

Direct answer
Plain assignment doesn't copy anything, it just gives a second name to the same object. A shallow copy creates a new outer container but reuses references to the same nested objects inside it, so mutating a nested element through either the original or the shallow copy is visible in both. A deep copy recursively copies every nested object too, giving you a fully independent structure.

Structured elaboration

• Assignment (b = a): a and b are now two names for the exact same object; b is a is True. There is no 'original' versus 'copy', they're the same thing.
• Shallow copy (copy.copy(a), or list(a), or a[:] for a list): creates a genuinely new outer object (b is a is now False), but for every element that is itself a mutable object (a nested list, a dict, a custom object), the copy holds a reference to the SAME nested object, not a copy of it (b[0] is a[0] is True).
• Deep copy (copy.deepcopy(a)): recursively walks the structure and makes a new copy of every nested mutable object too, so nothing is shared (b[0] is a[0] is False).
• The bug shape this causes: code that shallow-copies a nested structure believing it now has an independent snapshot, then mutates the original, and the 'snapshot' silently changes too, because the shallow copy's nested elements were never actually copied.

Worked example

import copy
original = [[1, 2, 3], [4, 5, 6]]
shallow = copy.copy(original)
deep = copy.deepcopy(original)

original[0].append(999)   # mutate a NESTED element of the original

Verified results after that mutation: original == [[1, 2, 3, 999], [4, 5, 6]], shallow == [[1, 2, 3, 999], [4, 5, 6]] (the nested list was shared, so the shallow copy sees the change too), deep == [[1, 2, 3], [4, 5, 6]] (fully independent, unaffected).

A realistic version of this bug: code takes a shallow copy of a dataset as a 'before' snapshot, then runs an in-place normalization pass over the dataset:

def normalize_inplace(rows):
    for row in rows:
        total = sum(row)
        for i in range(len(row)):
            row[i] = row[i] / total if total else 0

After running normalize_inplace on the dataset, the shallow-copied 'snapshot' taken beforehand is bitwise identical to the now-normalized dataset (verified by running it: snapshot == dataset evaluates True after normalization), because normalize_inplace mutates each row list in place, and the shallow copy's rows are the SAME row objects as the original's. The 'backup' was never a backup.

Trade-offs & pitfalls
The fix depends on what you actually need: if you truly need an independent snapshot, use copy.deepcopy (accepting its cost, see the mutability discussion) or rebuild the structure by copying each nested piece explicitly. If deep-copying every row of a large dataset is too expensive, the more scalable fix is usually to stop mutating in place at all, have normalize_inplace return a new structure instead of mutating its argument, which sidesteps the shallow/deep copy question entirely by removing the shared-mutable-state pattern that created the risk.

Direct answer
Recursion trades stack space and a per-call overhead for code that mirrors the problem's natural self-similar structure; iteration trades that clarity for constant stack usage and typically better raw performance. The concrete risk with recursion is a stack overflow on deep input, and the usual mitigating technique, tail-call optimization, is not guaranteed across mainstream languages (notably CPython does not do it).

Structured elaboration

• Readability: recursion often reads closer to the mathematical or structural definition of the problem (a tree, a fractal-like decomposition, n! = n * (n-1)!). Iteration usually needs an explicit accumulator or work-list and can obscure that structure, especially for tree/graph problems.
• Stack usage: each recursive call pushes a new stack frame (return address, local variables). A recursive call chain of depth n uses O(n) stack space, while a well-written iterative loop uses O(1) auxiliary stack space (the loop variables live in one frame).
• Stack overflow risk: if depth exceeds the runtime's limit, you get a hard failure (Python's RecursionError, a native segfault-style crash in some languages). This is a real production risk whenever recursion depth is driven by input size rather than a small fixed bound.
• Tail-call optimization (TCO): in a 'tail-recursive' function, the recursive call is the very last operation, nothing happens after it returns. A compiler or runtime that supports TCO can reuse the current stack frame for that call instead of pushing a new one, turning the recursion into a loop under the hood with O(1) stack usage. Languages like Scheme and (in the target-relevant case) Java's Scala guarantee this for self-tail-calls; CPython deliberately does NOT implement it (a language design choice, not a limitation of the trick) partly because it would make stack traces less informative for debugging.

Worked example

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)      # NOT tail-recursive: multiply happens after the call returns

def factorial_tail_style(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail_style(n - 1, acc * n)  # tail-recursive IN FORM, but Python still doesn't optimize it

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

All three agree on small input (verified: factorial_recursive(10) == factorial_iterative(10) == factorial_tail_style(10) == 3628800). The difference shows up at depth: with CPython's default recursion limit of 1000, factorial_recursive(5000) raises RecursionError: maximum recursion depth exceeded (confirmed by running it), while factorial_iterative(5000) completes normally regardless of the tail-style rewrite, because CPython never collapses the recursive call chain into a loop. The same real-world shape shows up walking a deep hierarchical structure (a category tree, a nested comment thread): a recursive walker is elegant until the tree gets deep enough that the recursion limit, not the actual computation, is what fails.

Trade-offs & pitfalls
A correct senior answer does not claim 'just write tail-recursive code and it'll be fine' in a language like Python, that is a common and wrong mental shortcut. The real decision is: if depth is bounded and small (most tree structures in practice), recursion's readability usually wins; if depth scales with untrusted or unbounded input, convert to an explicit iterative version with your own stack (see the tree-traversal conversion question for a worked version of exactly that conversion) rather than relying on the language to save you.

Direct answer
Convert the recursive walk into an explicit loop that maintains its own stack (a plain list/array), pushing left children as you descend and popping/visiting/moving right exactly where the recursive calls would have happened, so the traversal order is identical but the call depth is no longer tied to the language's function-call stack.

Structured elaboration
The recursive in-order traversal is: recurse left, visit the node, recurse right. Each recursive call pushes a real stack frame, so a left-skewed tree of depth d uses O(d) frames and blows the interpreter's recursion limit once d exceeds it (Python's default is 1000). The iterative version replaces those implicit call-stack frames with an explicit stack you manage yourself, which lives on the heap and has no language-imposed depth limit (bounded only by available memory, not by a fixed call-depth ceiling):

1. Walk left as far as possible, pushing every node visited onto the stack (mirrors descending through the left-recursion calls without visiting yet).
2. Pop the top of the stack, that's the next node to visit, in the exact order the recursive version would have visited it.
3. Move to that node's right child and repeat from step 1 (mirrors the recurse-right call).
4. Stop when the stack is empty and there's no current node left to descend into.

Worked example

def inorder_iterative(root):
    out = []
    stack = []
    node = root
    while stack or node is not None:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

Verified against a known small balanced tree (root 4, left subtree 2 with children 1 and 3, right subtree 6 with children 5 and 7): both the recursive version and this iterative version return [1, 2, 3, 4, 5, 6, 7], identical order. Verified against a deliberately pathological case, a left-skewed tree of depth 3000 (each node's left child is the next node down, no right children): the recursive version raises RecursionError: maximum recursion depth exceeded at Python's default limit of 1000, while the iterative version completes and returns all 3000 values in order (len(result) == 3000, result == list(range(1, 3001))), confirming it has no equivalent depth ceiling.

Trade-offs & pitfalls
The iterative version is not simply 'better', it trades the recursive version's direct correspondence to the problem's structure (which makes it easy to verify by inspection) for an explicit stack whose invariant (everything on the stack is an ancestor of the current node, still awaiting its visit-and-descend-right) is easy to get subtly wrong, common bugs are popping before fully descending left, or forgetting to move to node.right after visiting and looping forever on the same node. This conversion is worth doing specifically when input depth is attacker- or user-controlled and therefore cannot be assumed small (a request-driven tree/graph walk), not as a blanket 'recursion is bad' rule for every tree operation.

Direct answer
A pure function's output depends only on its inputs, and calling it produces no observable effect outside its own return value, no mutation of external state, no I/O, no reliance on anything that could change between calls. A function with side effects does at least one of those things: it might mutate a variable outside its own scope, write to a file, or return a different result for the same input depending on some external state.

Structured elaboration

• Same input, same output, always: this is the defining property. math.sqrt(4) is pure, it returns 2.0 every single time. A function that reads the current time, a global counter, or a mutable default argument that accumulates across calls is not pure, its output can differ across calls even with identical arguments.
• No observable effects outside the return value: a pure function doesn't print, doesn't write to a database, doesn't mutate an object passed into it, doesn't increment a counter defined outside itself. If you could delete every call to it (assuming nothing used the return value) and the rest of the program's behavior would be unchanged, that's a strong sign of purity; if deleting a call changes behavior beyond 'the return value is no longer available', something impure happened inside it.
• Why purity matters for testing: a pure function needs no setup beyond its arguments and no teardown, you call it, you assert on the return value, done. An impure function's test has to also arrange whatever external state it reads, and verify whatever external state it mutates, which multiplies both the setup complexity and the number of ways the test can be wrong or flaky.
• Why purity matters for parallel execution: if a function only reads its inputs and produces a return value, calling it concurrently from multiple threads for different inputs is automatically safe, there's no shared mutable state for two calls to race on. An impure function that mutates shared state needs explicit synchronization (locks) to be safe under concurrency, or it will produce wrong results or crashes under load in a way that's notoriously hard to reproduce.

Worked example

def add_tax_pure(price, rate):
    return price * (1 + rate)          # no side effects

total_calls = {"count": 0}
def add_tax_impure(price, rate):
    total_calls["count"] += 1          # side effect: mutates external state
    return price * (1 + rate)

Verified: add_tax_pure(100, 0.08) returns 108.0 every time it's called, and calling it twice does not change anything else observable in the program. add_tax_impure(100, 0.08) returns the same 108.0, but after two calls total_calls["count"] has become 2, a change visible to any OTHER code that also reads total_calls, which is exactly the kind of hidden coupling purity avoids: two unrelated pieces of code that both happen to call add_tax_impure now silently affect each other's view of total_calls.

Trade-offs & pitfalls
Purity isn't free, and most real programs need SOME side effects (writing output, updating a database) somewhere; the useful discipline is not 'eliminate all side effects everywhere' but 'push side effects to the edges of the system and keep the core computation (the actual business logic, the actual data transformation) pure', so the large majority of the code gets the testing and concurrency benefits, and the necessarily-impure parts are small, isolated, and easy to reason about individually.

Direct answer
The stack holds each function call's local variables and control-flow bookkeeping in a strict last-in-first-out region that's automatically reclaimed the instant a function returns; the heap holds data whose lifetime isn't tied to any single function call, and it's reclaimed either manually (unmanaged languages) or by a garbage collector (managed languages).

Structured elaboration

• What lives where: a local primitive variable, or in some languages a fixed-size value type, is allocated on the stack as part of the current function's frame. Anything created with an explicit allocation (new in Java/C++, any Python object, since CPython objects are always heap-allocated even for an int) lives on the heap; the stack only holds a reference/pointer to it.
• Variable lifetime: a stack frame's contents die the moment that function returns, this is why you can't return a pointer to a local stack variable in C and expect it to still be valid. Heap objects live until nothing references them anymore, tracked either by the programmer (manual free/delete), reference counting, or a tracing garbage collector.
• Managed vs unmanaged: in C/C++, forgetting to free heap memory is a leak, and freeing it twice or using it after freeing ("use-after-free") is undefined behavior, a classic source of crashes and security bugs. In managed languages like Java or Python, the heap is reclaimed automatically, which removes that class of bug but introduces its own failure mode: an object that's still reachable (through a lingering reference you forgot about) never gets collected even though you're logically done with it, this looks exactly like a leak from the outside even though nothing is 'wrong' with the GC.
• Common pitfalls: dangling references (using a pointer after its target was freed) and double-free in unmanaged languages; unintentional retention (a cache, a global list, or a closure holding a reference longer than intended) in managed languages, which is the managed-language equivalent of a leak.

Worked example
A function def compute(x): result = x * 2; return result allocates result in its stack frame; that frame disappears the instant compute returns. If instead the function does def compute(x): return [x, x*2], the list object itself lives on the heap, only the reference to it lived momentarily in the stack frame, and the list survives the function return because the caller now holds a reference to it. This is exactly why returning a local list is safe in Python (you're returning a heap reference) while returning a pointer to a local stack array in C is not (you're returning a pointer to memory that's about to be reused by the next function call).

Trade-offs & pitfalls
Stack allocation is fast (just moving a pointer) and has zero collection cost; heap allocation is more flexible (variable size, unpredictable lifetime) but costs more per allocation and, in a managed language, imposes collection work (pause time, throughput cost) somewhere down the line. This is a large part of why some languages let you opt certain data onto the stack explicitly (value types, structs) when you know its lifetime is scoped to the current call, to avoid heap/GC overhead for short-lived data.