Recursion Davis' Staircase

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.

With N = 3 the possible choices are

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

Here's the tree (the recursion calls) similar to the fibonacci problem. 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

It looks like there are two questions: 1. How does code in OP solve question 2. How is state of a particular set of calls represented in tree.

I'll use "stride" to indicate that Davis climbed 1, 2, or 3 steps. The answer to the problem is the number of ways a set of strides can be combined to climb $n$ steps.

Answers:

1. Function $f$ returns the number of ways a staircase with $n$ steps can be climbed. If $f$ is called with a negative integer, it returns zero, because the previous stride was disallowed (it was greater than the number of steps left to the top). If called with zero, which means previous stride was allowed, it returns 1. If called with $n\ge 1$, then $f$ is called recursively with $n-1$, $n-2$, and $n-3$. It is called with the 3 different values because Davis' strides can be 1, 2, or 3 steps, which, respectively, leave $n-1,n-2,n-3$ steps to the top of the stairs. (Note that $f(0)=0$ and $f(1)=0$. So arguably $f$ returns the wrong value if it was non-recursively called with 0, but returns correct value if called recursively)

2. Each node in the graph represents a call with the label of the node being the argument to $f$. Each arrow represents a recursive call. Each number in red is the return value of a call. All leaf nodes will return 0 or 1. All non-leaf nodes will return the sum of the return values of their child nodes. So, for example, the node in light blue is $f(1)$ and was called from $f(3)$ (ie $f(n-2)$). That node calls $f(0),f(-1),f(-2)$ which return $1,0,0$ respectively. So $f(1)$ returns $1+0+0$ to $f(3)$, which returns $2+1+1$. Giving 4 ways to climb 3 steps.