2

I want to create an Iterator in Java (i.e. support hasNext() and next() calls). However, the thing I'm iterating is generated recursively. I want to be able to create this Iterator without having to generate the values beforehand and storing them. Instead, the next() call should get the next value that the recursion outputs, and hasNext() should check that the recursion is not yet done.

Is there a standard pattern for doing this?

Edit: I think a Python yield in a recursive function is the functionality I'm looking for. Not sure how to do it in Java though.

rococo
  • 2,280
  • 2
  • 22
  • 37
  • Check out my code [here](https://stackoverflow.com/questions/55190980/how-to-do-a-cyclic-doubly-link-list-add-method-in-java/55191433#55191433). May be this is what you are looking for, if not then at least could offer some hints. – Rahul R. Mar 21 '19 at 19:13
  • 1
    Can you show an example of the recursive algorithm? Using iterators it's often possible to convert a recursive algorithm into an iterative one by retaining the state between calls to `next()`. – Alnitak Mar 21 '19 at 19:59
  • I figured out an iterative solution to my specific problem: I was trying to generate all subsets of a certain size for a given set. I do this iteratively now by incrementing a set of indices on the original set. I'll leave the question open though, since I think there are definitely algorithms where it's difficult to get an iterative solution. – rococo Mar 21 '19 at 20:31
  • 1
    See e.g.http://jdoodle.com/a/15tZ, where I've generated an O(1) algorithm using iterators to generate each member of the Fibonacci sequence. – Alnitak Mar 21 '19 at 20:32
  • 1
    https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration – Alnitak Mar 21 '19 at 20:33

0 Answers0