JavaScript array recursion without generators

Question

How would one solve the following problem without Generators? I came across something like this in a project I'm working on that requires deep iteration in pairs. I've only been able to solve it with Generators.

nums is a sample input. The input is an array of arbitrary length made up of integers and other such arrays of arbitrary depth.

Iterate over nums in pairs of [beforeNum, nextNum]. This means that the first pair's first value should be null ([null, 1]). The second pair should be [1, 2], and so on. The final pair should be [10, 11].

Ultimately, my actual goal was to be able to get the nth individual "atom", regardless of how many levels deep it is. For example, get(nums, 6) would be 7.

const nums = [1, [2, 3, [4, [5, 6], 7], [8, 9, [10], 11]]];

Edit Figured it out with @hugomg's help. When I dove in, it turns out that the fact that I was actually implementing this with something much different than plain arrays was getting in my way. The solution's actually super straightforward: https://gist.github.com/jclem/fbd44c43cb175dbf880e

Is nums a sample input? Are inputs always a pair at any depth? — f1yingbanana
– f1yingbanana, Commented May 16, 2015 at 2:12

hugomg · Accepted Answer · 2015-05-16 02:20:38Z

1

We can solve your problem by doing a simple traversal over the tree by keeping a "prev" variable as we go along. Its just a matter of writing a simple recursion:

function iterate(tree, onNum){

    var prev = null;

    function go(x, onNum){
       if(x instanceof Array){
         // If you are using a library that provides
         // an isArray function it can be more accurate than this.
         for(var i=0; i<x.length; i++){
             go(x[i], onNum);
         }
       }else{
         onNum(prev, x);
         prev = x;
       }
    }

    go(tree, onNum);
}

var myTree = [1, [2, 3, [4, [5, 6], 7], [8, 9, [10], 11]]];
iterate(myTree, function(prev, curr){
    console.log(prev, curr);
});

No need to use generators here. Generators only help if you need to make your iterator into an external iterator that you can "pause". For example, if you need to iterate over two of these trees in parallel. For your current problem using an internal iterator and some recursion is fine.

edited May 16, 2015 at 2:20

answered May 16, 2015 at 2:16

hugomg

70.4k30 gold badges168 silver badges257 bronze badges

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

14 Comments

clem Over a year ago

Of course. I'm not sure why I had so much trouble with this, but this makes perfect sense. I'm curious how this could be modified to allow for fetching the nth pair.

clem Over a year ago

Oh, it's just a simple countdown that's passed in to each iteration.

hugomg Over a year ago

update a counter together with the "prev". To "get out" as soon as you find the result you want if more tricky. You can make all the functions return a boolean and exit immediately if a recursive call goes false or you can go for the hacky way and raise an exception

hugomg Over a year ago

that said, it might be cleaner to refactor this into a flattening function that converts the tree into an array. Then all the operations you want become much easier

clem Over a year ago

That said, what's difficult to get right is that fact that I essentially need to iterate over these pairs in a loop and do something each time. I'm actually using generators because I can just do this in a for loop using something like this: gist.github.com/jclem/358345e4c40d6cc7ea2b

|

Collectives™ on Stack Overflow

JavaScript array recursion without generators

1 Answer 1

14 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

14 Comments

Your Answer

Sign up or log in

Post as a guest

Related