javascript steps climbing with recursion

Question

My problem is the same as in this question , but the only difference is that I have to return the number of ways in which the steps can be climbed according to a given array of permitted steps. For example, if steps to be climbed are 4 and the permitted steps are [1,3], the result should be 3. Combinations:[(1,1,1,1),(1,3),(3,1)]

I tried to modify the code as :

function add(x,arr){
let result = 0
   if(x<0)
      return 0;

   if(x===0)
      return 1;

   else{for(let i=0 ; i<arr.length ; i++){
        result += add(x-arr[i]);
      }
      return result};  
}
add(4,[1,3])

but this returns an error saying cannot read property length of "undefined".How do I correct this?

How do you call `add(x, arr)`? The message would clearly indicate that `arr` is `undefined` — Martin, Jul 30 '19 at 15:45
sorry I didn't include that.That's what it says after calling add. — Aditya Singh, Jul 30 '19 at 15:57

score 1 · Accepted Answer · answered Jul 30 '19 at 16:29

1

In your else condition,

result += add(x-arr[i])

Should be

result += add(x-arr[i], arr)

answered Jul 30 '19 at 16:29

Abbas Cyclewala

549
3
10

score 1 · Answer 2 · answered Jul 30 '19 at 19:24

I misread the question at first, and was happy to show how to convert a recursive function which counts the results to one which lists them. As I came here to post it, I realized that this was not what was asked, but I still find it a nice example of how one might go about this... so I'm posting it anyway. :-)

A straightforward counting solution, similar to the one in the question (with the fix from Abbas Cyclewala) could be structured like this:

const count = (n, ss) =>
  n < 0 ? 
    0 
  : n == 0 ? 
    1 
  :   // else
    ss.map(s => count(n - s, ss))
      .reduce((a, b) => a + b, 0)

console .log (
  count (4, [1, 3])  //~> 3
)

We can switch to a list of results instead of the count by noting that the equivalent of 0 is [], of 1 is [[]] and instead of adding all the recursive results, we need to simply concatenate them. That leaves only an update to the actual recursive results, which is not difficult: if the first step is of length k, recurse on (n - k), and prepend k to each result.

You can see how structurally similar these are:

const paths = (n, ss) => 
  n < 0 ? 
    [] 
  : n == 0 ? 
    [[]]
  :   // else
    ss.map(s => paths(n - s, ss).map(ps => [s, ...ps]))
      .reduce((a, b) => a.concat(b), [])

console .log (
  paths (4, [1, 3]) //~> [[1, 1, 1, 1], [1, 3], [3, 1]]
)

So this doesn't answer the original question, but if someone wants it, here it is!

javascript steps climbing with recursion

2 Answers2