How to iterate over arrays of arrays n level deep without recursion?

Question

I have something like:

[ {}, {children:[{}, {}]} , {} ]  #each element cane be any level deep

and want to iterate over it without recursion. Just to test performance benefits. Any help?

Well, no, I don't think it's possible without recursion. But the true question is: why should you do this without recursion? — Niccolò Campolungo
– Niccolò Campolungo, Commented Jul 19, 2013 at 20:12
I implemented with recursion and it works well, but manager suggested to implement via iteration as it might be faster. So trying to profile the two and see. This could be for large data set so there might be a significant difference — dchhetri
– dchhetri, Commented Jul 19, 2013 at 20:14
I am not totally sure about it, but I don't think you can do that with iteration, because if you write n deep iterations and you get an object which is n+1 deep your function wouldn't work well(it would leave the last level unparsed). Say that to your manager :P — Niccolò Campolungo
– Niccolò Campolungo, Commented Jul 19, 2013 at 20:16
also it sounds like your manager is trying to prematurely optimize — Justen Martin
– Justen Martin, Commented Jul 19, 2013 at 20:17

Eugen Rieck · Accepted Answer · 2013-07-19 20:28:59Z

1

Every resursive function can be shortcutted into a function, that keeps its own stack - the question is: Is it faster? I guess not.

What I mean here is something like (in pseudo-code)

function flatten(something) {
  var ping=[];
  var pong=[];
  repeat {
    if (ping is empty) {
      if (something is empty) break;
      else ping.prepend(something.shift());
    }

    var element=ping.shift();
    if (element has children)
      foreach (child of element in reverse order) ping.prepend(child);
    else
      pong.append(element);
  }

  return pong;
}

calling flatten(your_input_object) will result in a "naive humanlike enumeration" list of its entries

answered Jul 19, 2013 at 20:28

Eugen Rieck

65.6k10 gold badges75 silver badges97 bronze badges

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

1 Comment

dchhetri Over a year ago

cool cool, yea in this case we flatten then iterate whereas in recursive we iterative as we go. So recursion might be faster, I would assume

user2600691 · Accepted Answer · 2013-07-19 20:16:58Z

0

I may be wrong, but if you're able to check if there is a following element in the array, can you write a nested while loop?

answered Jul 19, 2013 at 20:16

user2600691

1

Collectives™ on Stack Overflow

How to iterate over arrays of arrays n level deep without recursion?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related