Recursion Davis' Staircase understanding

Question

I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase

and I'm having difficulty understanding how the solution below solves the problem. Here's the tree (the recursion calls) like you would with the fibonacci problem but I don't see the insight

With N = 3 the possible choices are

• 3
• 1,1,1
• 2,1
• 1,2

But I don't see these states represented in the tree, I guess I'm not following the logic which makes it hard for me to solve recursive problems

func f(int n){
   if (n < 0) /* base case */
    return 0;
   if (n == 0) /* base case */
    return 1;

   return f(n-1) + f(n-2) + f(n-3)
}

Answer 1

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$).