Library › Coding AI › College students

Speed up a recursive function with a hand-written memo

Practice: Setting limits and rules. About 5 minutes.

About this exercise

Your grid-paths function is far too slow for 16 x 16. Your course hasn't covered functools yet and the autograder blocks imports, so add memoization by hand: a memo=None parameter that becomes a dict inside the function (not a mutable default memo={}), keyed by (r, c). Keep the name, the r and c parameters and the base cases. Reply with exactly 1 code block of at most 12 lines, then exactly two lines: 'Before: O(2^(r+c))' and 'After: O(r*c)', under 25 words outside the code.

Common mistakes when you ask AI for this

  • Getting @lru_cache. The AI's go-to fix is functools.lru_cache, which your autograder blocks. Try: Say: "No imports; memoize by hand with a dict."
  • The mutable default trap. memo={} as a default is shared between calls, a classic bug. Try: Add: "Use memo=None and create the dict inside."
  • Switching to the formula. The AI may replace the recursion with factorials, which skips what you're practicing. Try: Add: "Keep the recursion and base cases; key the memo by (r, c)."
  • A lecture instead of two lines. The AI explains Big-O in paragraphs. Try: Show it: "After the code write exactly: Before: O(2^(r+c)) / After: O(r*c)."
  • Several versions. The AI shows a decorator version too. Try: Add: "One version, one code block, at most 12 lines."

What a strong prompt includes

  • Rules out imports
  • Asks for memo=None
  • Keeps the recursion
  • Shows the Big-O lines
  • Caps the reply

Practice this now ↑

Related exercises