Recursion trees, complexity and stack limits

≈ 45 min

Recursion trees, complexity and stack limits

A recursion tree represents each call as a node and each recursive call as an edge. It is useful for visualising divide-and-conquer algorithms and for spotting duplicated work. A method that makes two calls on nearly the same input can grow rapidly; a method that makes one call on n - 1 has a simple linear chain but still uses one stack frame per call.

Complexity describes how resource use grows as input grows. Big-O notation ignores constant factors but does not ignore a bad growth pattern. Recursive Fibonacci without memoisation repeats the same subproblems, while binary search discards half an ordered interval at each step. Stack depth is separate from total runtime: a deep chain can overflow even if each step is simple.

Worked reasoning. For binary search on 32 sorted items, each call halves the remaining interval: 32, 16, 8, 4, 2, 1. At most about five comparisons are needed before the interval is empty or the item is found. For a linear recursive search, the worst case checks every item and creates one frame per item.

Exam lens. Draw the first few levels, then state the shrinking rule. Do not claim logarithmic behaviour unless the remaining problem is repeatedly divided by a constant factor.

java

Uses Uvero's optional secure Java practice service. If it is unavailable, your lessons and progress still work.

Which statement is the most defensible principle for Recursion trees, complexity and stack limits?

A recursion tree exposes the number of calls, work per level and where repeated subproblems or stack growth appear.

Treat an implementation detail as more important than the stated rule.

Assume one successful run proves the system is correct in every case.

Avoid recording assumptions, limits or failure conditions.

Enter the key term for Recursion trees, complexity and stack limits. What diagram shows how a recursive call splits into smaller calls?

A recursive method calls itself twice with n - 1 and does no caching. What risk should a recursion tree reveal?

It can create many repeated subproblems and grow exponentially, making it impractical for modestly large n.

Use a larger class or broader permission without stating a rule.

Trust the first output and skip a boundary or failure check.

Hide the decision so affected people cannot inspect it.

Name the concise safeguard or principle that completes this lesson’s scenario: A recursive method calls itself twice with n - 1 and does no caching. What risk should a recursion tree reveal?