Recursive staircase

Background

Apparently this is a problem employers ask, See these youtube vids to get an idea.

• Amazon Coding Interview Question - Recursive Staircase Problem
  https://www.youtube.com/watch?v=5o-kdjv7FD0
• Algorithms: Solve ‘Recursive Staircase’ Using Recursion
  https://www.youtube.com/watch?v=eREiwuvzaUM

The host of the first video found the statement of the problem at https://www.dailycodingproblem.com. Here it is.

Picolisp solution

Yeah, don’t use Java, as in one of the referenced videos above (boy, was that painful to watch). We’ll be using picolisp¹. Let’s look at a recursive solution; then, let’s see how we can improve upon it.

Recursive solution

Our recursive solution here computes the number of ways to climb a staircase of Total-steps steps, given that one can take strides of various sizes (found in the input list Strides).

(de num-ways (Total-steps Strides)
  (sum '((Stride)
         (let Remaining (- Total-steps Stride)
              (cond ((lt0 Remaining) 0)
                    ((=0  Remaining) 1)
                    (T (num-ways Remaining Strides)))))
       Strides))

For each stride Stride, the number of ways to climb the entire staircase starting with taking a step of length Stride is equal to the number of ways to climb the remaining steps that you see after you take that initial step (namely, (num-ways Remaining Strides)). That’s how we reduce the problem to sub-problems of a smaller size. When these number of ways (for each (starting) stride) are computed, they are added together via the outer call to sum. The base cases of the recursion have these conditions:

• The steps remaining are less than zero — (lt0 Remaining) — in which case the last stride would be too long (would have caused the climber to “overshoot” the top step), e.g., there is one remaining step to take and Stride is 2 There are no ways to do that, which is why we return 0.
• There are no remaining steps to take — (=0 Remaining) — meaning that the last stride put the climber exactly on the top step. There is one way to do that; so, we return 1.

Example

Question: how many ways can one climb a 10-step staircase, if that person could climb one step at a time or two steps at a time (but no more)? Answer: (num-ways 10 (1 2)) -> 89 ways.

Notes

Notice that I used Total-steps (instead of N) and Strides (instead of X). I usually prefer longer, meaningful symbol names for identifiers, but shorter names sometimes yield easier-to-read code. It’s a judgment call and a matter of taste. (“Yeah, well, you know, that’s just, like, your opinion, man.”) Know your reader, if possible.

Some assumptions are being made:

• Total-steps is an integer.
• Strides is a list of positive integers with unique entries.

This, of course, may be enforced with extra code, and in a production environment it should be.

But more importantly, notice the recursive call. With a large enough value for Total-steps, we are going to blow up our call stack. So, let’s see about turning that into a loop.

Non-recursive solution

First, we observe that we are computing a sequence of numbers not unlike the Fibonacci sequence where we compute the I-th term of the sequence as the sum of the previous J-th terms (already computed) for J ∈ Strides. ²

Here’s the “bottom up” solution method described by the first video (toward the end) ported to picolisp. Notice how the picolisp code is no less concise than the pseudo/Python code from that video.

(de num-ways2 (Total-steps Strides)
  (let (Previous (list 1) Result 0)
    (for I Total-steps
      (zero Result)
      (for J Strides
        (when (>= I J)
          (inc 'Result (get Previous J))))  # add in the J-th preceding term
      (push 'Previous Result))              # cache the I-th term
    Result))

We can now compute the answer for large Total-steps.

: (num-ways2 400 (1 2))
-> 284812298108489611757988937681460995615380088782304890986477195645969271404032323901
: (num-ways2 4000 (1 2))
-> 64574884490948173531376949015369595644413900640151342708407577598177210359034088914449477807287241743760741523783818897499227009742183152482019062763550798743704275106856470216307593623057388506776767202069670477506088895294300509291166023947866841763853953813982281703936665369922709095308006821399524780721049955829191407029943622087779296459174012610148659520381170452591141331949336080577141708645783606636081941915217355115810993973945783493983844592749672661361548061615756595818944317619922097369917676974058206341892088144549337974422952140132621568340701016273422727827762726153066303093052982051757444742428033107522419466219655780413101759505231617222578292486081002391218785189299675757766920269402348733644662725774717740924068828300186439425921761082545463164628807702653752619616157324434040342057336683279284098590801501
:

In fact, we are only limited by two things, it appears: (i) the size of an integer (we have bignums here) and (ii) the size of the internal cache Previous which grows linearly with respect to Total-steps.

Columbo ending (“Just one more thing …”)

We can make the function have constant space by limiting the length of the cache Previous. After all, we only have to “remember” as far back as the M-th previous term, where M is (max Strides). For instance, if Strides is (1 3 5), we only have to remember as far back as 5 “terms ago” – 6 terms ago, 7 terms ago, and so on, we don’t care about any more. Accordingly, we have the following.

(de num-ways3 (Total-steps Strides)
  (let (Previous (need (- (apply max Strides)) (list 1) 0)
        Result   0)
    (do Total-steps
      (zero Result)
      (for J Strides
        (inc 'Result (get Previous J)))     # add in the J-th preceding term
      (set (rot Previous) Result))          # cache the I-th term
    Result))

We took the time to add a couple of improvements: (i) removing the check (when (>= I J), as it’s no longer needed because the cache is padded out with zeros and so we’ll always find a J-th previous entry, even from the beginning of the process, and (ii) removing the index I as it is no longer needed.

Recursive Columbo (“Just one more thing on that ‘one more thing’…”)

Thanks to some very handy primitives in picolisp and the fact that, because lisp programs are expressions (“turtles”) “all the way down,” we can manipulate the code very much like a mathematician manipulates mathematical expressions algebraically. We can “rearrange” or “reduce” the code, while maintaining its equivalence to previous code. In this case, we were able to “cancel out” the “variable” Result. Now, we have the following.

(de num-ways4 (Total-steps Strides)
  (let Previous (need (- (apply max Strides)) (list 1) 0)
    (do Total-steps
      (set (rot Previous) (sum '((J) (get Previous J)) Strides)))
    (car Previous)))

The code is shorter (even than the Python code in the first video). It might not be as clear as the code of num-ways3, but if the reader were an experienced picolisp programmer, it would likely be more clear (solely because the body of the function is more concise and idiomatic). The expression (sum '((J) (get Previous J)) Strides) computes the sum of the J-th previous terms (for all J in Strides). This is much more compact than the previous for loop and likely faster. That computation is always stored in the CAR of Previous (in every iteration of the do loop); so, when the process is complete, the final result can be found there.