2

Here is a mapping function I was exercising on;

var list = [1,2,3,4,5];

function isOdd(v) {
    return v % 2 == 1;
}

function exclude(arr, fn) {
    var myList = [];
    for (var i = 0; i < arr.length; i++) {
        if (fn(arr[i])) {
            myList.push(arr[i]);
        }
    };
    return myList;
}

I want to replace for loop with a recursive solution but it doesn't produce a proper array since I started a new list in each function call at line 2. How can I solve it with a recursion? Here is the closest I got;

function exclude(arr, fn) {
    let myList = [];
    if (arr.length = 1) {
        if (fn(arr[0])) {
            return myList.push(arr[0]);
        }
    } else {
        return myList.push(exclude(arr.slice(1), fn));
    }
}

console.log(exclude(list, isOdd));
1
  • 2
    Is there a reason you don't want to use list.filter(isOdd)? Commented Jan 12, 2017 at 9:08

6 Answers 6

3

Try this one solution. I have changed a bit your implementation.

function exclude(arr, fn, output) {
  output || (output = []);
  
  if(!arr.length) { 
    return output;
  }
  
  if (fn(arr[0])) {
    output.push(arr[0]);
  }

  return exclude(arr.slice(1), fn, output);
}

console.log(exclude([1,2,3,4,5,6,7,8,9], function(i) { return i % 2; }));

Sign up to request clarification or add additional context in comments.

Comments

1
if (arr.length = 1) {

This assigns 1 to arr.length, effectively trimming the array if there are more than 1 items in it. You probably meant arr.length ===.

Secondly, the Array#push method returns the new length of the array, not the array itself, so where you have:

return myList.push(arr[0]);

You probably want:

myList.push(arr[0]);
return myList;

Comments

0

If you don't want to modify the original array and make copy of the original array on each recursive call, here could be an ugly solution

function exclude(arr, fn, result, index) {
    if (!result) {
        result = [];
        index = -1;
    }
    index++;
    if (index < arr.length && fn(arr[inndex]))
        result.push(arr[index]);
    if (index === arr.length)
        return result;
    return exclude(arr, fn, result, index);
}

console.log(exclude([1,2,3,4], function(i){return i%2===0;})); // prints "2,4"

Comments

0

IMHO, your example doesn't really fit with recursion. It is much more readable and less prone to errors to use the for loop here. Recursion can easily mess things up in JS because of contexts and scopes. If you really want to do it as a test case, i recommend you not to transform the array, it will be slow and not of much use. Anyway at the end, you will end with same behaviour as a for loop, but less efficient. here is an example:

var list = [1,2,3,4,5];

function isOdd(v) {
    return v % 2 == 1;
}

function exclude(arr, fn, optionalIndex) {
    var myList = [];
    if(!optionalIndex){
        optionalIndex = 0;
    }
    if(optionalIndex < arr.length){
        if(fn(arr[optionalIndex])){
            myList.push(arr[optionalIndex]);
        }
        myList = myList.concat(exclude(arr, fn, optionalIndex + 1));
    }
    return myList;
}

console.log(exclude(list, isOdd));

It actually would be more interesting for you to try to do it with a real recursion case, for example, using your version with for loop to filter this array with sub-arrays in it:

var list = [1, 2, 3, [0, 1, 2, [0, 10, 20, 30], 4], 5, [1 ,2 ,3]];

Comments

0

Just for fun of it, one line solution:

function exclude(a, fn, c) {
  return (c = c || (c !== 0 ? a.length - 1 : c)) >= a.splice(c, fn(a[c]) ? 0:1)*0 ? exclude(a, fn, c - 1) : a;
}

Snippet:

var list = [0,1,2,3,4,5];

function isOdd(v) {
    return v % 2 != 0;
}

function exclude(a, fn, c) {
  return (c = c || (c !== 0 ? a.length - 1 : c)) >= a.splice(c, fn(a[c]) ? 0:1)*0 ? exclude(a, fn, c - 1) : a;
}

console.log(exclude(list, isOdd));

Comments

0

Since JavaScript doesn't have tail call elimination a recursive solution over a large array will blow your stack. However a functional and recursive approach to the problem would look something like this:

function filter(arr, fn) {
    var stopAt = arr.length;
    function helper (index, acc) {
        return index === stopAt ? 
               acc : 
               helper(index+1, fn(arr[index]) ?
                               acc.concat([arr[index]]) :
                               acc) ;
    }
    return helper(0, []);
}

Of course this should never be production code. Having a functional interface while allowing for mutating internal structures is probably the best approach. If you were to look at the source for the functional library Rambda you see that they do mutate internal state.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.