Recursion and Call Stack

Recursion is not magic. It is a function calling itself with a smaller version of the problem, while the runtime keeps unfinished calls on the call stack. Understanding that stack is what separates clear recursive reasoning from memorized templates.

Base Case and Recursive Case

Every recursive function needs a base case that stops the chain and a recursive case that makes progress toward that base case. If either part is wrong, the code can loop forever, overflow the stack, or compute the wrong result.

Scenario: Folder Size Calculation

A file manager calculates folder size. A folder can contain files and other folders. This is naturally recursive because each folder asks the same question of its children. But if the folder tree is extremely deep, recursion depth can become a reliability risk.

Same Pattern in Java, Python, and JavaScript

These examples compute maximum depth of a binary tree. The base case is an empty node. The recursive case asks both children for their depth.

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

class MaxDepth {
    static int depth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

Recursion Cost Model

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Compute the maximum depth of a binary tree.
• Invert a binary tree recursively.
• Rewrite recursive DFS with an explicit stack to avoid call-stack overflow.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class TreeNode { TreeNode left; TreeNode right; }

class Depth {
    static int depth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

class Node { Node left; Node right; }
class Invert { static Node invert(Node node) { if (node == null) return null; Node tmp = node.left; node.left = invert(node.right); node.right = invert(tmp); return node; } }

import java.util.*;
class Dfs { static List<Integer> dfs(Map<Integer,List<Integer>> g, int start) { Set<Integer> seen = new HashSet<>(); Deque<Integer> stack = new ArrayDeque<>(); List<Integer> out = new ArrayList<>(); stack.push(start); while (!stack.isEmpty()) { int node = stack.pop(); if (!seen.add(node)) continue; out.add(node); for (int next : g.getOrDefault(node, List.of())) stack.push(next); } return out; } }

Solved modelWorked Interview Answer

Compute maximum binary-tree depth recursively. The empty node is the base case. Each non-empty node waits for the depths of its children and adds one.

class TreeNode { TreeNode left; TreeNode right; }

class Depth {
    static int depth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Missing the base case.
• Not making progress toward the base case.
• Ignoring stack depth for deep inputs.
• Repeating subproblems without memoization when overlap exists.
• Forgetting cycle detection in graph-like data.

Execution guardrailQuick-Start Checklist

• Define base case.
• Define recursive case.
• Prove input gets smaller or progresses.
• State time and call-stack space.
• Check depth and cycle risks.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice tree depth, tree inversion, and recursive DFS.
• Compare recursive DFS with explicit-stack DFS.
• Study memoization later for repeated recursive subproblems.