cs-088 — The Tower Steps

Problem

Count ways to climb n steps taking 1 or 2 at a time. Recursion tree shows re-computation; memoisation saves it. The bridge to dynamic programming.

Your deliverable is the recurrence with base cases, the answer for the worked instance, and the memoised (or tabulated) version. If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.

Examples

• Input: ways(5) = 8 (1+1+1+1+1, 2+1+1+1, ... patterns); ways(1)=1, ways(2)=2
• Output: ways(n) = ways(n-1) + ways(n-2): Fibonacci in disguise; memo turns 2^n into O(n)

Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.

What to notice

• Last move is 1 or 2 - so ways(n) = ways(n-1) + ways(n-2). Draw the tree for n=5 and circle repeats.
• Trust the recursive call: if f(smaller) is correct, the transition is all you must get right.
• A DP table is the call tree, cached.

Discussion starter

After the solution is revealed, the class spends five minutes on this prompt: "State f(k)'s meaning in words; is your statement precise enough to code from?"

Constraints and assumptions

• Difficulty: Expert (independent design decisions and proof-shaped arguments assumed).
• Topics: recursion, dp preview.
• Classroom-scale inputs unless the problem says otherwise.
• Time-box: about five minutes for the attack plan; the full argument may exceed the box - outline the proof strategy instead of grinding details.
• Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.

Hints and extension

• First nudge: identify the pattern the worked instance uses before computing anything.
• If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
• After the reveal, attempt the extension below before the next lecture.
• Extension challenge: Convert the recursion to a loop and compare the call stacks.