Yes. Different histories reach an identical remaining question. If the allowed steps never depend on history, the number of continuations from one step left is reusable.

ways(4)
├── ways(3)
│   ├── ways(2)
│   │   ├── ways(1)
│   │   └── ways(0)
│   └── ways(1)
└── ways(2)        ← same question as above
    ├── ways(1)
    └── ways(0)

def ways(remaining):
    if remaining == 0:
        return 1
    if remaining < 0:
        return 0
    return ways(remaining - 1) + ways(remaining - 2)

assert ways(4) == 5
assert ways(0) == 1

Zero remaining steps has one completion: choose no more moves. Negative remaining steps has no completion. The first choices, one step and two steps, are disjoint; adding their counts does not double-count an individual sequence.

The plain recursion has exponentially many call occurrences, with O(2**n) a simple upper bound. Its maximum active depth is O(n), not the total number of calls. There are only n+1 nonnegative remaining-step states.

Merge repeated states conceptually and the dependency picture becomes a directed acyclic graph. Caching stores one answer per state, but both callers still use that count; you do not throw away one route’s contribution.

Analogy limit: not every recursion benefits from caching. A tree-height calculation on a normal tree visits each node once already. And listing every staircase sequence still requires constructing every requested output.

No. Whether the previous move had size two changes the legal next moves. Add that information to the state, such as (remaining, previous_was_two).