 Perl: the Markov chain saw PerlMonks

### Question about recursively generated iterators

by perlfan (Vicar)
 on Sep 21, 2007 at 14:56 UTC Need Help??

perlfan has asked for the wisdom of the Perl Monks concerning the following question:

I've been going over the posts and tutorials here on this subject, and I have made it to the point where I can code a very straightforward example of very simple recursion.
```#!/usr/bin/env perl
use strict;
use warnings;

sub recurse_factory {
my \$max = shift;
my \$number = shift;
if (\$number < \$max) {
return sub { return recurse_factory(\$max,\$number+1); }
} else {
return sub { print "done ... \$number\n"; };
}
}

my \$TIMES = 100;
my \$next = recurse_factory(100,0);
for (1..\$TIMES+1) {
\$next = \$next->();
}
However, I am trying to figure out how one may use this method (if at all) for a more complicated recursive algorithm. In essence what I'd like to do is find all acyclic paths in a digraph using the recursive depth first search method.

In otherwords, the recursion pattern looks more like the depth first traversal of a tree than a simple straight line like my simple example above. I am sure locked away in the great explanations I've found on this site is the key, but I need to be hit with a really big clue stick.

I think for this discussion, the recursive depth first traversal of a tree that returns a full root-to-leaf path would be an appropriate example...btw, I am assuming that this can be done with rgi's, but I could be wrong there, too.

TIA

Replies are listed 'Best First'.
Re: Question about recursively generated iterators
by ikegami (Patriarch) on Sep 21, 2007 at 15:52 UTC

I tried to see if I could find a generic way of transforming a recursive function into an iterator. I found a method that's can be applied rather mechanically.

Let's say your recursive function visits a tree in preorder. The following would be the a non-iterative solution:

```sub visit_preorder(&\$) {
my (\$visitor, \$node) = @_;
my (\$val, \$l, \$r) = @\$node;
\$visitor->() for \$val;
&visit_preorder(\$visitor, \$l) if defined \$l;
&visit_preorder(\$visitor, \$r) if defined \$r;
}

Change the visitor code to return \\$val; where \$val is the data to return from the iterator. return \@val; is also acceptable if you wish to return more than one value.

Break up the function where a recursive call is made. Return each block as a function as follows:

```sub visit_preorder {
my (\$node) = @_;
my (\$val, \$l, \$r) = @\$node;
return (
sub { return \\$val;                                    },
sub { return visit_preorder(\$l) if defined \$l; return; },
sub { return visit_preorder(\$r) if defined \$r; return; },
);
}

In this case, it can be simplified a little.

```sub visit_preorder {
my (\$node) = @_;
my (\$val, \$l, \$r) = @\$node;
return (
\\$val,
defined(\$l) ? sub { return visit_preorder(\$l); } : (),
defined(\$r) ? sub { return visit_preorder(\$r); } : (),
);
}

Now we just need an engine to drive this.

```sub make_iter {
my \$f = shift @_;
my @todo = \$f->(@_);
return sub {
while (@todo) {
my \$todo = shift @todo;
if (ref(\$todo) eq 'CODE') {
unshift @todo, \$todo->();
} elsif (ref(\$todo) eq 'ARRAY') {
return @\$todo;
} else {
return \$\$todo;
}
}
return;
};
}

Finally, an example caller.

```{
#      a
#     / \
#    b   e
#   / \   \
#  c   d   f

my \$tree = [
'a',
[
'b',
[
'c',
undef,
undef,
],
[
'd',
undef,
undef,
],
],
[
'e',
undef,
[
'f',
undef,
undef,
],
],
];

my \$iter = make_iter(\&visit_preorder, \$tree);
while (my (\$name) = \$iter->()) {
print(\$name);
}
print("\n");
}

This method can be used when a function has a loop, since loops can be implemented using recursion. This is great because it facilitates making iterators from functions where the call to the visitor is not at the end and from functions with multiple calls to the visitor.

For example, let's create a fibonacci generator. A simple implementation is:

```sub fibonacci {
my (\$visitor) = @_;
my (\$i, \$j) = (0, 1);
\$visitor->() for \$i;
for (;;) {
\$visitor->() for \$j;
(\$i, \$j) = (\$j, \$i+\$j);
}
}

Replace the loop with recursion.

```sub fibonacci {
my (\$visitor) = @_;
my (\$i, \$j) = (0, 1);
\$visitor->() for \$i;
_fibonacci(\$i, \$j);
}

sub _fibonacci {
my (\$visitor, \$i, \$j) = @_;
\$visitor->() for \$j;
_fibonacci(\$j, \$i+\$j);
}

Convert for make_iter.

```sub fibonacci {
my (\$i, \$j) = (0, 1);
return ( \\$i, sub { _fibonacci(\$i, \$j) } );
}

sub _fibonacci {
my (\$i, \$j) = @_;
return ( \\$j, sub { _fibonacci(\$j, \$i+\$j) } );
}

Try it out

```{
my \$iter = make_iter(\&fibonacci);
for (0..15) {
my (\$n) = \$iter->()
or last;
print("\$n ");
}
print("\n");
}
```0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
Very much appreciated, ikegami! This is very helpful.
Re: Question about recursively generated iterators
by Limbic~Region (Chancellor) on Sep 21, 2007 at 17:00 UTC
Thank you, yes I have. I prefaced this in the beginning of the question, but maybe I should have listed them explicitly. Your stuff actually got me started down this dark and scary road :)
perlfan,
Your stuff actually got me started down this dark and scary road :)

I am truly flattered. I can show you examples of both DFS and BFS iterators but they are not ones that I converted from a recursive algorithm. I almost never think of problems in terms of recursion. Probably why Haskell still eludes me.

Don't hesitate to /msg me with questions about something I have written, if you would like some examples, or if you would like me to write up a tutorial on something (assuming I am capable).

Cheers - L~R

Re: Question about recursively generated iterators
by artist (Parson) on Sep 21, 2007 at 15:13 UTC

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://640382]
Approved by philcrow
Front-paged by Old_Gray_Bear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (2)
As of 2022-09-26 19:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I prefer my indexes to start at:

Results (118 votes). Check out past polls.

Notices?