4
$\begingroup$

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)
}

enter image description here

$\endgroup$
  • $\begingroup$ What do you think you mean when you say, “With N = 3 the possible choices are”? $\endgroup$ – Charles Jul 30 '17 at 5:38
  • 1
    $\begingroup$ Also, could you please share with us where you got the "solution below" (the four bulletined values), and why you think that it is correct. $\endgroup$ – Charles Jul 30 '17 at 5:52
  • 1
    $\begingroup$ You never state the problem. The hackerrank link might rot one day, so you should state the problem (in your own words) while giving credit and linking to hackerrank. $\endgroup$ – Yuval Filmus Jul 30 '17 at 7:28
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think it would be (much) more helpful to the OP if you could show how you actually derived those base case values. Which is to say, to show how you "unravelled" the recursive calls and summed the values within the return statements. $\endgroup$ – Charles Jul 30 '17 at 5:49
  • 1
    $\begingroup$ It's worth noting that there's a closed formula, it can be obtained by standard methods. $\endgroup$ – quicksort Jul 30 '17 at 5:56
  • $\begingroup$ @Charles Thanks for comments. I'll update accordingly. Cc:@quicksort $\endgroup$ – fade2black Jul 30 '17 at 6:07
  • $\begingroup$ @fade2black I was hoping that you would have derived the base case values by actually using the presented code, and not through a more, conversational and exhaustive, method. Perhaps I'll post an answer in the morning. $\endgroup$ – Charles Jul 30 '17 at 7:48
  • $\begingroup$ @Charles, I am very curious how you could derive for example $F(1)$ through the code or relation. They are BASE CASES. $\endgroup$ – fade2black Jul 30 '17 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.