How to return combinations generated from recursive function to outside?

Question

I need to solve the following task recursively:

Find combinations of ways to climb a stair case, you can take only one or two steps at a time.

For example, for n = 3, it should output [1,1,1],[2,1],[1,2].

This is what I got so far:

function num_ways(n, alreadyTakenSteps) {
  var output = [];
  if (n == 0) {
    console.log(...output, ...alreadyTakenSteps);
    return [...output, ...alreadyTakenSteps];
  }
  
  if (n >= 1) {
    var res1 = num_ways(n - 1,  [...[1], ...alreadyTakenSteps]);
    if (res1.length) {
      output=[...output, ...res1];
    }
    //console.log(res1);
  }
  
  if (n >= 2) {          
    var res2 = num_ways(n - 2, [...[2], ...alreadyTakenSteps]);
    output=[...output, ...res2];
  }
  
  return output;
}

var output = num_ways(3, []);
console.log(output);

In the stop-condition (first if-statement), I output the result. There, all outputs are fine. But the overall returned value is wrong (see output of console.log(output)).

How can i make this working?

Answer 1

Your problem

Now, the only problem with your code is in case n == 0.
Here, you currently return an array containing the elements of alreadyTakenSteps. This is wrong, because the return-value is then destructured, which results in losing the combination of a way among other destructured ways.

You can imagine it like this:
Currently, you return a way of taking the steps, which is then destructured and placed next to other destructured ways. We are essentially missing the ways among themselves, as we remove the arrays which identify them.

Instead, we want to return an array containing the ways. That array will then be destructured, placing all the different ways in one array. This will result in an array containing all the ways.

Simply put:
In case n == 0, return [alreadyTakenSteps]; return the existing way in a wrapper-array.

Thoughts on refactoring

• All statements of the form of ...[x] will result in x. It basically creates an immediately destructured array, which may impact memory-usage for a large n.
  Just change it to x.
• The use of var has become somewhat obsolete, as it can be replaced by either let or const in most cases.
  Using var is not a problem, but the alternatives may convey more meaning (e.g. the reference of a const is never changed, the reference of a let may be changed).
• We can use default parameters to simplify the call of num_ways(); more precisely, we can default the alreadyTakenSteps-parameter to []:
  function num_ways(n, alreadyTakenSteps = []) { ... }
  With this, a call could look like num_ways(3), but we can still pass the second argument in case we want to extend some already taken steps.
• Case n == 0:
  You are destructuring the empty output-array, effectively doing nothing. In this case, output actually doesn't need to be initialized yet.
  This means, it can be rewritten to [alreadyTakenSteps] (incorporating the solution from before), with var output = []; after this if-statement.
• Case n >= 1:
  The inner if (res1.length) is unnecessary, since we pass [1, ...alreadyTakenSteps] as the second argument, which contains at least 1 as an element.

Afterthoughts

What I personally dislike is your way of re-instantiating the output-array for cases n >= 1 and n >= 2. This can be circumvented by using more cases.

Here is my implementation of the task. Difference between yours and mine is, that mine will return an empty array instead of an array containing an empty array.
Semantically, this would be equal to…

• …you saying: "There is a way: You may take 0 steps."
• …me saying: "There is no way: You cannot climb such 'stairs'."

console.log(recursiveNumWays(3));

function recursiveNumWays(n, arr = []) {
  if (n == 0) return arr;
  if (n == 1) return [1, ...arr];
  
  const ways1 = recursiveNumWays(n - 1, [1, ...arr]);
  const ways2 = recursiveNumWays(n - 2, [2, ...arr]);
  
  if (n == 2)
    return [ways1, ways2];
  if (n == 3)
    return [...ways1, ways2];
  
  return [...ways1, ...ways2];
}

.as-console-wrapper{max-height:100%!important;top:0}

Answer 2

I just want to point out a perhaps cleaner implementation of the same idea.

const climbStairs = (n) =>
  n < 1 
    ? [[]] 
    : [
        ... climbStairs (n - 1) .map (p => [1, ... p]),
        ... (n > 1 ? climbStairs (n - 2) .map (p => [2, ... p]) : []),
      ]

console .log (climbStairs (5))

.as-console-wrapper {max-height: 100% !important; top: 0}

If there are no stairs remaining, there is only one path, up them, the empty path. If there's at least one, then we can take one step up and recur on the remaining stairs, or, if there are at least two stairs, then we can take two steps up and recur on the remainder. The .map calls just combine our current step with each of the recursive results.

One nice thing about this is how well it maps to the similar counting problem, where we don't want to list all the paths, but only to count them. Note how close this is to climbStairs:

const nbrOfWays = (n) =>
  n < 1 
    ? 1
    : nbrOfWays (n - 1) + 
      (n > 1 ? nbrOfWays (n - 2)  : 0)
  

console .log (nbrOfWays (5))

Answer 3

When there are no more steps to take you need to encapsulate the walk/array. So instead of return [...output,...alreadyTakenSteps]; do return [...output,...[alreadyTakenSteps]];

function num_ways(n,alreadyTakenSteps) {
    var output=[];
    if (n == 0) {
      console.log(...output,...alreadyTakenSteps);
      return [...output,...[alreadyTakenSteps]];
      
    }
    if (n >= 1) {
     
      var res1=num_ways(n - 1,  [...[1],...alreadyTakenSteps]);
      if(res1.length){
        output=[...output,...res1];
      }
     //console.log(res1);
    }
    if (n >= 2) {          
      var res2= num_ways(n - 2, [...[2],...alreadyTakenSteps]);
      output=[...output,...res2];
    }
    return output;
  };
 var output= num_ways(3,[]);
 console.log(output);