http://www.perlmonks.org?node_id=458789


in reply to Recursively-generated Iterators

Here's another iterator solution that avoids the recursion altogether. There are three differences:

All three of these can certainly be fixed, but I wanted to keep the code clear.
sub choose_n_iter { my @todo = [ shift, [ @_ ], [] ]; return sub { while ( @todo ) { my ( $n, $pool, $tally ) = @{ shift @todo }; return $tally if $n == 0; next if @$pool == 0; my ( $first, @rest ) = @$pool; push @todo, [ $n - 1, \@rest, [ @$tally, $first ]], [ $n , \@rest, $tally ]; } return; }; }
And here is a more effecient version:
sub choose_n_iter { my @todo = [ shift, [ @_ ], [] ]; return sub { while ( @todo ) { my ( $n, $pool, $tally ) = @{ shift @todo }; return $tally if $n == 0; return [ @$tally, @$pool ] if $n == @$pool; next if @$pool == 0; my ( $first, @rest ) = @$pool; push @todo, [ $n - 1, \@rest, [ @$tally, $first ]]; push @todo, [ $n , \@rest, $tally ] if @res +t; } return; }; }
Thanks goes out to HOP for the recursion-to-iterator help.

Replies are listed 'Best First'.
Re^2: Recursively-generated Iterators
by Roy Johnson (Monsignor) on May 23, 2005 at 15:57 UTC
    Your solution is more traditional. It does essentially the same thing as mine — delaying evaluation of later elements until they're needed — by keeping an explicit stack (or what should be a stack, but you seem to be using it as a queue, which explains the different order of return values). You note that it "avoids recursion altogether", but that's not really a legitimate goal. Recursion is not a bad thing in and of itself. It is often a very helpful thing.

    The reason I think my solution is an improvement is that it saves you the trouble of manipulating a stack, and allows the iterative solution to more closely resemble the recursive one. In a word: simplicity. You can follow a foolproof recipe, and in five or ten minutes have an iterator that returns exactly the same set as the recursive one. Same order, same structure, same arguments. Here's the recipe (this is new since my original post):

    1. Empty-set return values are replaced by empty subs
    2. Explicit (non-recursing) return values are assigned to an array; the iterator will be a sub that shifts that array
    3. A list of return values that includes recursive calls is replaced by a list of sub-wrapped iterators (wrapping the iterator calls in subs delays their evaluation), the iterator will be a sub that shifts its way through that list, unwrapping iterators until it finds one that returns something.
    4. See the rewrite of iter_choose_n (at the end of this post) for what to do when you have to accumulate data with a recursive call, as choose_n does (but Hanoi doesn't).
    That last is a little complicated to describe in words, so I'll demonstrate with Towers of Hanoi.

    Rewriting iter_choose_n to work with the boilerplate:


    Caution: Contents may have been coded under pressure.