## 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.

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

- 1, 1, 1, 1
- 2, 1, 1
- 1, 2, 1
- 1, 1, 2
- 2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

### 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^{1}.
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`

.
^{2}

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.

- For readers unfamiliar with picolisp, consult the tutorial (https://software-lab.de/doc/tut.html) which has links in the first two paragraphs for preliminary documents as well as the language reference.
^{[return]} - Actually, this function is
*in fact*a generalization of a Fibonacci function. Note that`(num-ways N (1 2))`

yields the`N`

-th Fibonacci number. Indeed,*any*function that computes recursive staircase solutions is a generalization of any function that computes the Fibonacci sequence.^{[return]}