Suggest an editImprove this articleRefine the answer for “What does "recursion depth" mean?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**Recursion depth** is the number of simultaneously active recursive calls (the depth of the call stack) during an algorithm's execution; it is also often used to mean the maximum possible or actual maximum depth of such calls for a given input. Stack consumption (memory) and the risk of a stack overflow depend directly on the recursion depth. **Key point:** the space complexity of a recursive algorithm is usually O(depth), because that many call frames are on the stack at once.Shown above the full answer for quick recall.Answer (EN)Image## Short answer Recursion depth is the number of simultaneously active recursive calls (the depth of the call stack) during an algorithm's execution; it is also often used to mean the maximum possible or actual maximum depth of such calls for a given input. Stack consumption (memory) and the risk of a stack overflow depend directly on the recursion depth. ## Detailed answer ### Definition - Current recursion depth: how many frames of the recursive function are on the stack at once at a given moment of execution. - Maximum recursion depth: the largest value of the current depth over the algorithm's run on a given input. It is often used to estimate memory cost and the solution's reliability. ### Why this matters - Stack memory: each recursive call holds local variables and a return address. Stack memory grows proportionally to depth: O(depth). - Stack overflow: if the depth exceeds the runtime/language limit, the program crashes with a stack overflow error. - Asymptotics: recursion depth often equals the problem's natural measure (input size, tree height, log n, etc.) and determines the space complexity. ### Code examples Example 1: factorial with maximum-depth measurement in JavaScript. ``` function fact(n, depth = 1, stats = { maxDepth: 0 }) { stats.maxDepth = Math.max(stats.maxDepth, depth); if (n <= 1) return 1; return n * fact(n - 1, depth + 1, stats); } const stats = { maxDepth: 0 }; console.log(fact(5, 1, stats)); // 120 console.log('maxDepth =', stats.maxDepth); // 5 // The maximum depth for fact(n) equals n (linear recursion). ``` Example 2: computing the height (maximum depth) of an N-ary tree in Python - the recursion depth equals the tree height. ``` class Node: def __init__(self, val, children=None): self.val = val self.children = children or [] def max_depth(root, depth=1): if root is None: return 0 if not root.children: return depth return max(max_depth(c, depth + 1) for c in root.children) root = Node(1, [Node(2), Node(3, [Node(4)])]) print(max_depth(root)) # 3 # The recursion depth when traversing a tree equals the tree height. ``` ### Estimating recursion depth for typical problems - Linear recursion (factorial, summing 1..n): depth = n → O(n). - Binary search: depth ≈ ⌊log2 n⌋ → O(log n). - Tree traversal (DFS): depth = tree height h → O(h). For an unbalanced tree h can be O(n). - Quicksort: average depth = O(log n), worst case = O(n) (with a poor pivot choice). ### Recursion depth and space complexity The space complexity of a recursive algorithm is usually O(depth), because that many call frames are on the stack at once. Approximate memory consumption can be estimated as: memory ≈ frame_size × depth. - Frame size includes local variables, parameters, the return address, and runtime bookkeeping. - With tail-call optimization, tail recursion can keep the stack at O(1), because the frame is reused. ### Tail recursion and optimization A tail call is a recursive call that is the last operation performed by a function. With tail-call optimization (TCO) support, the recursion depth can logically be large, but the stack physically stays at O(1). However, in many popular environments TCO is either unavailable or not guaranteed. - A reliable approach for deep recursion: rewrite it as an iterative algorithm with an explicit stack/loop. Comparison of a tail-recursive and an iterative version, using the sum of 1..n in JavaScript. ``` function sumRange(n, acc = 0) { if (n === 0) return acc; // tail call return sumRange(n - 1, acc + n); } // Iteratively (more reliable for large n): function sumRangeIter(n) { let acc = 0; while (n > 0) { acc += n; n--; } return acc; } console.log(sumRange(5)); // 15 console.log(sumRangeIter(5)); // 15 ``` ### Limitations and practical advice - Control the base case. It must be guaranteed to trigger and reduce the depth; otherwise infinite recursion is possible. - Estimate the worst-case depth on real data: for unbalanced structures it can be linear. - Configuration/limits: some environments let you change the recursion limit or stack size (for example, in some languages/runtimes), others do not; account for the target platform's constraints. - For potentially large depth, use iterative solutions or your own stack/queue. - Do not rely on TCO where it is not guaranteed; plan for O(depth) memory. ### How to answer in an interview - Give the definition: recursion depth is the number of active recursive calls and/or the maximum depth reached. - Mention the connection to the stack and the O(depth) space complexity. - Give an example (factorial/DFS) and say what the depth depends on (n, tree height, log n). - Describe the risk of stack overflow and the alternatives (iteration, a custom stack, balancing, tail recursion).For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.