# this function is not recursive; it is called once
# and returns with the subroutine calls it /would have/
# made had it be implicitly recursive

sub get_sub (param1,...,paramN)
  # shift params, which are are assumed to data stucts refs
  initialize @retsubs = ()
  if terminating condition FALSE
    # create/modify params used in recursive call
    initialize new _param1 to some value;
    ...
    initialize _paramN to some value;
    loop to get set of next subs for next level of recursion
      push "sub {return get_sub(_param1,...,paramN);})" onto @retsubs;
    end loop
  endif 
  return {substack=>@retsubs,retval1=>'somevalue'};
end get_sub

# initialize call stack with first set of subs to call
my @callstack = array of subs returned by get_sub(param1,...,paramN);

# now execute the call stack until it's been exhausted
while(@callstack) {
  pop next $sub off of @callstack;
  execute sub ref, $x = $sub->();
  push subs returned by get_sub(param1,...,paramN) onto @callstack;
end while

##</code><code>##

...
  return sub { my $arg1 = shift; my $arg2 = shift; ... ;};
...

##</code><code>##

  my @subrefs = ();
  # loop, push sub refs onto @subrefs
    push (@subrefs,sub { ... });
  # end loop
...
  return { subref => @subrefs, val1 => 1, val2 => 'abc' };
...

##</code><code>##

# make call
my $caller = get_sub(...);
# extract subrefs from the returned hash ref
my @subrefs = @{$caller->{subrefs}};
# push returned subs onto call stack
push(@callstack,@subrefs);

##</code><code>##

#!/usr/bin/env perl
use strict;
use warnings;
use FLAT::DFA;
use FLAT::NFA;
use FLAT::PFA;
use FLAT::Regex::WithExtraOps;
my $PRE = "abc&(def)*";
my $dfa = FLAT::Regex::WithExtraOps->new($PRE)->as_pfa->as_nfa->as_dfa->as_min_dfa->trim_sinks;
my $next = $dfa->new_acyclic_string_generator;
print "PRE: $PRE\n";
print "Acyclic:\n";
while (my $string = $next->()) {
  print "  $string\n";
}
$next = $dfa->new_deepdft_string_generator();
print "Deep DFT (default):\n";
for (1..10) {
 while (my $string = $next->()) {
   print "  $string\n";
   last;
  }
}
$next = $dfa->new_deepdft_string_generator(5);
print "Deep DFT (5):\n";
for (1..10) {
  while (my $string = $next->()) {
    print "  $string\n";
    last;
  }
}

##</code><code>##

PRE: abc&(def)*
Acyclic:
  deabfc
  deabcf
  dabcef
  dabefc
  dabecf
  daebfc
  daebcf
  abc
  adbcef
  adbefc
  adbecf
  adebfc
  adebcf
Deep DFT (default):
  deabfdcef
  deabfc
  deabcf
  deafbdcef
  deafbdecf
  deafbc
  deafdbcef
  deafdbefc
  deafdbecf
  dabcef
Deep DFT (5):
  defdefdefdefdeabfdcef
  defdefdefdefdeabfdcefdef
  defdefdefdefdeabfdcefdefdef
  defdefdefdefdeabfdcefdefdefdef
  defdefdefdefdeabfdcefdefdefdefdef
  defdefdefdefdeabfdefdcef
  defdefdefdefdeabfdefdcefdef
  defdefdefdefdeabfdefdcefdefdef
  defdefdefdefdeabfdefdcefdefdefdef
  defdefdefdefdeabfdefdcefdefdefdefdef

##</code><code>##

sub get_acyclic_sub {
  my $self = shift;
  my ($start,$nodelist_ref,$dflabel_ref,$string_ref,$accepting_ref,$lastDFLabel) = @_;
  my @ret = ();
  foreach my $adjacent (keys(%{$nodelist_ref->{$start}})) {
    $lastDFLabel++;
    if (!exists($dflabel_ref->{$adjacent})) {
      $dflabel_ref->{$adjacent} = $lastDFLabel;
      foreach my $symbol (@{$nodelist_ref->{$start}{$adjacent}}) { 
        push(@{$string_ref},$symbol);
      	my $string_clone = dclone($string_ref);
        my $dflabel_clone = dclone($dflabel_ref);
        push(@ret,sub { return $self->get_acyclic_sub($adjacent,$nodelist_ref,$dflabel_clone,$string_clone,$accepting_ref,$lastDFLabel); }); 
        pop @{$string_ref};
      }
    } 
 
  }
  return {substack=>[@ret],
          lastDFLabel=>$lastDFLabel,
          string => ($self->array_is_subset([$start],[@{$accepting_ref}]) ? join('',@{$string_ref}) : undef)};
}
sub init_acyclic_iterator {
  my $self = shift;
  my %dflabel = (); 
  my @string  = (); 
  my $lastDFLabel = 0; 
  my %nodelist = $self->as_node_list(); 
  my @accepting = $self->get_accepting();
  # initialize
  my @substack = ();
  my $r = $self->get_acyclic_sub($self->get_starting(),\%nodelist,\%dflabel,\@string,\@accepting,$lastDFLabel);
  push(@substack,@{$r->{substack}});
  return sub {
    while (1) {
      if (!@substack) {
        return undef;
      }
      my $s = pop @substack;
      my $r = $s->();
      push(@substack,@{$r->{substack}}); 
      if ($r->{string}) {
       return $r->{string};
      }
    }
  }
}

sub new_acyclic_string_generator {
  my $self = shift;
  return $self->init_acyclic_iterator();
}