@Necctor said in Why does recursion not work?:

Can you please explain why it should cost O(2^n)?

This problem is exactly like Fibonacci sequence, and although it's known that the naive recursion algorithm to generate Fib(n) is O(2^n), there's a tighter bound which is roughly O(1.6^2). It's easier to explain it as 2^n as follows:

You have n stairs to climb, each stair is unique and no repetition (you won't climb the same stair twice, but in fact the numbers do repeat as and we have overlapping subproblems, that's why we use DP for it), so from counting it would be 2^n

Another way to think about it, you have n stairs, at each stair you have 2 choices, either to jump 1 stair or 2 stairs, so at the first stair you n ways to jump either 1 stair or 2, then you have either n - 1 ways to jump 1 or 2 stairs or n - 2 ways to jump 1 or 2 stairs.

Back to why it's not O(2^n) exactly is the following

let's for example calculate for n = 4

```
4
/ \
3 2
/ \ \
2 1 0
| |
0 0
```

it would be exactly 2^n if each node has 2 children, but that's not the case cause some trees terminate with one child only

I hope that's all make sense to you