Just another Perl shrine PerlMonks

### Comment on

 Need Help??
Recursive algorithms are often simple and intuitive. Unfortunately, they are also often explosive in terms of memory and execution time required. Take, for example, the N-choose-M algorithm:
```# Given a list of M items and a number N,
# generate all size-N subsets of M
sub choose_n {
my \$n = pop;
# Base cases
return []   if \$n == 0  or \$n > @_;
return [@_] if \$n == @_;
# otherwise..
my (\$first, @rest) = @_;
# combine \$first with all N-1 combinations of @rest,
# and generate all N-sized combinations of @rest
my @include_combos = choose_n(@rest, \$n-1);
my @exclude_combos = choose_n(@rest, \$n);
return ( (map {[\$first, @\$_]} @include_combos)
, @exclude_combos );
}
Great, as long as you don't want to generate all 10-element subsets of a 20-item list. Or 45-choose-20. In those cases, you will need an iterator. Unfortunately, iteration algorithms are generally completely unlike the recursive ones they mimic. They tend to be a lot trickier.

But they don't have to be. You can often write iterators that look like their recursive counterparts — they even include recursive calls — but they don't suffer from explosive growth. That is, they'll still take a long time to get through a billion combinations, but they'll start returning them to you right away, and they won't eat up all your memory.

The trick is to create iterators to use in place of your recursive calls, then do a little just-in-time placement of those iterator creations.

So let's take a first stab at choose_n. First, our base cases are going to be subs that return whatever they were returning before, but after returning those values once, they don't return anything anymore:
```sub iter_choose_n {
my \$n = pop;
# Base cases
my \$once = 0;
return sub {\$once++ ? () : []} if \$n == 0  or \$n > @_;
my (\$first, @rest) = @_;
return sub {\$once++ ? () : [\$first, @rest]} if \$n == @_;
Apart from the iterator trappings, we've got essentially what we had before. Converting the map into an iterator involves some similar work, but the parallels are still pretty obvious. We exhaust the first iterator before turning to the second:
```    # otherwise..
my \$include_iter = iter_choose_n(@rest, \$n-1);
my \$exclude_iter = iter_choose_n(@rest, \$n);
return sub {
if (my \$set = \$include_iter->()) {
return [\$first, @\$set];
}
else {
return \$exclude_iter->();
}
}
We now have a recursively-defined iterator that wasn't a heck of a lot more complex than our original algorithm. That's the good news. The bad news is: it's still doubly recursive, O(2^N) in space and time, and so will take a long time to start generating data. Time for a little trick. Because we don't use \$exclude_iter until we've exhausted \$include_iter, we can delay defining it:
```    # otherwise..
my \$include_iter = iter_choose_n(@rest, \$n-1);
my \$exclude_iter;
return sub {
if (my \$set = \$include_iter->()) {
return [\$first, @\$set];
}
else {
\$exclude_iter ||= iter_choose_n(@rest, \$n);
return \$exclude_iter->();
}
}
}
Now our code is singly recursive, O(N) in space and time to generate an iterator, and that makes a big difference. Big enough that you probably won't need to go to the trouble of coming up with an O(1) truly iterative solution.

Of course, if you complete the iterations, eventually you will have generated those 2^N subs, and they'll clog up your memory. You may not be concerned about that (you may not be expecting to perform all that many iterations), but if you are, you can put a little code in to free up exhausted iterators:

```    # otherwise..
my \$include_iter = iter_choose_n(@rest, \$n-1);
my \$exclude_iter;
return sub {
if (\$include_iter and my \$set = \$include_iter->()) {
return [\$first, @\$set];
}
else {
if (\$include_iter) {
undef \$include_iter;
\$exclude_iter = iter_choose_n(@rest, \$n);
}
return \$exclude_iter->();
}
}
}
Update: See my response to Kelan for a recipe for conversion from recursion to iterator.

Caution: Contents may have been coded under pressure.

In reply to Recursively-generated Iterators by Roy Johnson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2017-08-17 18:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (290 votes). Check out past polls.

Notices?