Counting stair climbs without the exponential blow-up

You climb a staircase of n steps, taking either 1 or 2 steps at a time. The number of distinct ways to reach the top satisfies

ways(n) = ways(n-1) + ways(n-2),  ways(0) = 1,  ways(1) = 1

The naive recursion is fine for n = 20 but crawls at n = 45.

Explain why the direct recursion is exponential, then give an $O(n)$ version.