CODEWITHSUNDEEP
javascriptrecursion
Arp
Arp

Reputation: 1088

Why is my recursive function doing a recursion without passing a logical test (Javascript function help)?

I am performing a simple recursion and I am noticing that the logic which holds the recursion is being called even with a false parameter at the return ternary rule statement.

This little recursion will do the following:

  1. Sort the array from the smallest to the biggest
  2. reduce while a is smaller than 100
  3. If a is bigger than 100, call the function with the sliced array and increase vol.

In this case, the result if I call nSVol(nSm2, 0) should be 4.

I have noticed that it works well, until, after the last recursion, the arr is 70, arr length is 1 and vol is 4. Somehow, at this point of the recursion, even though I state that when the length equals 1 return vol + 1, the function is called once more, with the last snapshot of the arr, which in this case is [55, 70] and at the very end, vol is the result of its own value, plus the value of arr, which result in 73.

What am I doing wrong?

const nSm2 = [20, 55, 13, 20, 55, 13, 70];

  function nSVol(arr, vol) {
    return arr.length === 1
      ? vol + 1
      : arr
          .sort((a, b) => a - b)
          .reduce((a, b, i) =>
            a + b < 100 ? a + b : nSVol(arr.slice(i), vol + 1)
          );
  }

Upvotes: 0

Views: 44

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50807

Another fairly clean approach is the following more traditional recursive version:

const nSVol = (arr) => {
  const recur = ([x, ...xs], sum, vol) => 
    x == undefined
      ? vol
    : sum + x < 100
      ? recur (xs, sum + x, vol)
      : recur (xs, x, vol + 1)
  
  return recur (arr .sort ((a, b) => a - b), 0, 1)
}

const nSm2 = [20, 55, 13, 20, 55, 13, 70];

console .log (nSVol (nSm2)) //=> 4

We can easily convert it to one which collects the lists of numbers summing to below 100 rather than just counting them, with a version like this:

const breakdown = (arr) => {
  const recur = ([x, ...xs], sum, current) =>
    x == undefined
      ? current
    : sum + x < 100
      ? recur (xs, sum + x, [...current.slice(0, -1), [...current[current.length - 1], x]])
    : recur (xs, x, [...current, [x]])
  return recur (arr .sort ((a, b) => a - b), 0, [[]])
}

console .log (breakdown ([20, 55, 13, 20, 55, 13, 70])) 
//=> [[13, 13, 20, 20], [55], [55], [70]]

This latter version could be made cleaner by using some simple reusable helper functions:

const init = (xs) => xs .slice (0, -1)
const last = (xs) => xs [xs .length - 1]

//...
    : sum + x < 100
      ? recur (xs, sum + x, [...init (current), [...last (current), x]])

or a dedicated helper function:

const appendToLast = (x, xss) => 
  [... xss .slice (0, -1), [...xss [xss.length - 1], x]]

// ...
    : sum + x < 100
      ? recur (xs, sum + x, appendToLast(x, current))

Upvotes: 0

Aplet123
Aplet123

Reputation: 35560

The issue with your code is that the reduce keeps going after it passes 100, which means that you end up having a lot of repeated calculations that don't need to happen. Instead of using reduce, just use a loop (yes, recursive functions can still have loops in them) to find when you first pass 100. Also, you don't need to sort every time, so you can just put the recursive part in a helper function:

function nSVolHelper(arr, vol) {
    let sum = 0;
    for (let i = 0; i < arr.length; i ++) {
        if (sum + arr[i] < 100) {
            sum += arr[i];
        } else {
            return nSVolHelper(arr.slice(i), vol + 1);
        }
    }
    return vol + 1;
}

function nSVol(arr) {
    return nSVolHelper(arr.sort((a, b) => a - b), 0);
}

Upvotes: 1

Related Questions