I am attempting to create a function that aims to eliminate any consecutive duplicate elements in an array recursively. It works with a global variable, however, I find that rather weak work around. I have based my code off of this code (Remove all consecutive duplicates from the string; language used: C++). I understand there are mutability differences between strings and arrays, but I don't exactly understand what is occurring to the stack in the background. Once the function is run, the global variable is correct, but the output from the function itself is not. Any explanation or direction would be greatly appreciated. Thank you!

This is not a homework question, I'm just trying to hammer recursion into my skull as it still throws me for a loop. Sorry for the pun.

//var testArr = [1, 1, 2, 2, 3, 3, 1, 1, 1]
//press(testArr); //[1,2,3,1] //<= expected result
//current output [1, 2, 2, 3, 3, 1, 1, 1]
var arr = [];
var press = function(list) {
     //var arr = [];
    if (list.length === 0) {
        return arr;
    } 
    if (list.length === 1) {
        arr.push(list[0]);
        return list
    }
    if (list.length > 1 && list[0] !== list[1]) {
        arr.push(list[0])
        press(list.slice(1,));
    }
    if (list.length > 1 && list[0] === list[1]) {
        list.splice(0,1);
        press(list);
    }
    return list;
}

I am attempting to create a function that aims to eliminate any consecutive duplicate elements in an array recursively. It works with a global variable, however, I find that rather weak work around. I have based my code off of this code (Remove all consecutive duplicates from the string; language used: C++). I understand there are mutability differences between strings and arrays, but I don't exactly understand what is occurring to the stack in the background. Once the function is run, the global variable is correct, but the output from the function itself is not. Any explanation or direction would be greatly appreciated. Thank you!

This is not a homework question, I'm just trying to hammer recursion into my skull as it still throws me for a loop. Sorry for the pun.

//var testArr = [1, 1, 2, 2, 3, 3, 1, 1, 1]
//press(testArr); //[1,2,3,1] //<= expected result
//current output [1, 2, 2, 3, 3, 1, 1, 1]
var arr = [];
var press = function(list) {
     //var arr = [];
    if (list.length === 0) {
        return arr;
    } 
    if (list.length === 1) {
        arr.push(list[0]);
        return list
    }
    if (list.length > 1 && list[0] !== list[1]) {
        arr.push(list[0])
        press(list.slice(1,));
    }
    if (list.length > 1 && list[0] === list[1]) {
        list.splice(0,1);
        press(list);
    }
    return list;
}

• javascript
• arrays
• recursion

6 Answers 6

Using ECMAScript 6 features:

const testArr = [1, 1, 2, 2, 3, 3, 1, 1, 1];
const press = ([head, ...rest]) => {
  if (!head) return [];
  const tail = press(rest);
  return head === tail[0] ? tail : [head, ...tail];
}
console.log(press(testArr));

As a side note, I'd like to note that functional approach is a little bit shorter (yeah, I know that the question is about recursive approach):

const testArr = [1, 1, 2, 2, 3, 3, 1, 1, 1];
const output = testArr.reduce((list, next) => list.slice(-1)[0] === next ? list : [...list, next], []);
console.log(output);

Because list.slice(1,) copies the array, so in the recursive call list is not the original array. Changing that does not change the original array. You have to change the list you want to return (passing the result up the call stack):

list = [list[0], ...press(list.slice(1,))];

Maybe shorter:

const press = arr => arr.length > 1
  ? arr[0] === arr[1]
      ? press(arr.slice(1))
      :  [arr[0], ...press(arr.slice(1))]
  : arr;

You can do classic recursion (that reads like Haskell) without the global by recursing on the tail of the list:

var press = function(list) {
    if (list.length === 0) return [];
 
    let [head, ...rest] = list
    let l = press(rest)
    return (l[0] === head) 
            ? l
            : [head, ...l]
}

var testArr = [1, 1, 1, 1, 2, 2, 3, 3, 1, 1, 1, 2, 2]
console.log(press(testArr))

