Thinking recursively

Don't trace every call in your head. Ask: if I already had the answer for a smaller input, how would I finish?

Climbing n stairs taking 1 or 2 steps at a time: your last move was either 1 step (from stair n − 1) or 2 steps (from n − 2). So ways(n) = ways(n − 1) + ways(n − 2).