Understanding Array.prototype.reduce () and Recursion Using the Example of Apple Pie

I had problems understanding reduce () and recursion in JavaScript, so I wrote this article to explain them to myself first (hey, look, it's a recursion!). These concepts have some similarities with cooking apple pie. I really hope you find my examples both useful and appetizing.

An array containing nested arrays is given:

var arr = [1, [2], [3, [[4]]]] 

As a result, we want to get:

 var flat = [1, 2, 3, 4] 

Using a for loop and an if statement.

If we know the maximum number of nested arrays that we have to work with (in example 4), then the for loop is quite suitable for iterating over each element of the array, and then the if statement to check if this element is itself an array, and etc…
')

 function flatten() { var flat = []; for (var i=0; i<arr.length; i++) { if (Array.isArray(arr[i])) { for (var ii=0; ii<arr[i].length; ii++) { if (Array.isArray(arr[i][ii])) { for (var iii=0; iii<arr[i][ii].length; iii++) { for (var iiii=0; iiii<arr[i][ii][iii].length; iiii++) { if (Array.isArray(arr[i][ii][iii])) { flat.push(arr[i][ii][iii][iiii]); } else { flat.push(arr[i][ii][iii]); } } } } else { flat.push(arr[i][ii]); } } } else { flat.push(arr[i]); } } } // [1, 2, 3, 4] 

What works in principle, but hard for both reading and understanding. Moreover, this only works when the number of nested arrays is known. And in general, you can imagine what debazhit is all this mess (even now it seems that I have put too much i).

Use reduce.

Fortunately, JavaScript has a couple of methods to make our code clearer and simpler. One of these methods is reduce (). And it will all look like this:

 var flat = arr.reduce(function(done,curr){ return done.concat(curr); }, []); // [ 1, 2, 3, [ [ 4 ] ] ] 

It turned out much less code, but we miss some (in our example, one) nested arrays. Let's step by step analyze how reduce () works and see what it does after all to fix it.

Array.prototype.reduce ()

The reduce () method applies a function to the battery and each value of the array (from left to right), reducing it to one value. ( MDN )

It is not as difficult as it seems. Let's talk about reduce () as something outside the work of the developer. Meet this is Adam. Adam's main function is to take apples from a pile, wash them, and then place them one by one in the basket. This basket of shiny apples is designed to be delicious apple pies. This is a very important job.

Apples + Human effort = Pie. Do not confuse the formula with the recipe for apple-human pie, it is not so tasty.

In the example above, a bunch of apples is our arr array. The basket is a done variable, a battery. The initial value of done is an empty array, which we see as [] the last parameter of our reduce (). The apple that Adam is currently washing is curr (from current). As soon as Adam finishes washing the current apple, he puts it in the basket (we do this with .concat ()). When the mountain of apples ends, Adam gives the basket of clean apples to us and goes home to his cat.

Use reduce () recursively to refer to nested arrays.

Well, according to the result of Adam's work, we have a basket of clean apples and everything seems to be excellent. But we still need to deal with these nested arrays. Returning to our analogy: suppose that some apples were so good that they were packed in separate boxes even when sold. Inside each box there may be more apples and more boxes containing apples and smaller boxes.


Pretty, slightly skewed apples just want to be loved / eaten and.

Here is what we want from our apple-processing function / Adam:

1. If a pile of apples is a pile of apples, then take an apple from a pile.
2. If what you took is an apple, then mine it and put it in the basket.
3. If what you took is a box, then open the box. If the apple in the box go to step 2.
4. If the box is another box, then go to step 3.
5. When there is no trace of the pile of apples, give us the basket.
6. If a bunch of apples are not a bunch of apples, then give it away, whatever they are.

The recursive function with reduce () will look like this:

 function flatten(arr) { if (Array.isArray(arr)) { return arr.reduce(function(done,curr){ return done.concat(flatten(curr)); }, []); } else { return arr; } } // [ 1, 2, 3, 4 ] 

Patience and I will explain everything.

Recursion

Function actions followed by a call to itself. Recursion is used to solve problems that contain smaller problems. The recursive function, as a rule, accepts two attributes: the base register (end of recursion) or the recursive register (the recursion continues). ( MDN )

If you look at our code above, you will see that flatten () appears twice. The first time he appears, he tells Adam what to do with a bunch of apples. The second time, he tells him what to do with what he is holding now, giving instructions if this is an apple and if this is not an apple. It should be noted that these instructions are a repetition of the original instructions with which we started - and this is recursion.

For clarity, let us analyze everything line by line:

1. function flatten (arr) { - we call our common function and indicate that it will take the argument arr.
2. if (Array.isArray (arr)) { - we check if the resulting array is.
3. return arr.reduce (function (done, curr) { - if the previous line returns true and the argument is an array you pass it to reduce () - this is our recursive register.
4. return done.concat (flatten (curr)); - an unexpected plot twist! The function that we call is the same function we are in now. In short: start over from the top.
5. }, []); - we tell our reduce function to start with an empty accumulator (done) and put what the function returns exactly in it.
6. } else { - this resolves those cases when string 2 returns false, that is, when the argument is not an array.
7. return arr; - to return something that arr would not be equal to (presumably a clean apple). This is already on the base register, which takes us out of recursion.
8. } - completion of the else block.
9. } - end of the common function.

And we are done! We have moved from a 24-line, 4-layer-nested for loop to a more concise and concise 9-line recursive solution. Reduce and recursion may seem complicated at first, but these are valuable tools that will save you a lot of effort in the future as soon as you understand them.

And don't worry about Adam, our non-working developer. He received so much attention after this article that he opened his own AI-controlled apple pie factory. He is very pleased.

+1 you, if you expected a joke about Adam's Apple.

---

This article risks stating obvious things. But the question should be asked: “Obvious for whom?”.

For the first time I am translating an article, from that I will be grateful for any changes, corrections and indication of defects.

• Original article. Vicky Lai's Blog
• MDN