Basically ou need to return arr instead of list.

Then you need a single check for unequalnes of the actual element and the next element then push.

Go on with a sliced array and return arr at the end.

var arr = [];
var press = function(list) {
        if (list.length === 0) {
            return arr;
        } 
        if (list.length === 1) {
            arr.push(list[0]);
            return arr;
        }
        if (list[0] !== list[1]) {
            arr.push(list[0])
        }
        return press(list.slice(1));
    };

console.log(press([1, 1, 2, 2, 3, 3, 1, 1, 1]));

A diffrent approach is to use arr directly in the function, here renamed as result.

This one is teil optimized, because it ends with the call of the recursive function in case of more items.

var press = function(list, result = []) {
        if (list.length === 0) {
            return result;
        } 
        if (list.length === 1) {
            result.push(list[0]);
            return result;
        }
        if (list[0] !== list[1]) {
            result.push(list[0])
        }
        return press(list.slice(1), result);
    };

console.log(press([1, 1, 2, 2, 3, 3, 1, 1, 1]));

An even shorter approach without using another array for the result.

var press = function(list) {
        return list.length
            ? [].concat(list[0] === list[1] ? [] : list[0], press(list.slice(1)))
            : [];
    };

console.log(press([1, 1, 2, 2, 3, 3, 1, 1, 1]));

First you need to identify the base case, which is when the length of the array is less than 2. The recursion part needs to decide how the returned array should look like based on the criteria of no consecutive duplicates.

function press(list) {
  if (list.length <= 1) {
    return list  //base case
  } else if (list[0] === list[1]) {
    return press(list.slice(1, ))  //discard head of list
  } else {
    return [list.shift()].concat(press(list))  //keep head
  }
}

console.log(press([1,2,2,3,3,2,3,3,3,3])) //[1,2,3,2,3]
console.log(press([2])) //[2]
console.log(press([])) //[]

It's not pletely clear if you're intending to modify the original input. Using slice makes a copy to hand down to the next function call but calling splice does modify the original input, as does the C++ code you linked to. It does sound like you'd like to get rid of the global variable so let's do that.

Here are two versions. We have the convenience in JavaScript of dynamic parameter assignment, meaning we can make the first function call with only one parameter but set a default second parameter that we can then refer to during the recursion.

This version is quite simple. It modifies the original input by traversing it backwards and removing extra elements, which could also be simply done with a loop. This version uses O(n) time and no extra space.

// Our parameters are the original list and an
// index, i, pointing to our current array cell.
// We default to starting at the end of the list,
// can you think why? (Hint: think what would happen
// after our call to 'splice' if we went forward)
var press = function(list, i = list.length - 1) {
  // Base case, we've reached the beginning
  // of the list so we're done, return the 
  // modified list
  if (i == 0)
    return list;

  // The current element is the same as
  // the next one we're going to look at
  // (that's the one at i - 1) so remove it!
  if (list[i] == list[i - 1])
    list.splice(i, 1);
    
  // Return the result of continuing
  // each element's examination
  return press(list, i - 1);
}

console.log(press([1, 1, 2, 2, 3, 3, 1, 1, 1]));

And here's a version that does not modify the original list and (similarly to other answers here) results in O(n^2) space usage (and therefore time as well) by creating a copy of the list tail on each recursive call:

var press = function(list) {
  // The list is not long enough
  // to have extra elements, return it.
  if (list.length < 2)
    return list

  // The first two elements are different
  // so we definitely want to keep the
  // first one. Let's place it in an array
  // that we will 'concat' with the result
  // of pressing the list tail (the rest of the list).
  if (list[0] != list[1])
    return [list[0]].concat(press(list.slice(1)));
  
  // If we got here, the first two elements
  // are similar so we definitely just want
  // the result of pressing the rest of the list.
  return press(list.slice(1));
}

console.log(press([1, 1, 2, 2, 3, 3, 1, 1, 1]));