i am trying to implement Array.reduce() method through recursion, it works for me
var index = 0;
function reduce(arr, fn, initial) {
if (index >= arr.length) {
return initial;
}
if (!initial) {
initial = arr[index];
index++;
}
initial = fn(initial, arr[index], index, arr);
index++;
return reduce(arr, fn, initial);
}but verifier doesn't accept my answer. What i did wrong?
Some issues:
index as a global variable which is never reset to 0, so if reduce is called more than once, it will have the wrong value. There are several solutions for this. I would suggest using the this value for keeping track of where you are.initial argument is optional, but your code tests this with !initial which is not good enough: if the value of initial is 0 or any other falsy value, it should not be treated as being absent. Use arguments.length instead.initial argument was not provided, you don't check whether that index has become too large. The callback function should never be called with an invalid index. Swap the two if statements.reduce returns undefined, but it should throw an error as is the case with the native reduce method.Here is how you could deal with those issues:
function reduce(arr, fn, initial) {
// Get iterator for the indexes from `this`.
// The first time it will not be an iterator, so get it from arr.keys().
const iter = Object(this).next ? this : arr.keys();
let item = iter.next();
if (arguments.length < 3) { // Solid check for presence of initial argument
// Throw error when there's nothing to reduce
if (item.done) {
throw new TypeError("reduce of empty array with no initial value");
}
initial = arr[item.value];
item = iter.next();
}
// Check end of array only after having dealt with missing initial value
if (item.done) return initial;
initial = fn(initial, arr[item.value], item.value, arr);
return reduce.call(iter, arr, fn, initial); // Pass on the index via `this`
}
// Some test cases
console.log(reduce([1, 2, 3], (a, b) => a+b, 0), "should be 6");
console.log(reduce([1, 2, 3], (a, b) => a+b, 0), "should be 6");
console.log(reduce([1, 2, 3], (a, b) => a+b), "should be 6");
console.log(reduce([1], (a, b) => a+b), "should be 1");
console.log(reduce([1], (a, b) => a+b, 2), "should be 3");
console.log(reduce([], (a, b) => a+b, 1), "should be 1");
try {
console.log(reduce([], (a, b) => a+b), "error");
} catch(e) {
console.log("Error was raised as expected");
}The this reference is private to the function and cannot be seen by the caller, so using it for propagating the current state (the iterator) seems ideal. The alternatives are:
The last option has as downside that this mutation can be detected by the caller. In the extreme case where the caller had frozen those objects, the code will even fail with an exception.
All solutions have any way one flaw: the original caller could pass a state via the initial call. So for each of the solutions, the caller could pass a specific value of the index (or iterator) like this:
index property of the function that is passed to reduce to have the value 5.reduce with call or apply, providing it a specific this value (an iterator).There is nothing that can be done about this, since the requirement was to use recursion. Because of the recursion requirement there is nothing the function can do in the recursive call that the original caller could not do as well.
Object(this).next or arr.keys()), but I figured it out, thanks!A possible solution could be to take the actual index into the functions arguments and check if the index exist in the array.
For a further recusion for finding the initialValue you need a symbol for an undefined value to ditinguish between an undefined and a non set value.
function reduce(array, fn, initialValue, index) {
index = index || 0;
if (arguments.length === 0) {
throw 'Reduce: No array';
}
if (arguments.length === 1 || typeof fn !== 'function') {
throw 'Reduce: No function';
}
if (arguments.length === 2) {
while (index < array.length && !(index in array)) {
index++;
}
if (index in array) {
return reduce(array, fn, array[index], index + 1)
}
throw 'Reduce: Empty array without initial value';
}
if (index >= array.length) {
return initialValue;
}
return reduce(array, fn, index in array ? fn(initialValue, array[index], index, array) : initialValue, index + 1);
}
// console.log(reduce()); // throws Reduce: No array
// console.log(reduce([])); // throws Reduce: No function
// console.log(reduce([], (a, b) => a + b)); // throws Reduce: Empty array without initial value
console.log(reduce([], (a, b) => a + b, 42));
console.log(reduce([3, 4], (a, b) => a + b));
arr fn inital), witthout index, but your solution is works)thanksAs you have discovered, placing the index parameter outside the function leads to the complication that it must be continually managed for the function to work. I would think that usually, assignments to write functions assume they will be self-contained rather than rely on global variables.
We can conceptualize reduce recursively like this:
function reduce(arr, fn, initial){
if (!arr.length)
return initial;
if (arr.length == 1)
return fn(initial, arr[0]);
return reduce(arr.slice(1), fn, fn(initial, arr[0]));
}
console.log(reduce([1,2,3], (a,b)=>a+b, 0)); // 6
In JavaScript, each call to slice produces a copy of that section of the array, making this version less efficient for larger inputs. One option to improve efficiency could be to have an inner recursive function that relies on two parameters, an index and an accumulator, that would traverse the array, but I'm not sure the verifier would allow it since the outer function would no longer be calling itself.
One more thing to watch out for in your code is that !initial would catch whenever initial is a value that evaluates to "falsy," not only when it is not passed in as a parameter.
Here's a "hack"ish (because it modifies fn, although we could modify it back :), index-based solution that does not require an extra parameter and uses the full 4 parameters of fn:
function reduce(arr, fn, initial){
if (fn.index === undefined)
fn.index = 0;
else
fn.index++;
if (fn.index == arr.length)
return initial;
return reduce(arr, fn, fn(initial, arr[fn.index], fn.index, arr));
}
console.log(reduce([1,2,3], (a,b)=>a+b, 0)); // 6
fn args (in original reduce callback function has 4 args)? !initial checking is not a good idea, i got it, thanks!)
fn and you would not need an extra parameter as in Nina and trincot's solutions. That property would carry through and could be then updated on the fn object in the next call. To me, however, this suggestion, as well as trincot's use of this, iterables, or adding extra parameters seems a bit "hack"ish. I prefer purer functions with simple parameters where possible.fn.
indexis stateful and will not be correct if you try to reduce more than one array.reducefunction, I prefer to just loop