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;
}
[download]

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; },
   );
}
[download]

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); } : (),
   );
}
[download]

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;
   };
}
[download]

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");
}
[download]