We want to find $\texttt{N(n)}$, the number of ways to get to the $\texttt{n}^{\th}$ stair.

1. Recursion

To write $\texttt{N}$ recursively, we want to write $\texttt{N(n)}$ in terms of $\texttt{N(\small{something else})}$.

If you ever get stuck on this, it always helps to write the very end result recursively. The very end result above is $\texttt{N(4)}$, and we can get to step 4 from either step 3 or step 2. So $\texttt{N(4)} = \texttt{N(3)} + \texttt{N(2)}$. The same idea applies to any stair. In general, the recursion is:

2. Base case

The recursion calls smaller and smaller $\tt n$, and we need to find a stopping point for it. We need two base cases, because $\texttt{N(n)}$ depends on the previous two function calls $\texttt{N(n-1)}$ and $\texttt{N(n-2)}$.

We can stop when we get to the very first stair. We know the number of ways to get to the first stair is 1 because we start there, so $\texttt{N(0) = 1}$. We can also stop when we get to stair -1. There are no ways of getting to that step, so we can set the number of ways equal to zero, $\texttt{N(-1) = 0}$.

3. Code

To code this up, you can combine the recursion and base case as usual:

This solution is theoretically correct, but it's very slow, because it makes a lot of redundant function calls. To optimize, we have to use Dynamic Programming. To use Dynamic Programming, you compute function calls in the order that they're needed, so that you don't compute the same call twice, called "Tabulation".

To do this, you can realize that the function $\texttt{N(n)}$ depends on function calls that use smaller inputs $\texttt{N(n-1)}$ and $\texttt{N(n-2)}$. This means we can compute the function on smaller inputs first, and larger inputs last, going from $\texttt{N(-1), N(0), N(1), \dots, N(n)}$. We only have to keep track of the previous two values we've computed, because $\tt N$ only depends on the previous two function calls. Here's the code for doing this:

Time Complexity $O(n)$

Space Complexity $O(1)$