Your base case seems to be wrong.
Suppose we want to climb $n$ stairs, we want to compute $F(n)$. There are three possibilities which can be defined recursively:
1) First cover 1 stair, then there are $F(n-1)$ ways to continue.
2) First cover 2 stairs, then there are $F(n-2)$ ways to continue.
3) First cover 3 stairs, then there are $F(n-3)$ ways to continue.
So we need to add these three options
$$F(n) = F(n-1) + F(n-2) + F(n-3)$$
where base case is
$$F(1) = 1, F(2)=2, F(3) = 4$$
UPDATE (on Charles, and quicksort comments):
How to derive base cases
$F(1)$ means we have only one stair and thus there is only one way to climb it. So, $F(1)=1$.
For $F(2)$ we have two stairs and there are only two ways to climb it: First stair, and then the second, or directly jump on the second stair. So, $F(2) = 2$.
Similarly for $F(3)$. We may move to the first stair, then to the second, and then to the third one. We may also jump to the second and then to the third, or alternatively step on the first and then jump to the third. And finally we could directly jump to the third stair. In total, four possibilities, $F(3) = 4$.
The following is the pseudocode:
Count(N)
if N == 1 return 1
if N == 2 return 2
if N == 3 return 4
return Count(N-1) + Count(N-2) + Count(N-3)
end
As for the above tree, you don't need to "unravel" for the case $N=3$ since it is the base case which is handled in a single if-statement. However, for $N=5$ the recursion tree would look like as the following:
( 5 )
/ | \
/ | \
/ | \
/ | \
(4) (3) (2)
/ | \ | |
/ | \ 4 2
(3) (2) (1)
| | |
4 2 1
Note that the above method of counting is the most terrible way since you always solve the same subproblems (overlapping subproblems) many times which leads to the exponential time. You could rewrite the algorithm which solves iteratively without using recursion as following
Count(n)
if n == 1 return 1
if n == 2 return 2
if n == 3 return 4
x1 = 1
x2 = 2
x3 = 4
i = 4
while i <= n
sum = x1 + x2 + x3
x1 = x2
x2 = x3
x3 = sum
i+=1
end
return sum
end
Finally (as quicksort noted in his/her comment), you could solve the above recurrence relation and find the closed form formula which gives you $O(1)$ solution (without need to compute the entire sequence up to $N$).
