Memoisation, iteration and recursion limits

≈ 45 min

Memoisation, iteration and recursion limits

Recursion is a tool, not a compulsory style. It is often clear for trees, divide-and-conquer algorithms and definitions that naturally refer to smaller cases. But repeated calls can waste time, and deep call chains can exhaust the stack. Memoisation stores a result for each already-solved subproblem so another call can reuse it instead of calculating it again.

Iteration can express the same recurrence with constant stack space when the work proceeds linearly. For Fibonacci, a naive recursive method repeats Fibonacci(n - 2) many times; memoisation removes repeated work, and an iterative loop keeps only the last two values. The best choice depends on input size, constraints and whether the recursive structure improves understanding.

Worked reasoning. For Fibonacci(6), naive recursion recalculates Fibonacci(4), Fibonacci(3) and smaller values multiple times. A memo table stores each result once. An iterative version begins with 0 and 1, then updates two variables until it reaches n. All can be correct, but their time, memory and stack behaviour differ.

Exam lens. Identify repeated subproblems and stack depth before choosing an optimisation. Do not claim memoisation helps when every recursive subproblem is already unique.

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 Memoisation, iteration and recursion limits?

Choose recursion, memoisation or iteration by comparing repeated work, stack depth, clarity and the required result.

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 Memoisation, iteration and recursion limits. What technique stores results of subproblems so repeated recursive calls can reuse them?

A recursive traversal visits each node of a tree exactly once. Is memoisation automatically useful?

No. If there are no repeated subproblems, caching may add memory and complexity without avoiding repeated computation.

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 traversal visits each node of a tree exactly once. Is memoisation automatically useful?