Working out the cost of recursion

Complexity analysis Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
calls = 0

def ways(n: int) -> int:
    global calls
    calls += 1
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)

ways(20)
print(calls)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 21891

Right: the call tree grows roughly by a factor of 1.6 per level.

Over twenty thousand calls for n = 20 is the exponential call tree that memoisation collapses to about n calls.

Why not the others?
  • B 21. With a memo it would be about n calls; without one the tree branches.
  • C 40. Each call spawns two more until the base case, so calls grow exponentially.
The call tree of a two-branch recursion for n = 5, without and with a memo; repeated calls disappear once results are cached.

Illustrative

Text version

No memo:

  • ways(5): call
    • ways(4): call
      • ways(3): call
        • ways(2): call
          • ways(1): call
          • ways(0): call
        • ways(1): call
      • ways(2): call
        • ways(1): call
        • ways(0): call
    • ways(3): call
      • ways(2): call
        • ways(1): call
        • ways(0): call
      • ways(1): call

Result: 8 · 15 calls (call 15)

With memo:

  • ways(5): call
    • ways(4): call
      • ways(3): call
        • ways(2): call
          • ways(1): call
          • ways(0): call
        • ways(1): memo hit
      • ways(2): memo hit
    • ways(3): memo hit

Result: 8 · 9 calls (call 6, memo hit 3)

30-second answer

Draw the call tree: cost = total work across all calls. If each call does O(1) work and makes two calls on n - 1, the tree has about 2ⁿ calls, so O(2ⁿ). If each call splits the input in half and does O(n) work to combine, there are log n levels each doing O(n) in total, so O(n log n). Memoisation caps the calls at the number of distinct arguments.

Practise saying it · 60 s. No recording, just a timer

Explain how to analyse recursive cost.

Say your answer out loud, then check which of these points you covered:

  • Draw the call tree
  • Calls × work per call
  • Common recurrences

Deep dive

Common recurrences: T(n) = T(n/2) + O(1) is O(log n); T(n) = 2T(n/2) + O(n) is O(n log n); T(n) = T(n - 1) + O(1) is O(n).

The master theorem covers many divide-and-conquer cases, but drawing the tree is usually faster in an interview.

Count stack depth separately for space.

Common mistakes

  • Calling naive Fibonacci-style recursion O(n) because 'it goes down to 0 once'.
  • Forgetting the work done outside the recursive calls (merging, slicing).

Senior take & follow-ups

Sketch the first three levels of the call tree; the pattern usually shows the answer.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is T(n) = 2T(n - 1) + O(1)?

    Show hint

    O(2ⁿ): each level doubles the number of calls.

  2. What does memoisation change?

    Show hint

    Calls drop to the number of distinct states times work per state.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.