Several of the functional languages have gone to some effort to have the compiler recognize when recursion can be done by a loop instead. Perl does not. However recognizing that for yourself can be useful. When you can do it it is generally faster, more flexible, etc.

The following code is a native Perl version of what is already done by the UNIVERSAL::isa() method. It is a method that tells whether one class inherits from another. I have implemented this search of a tree-like inheritance structure without recursion by using an array as a stack. (As opposed to having a stack of function calls.)

Try to write a recursive version of the same. Don't forget the pruning of packages that you have already seen in this call to the method (in case there is a circular inheritance path!), and the inclusion of the special case of UNIVERSAL that everything inherits from.

Note that strict 'refs' are turned off. This is the only construct that I have seen where I did not think doing this was a mistake, trying to access a global in your caller's package.

sub isa {
    my $obj = shift;
    my $base = ref($obj) || $obj;
    my $class = shift;
    my %is_seen;
    my @pkgs = ("UNIVERSAL", $base);
    no strict 'refs';
    while (scalar @pkgs) {
        my $pkg = pop @pkgs;
        return 1 if ($pkg eq $class);    # Found it!
        next if exists $is_seen{$pkg};   # Already processed this one
        ++$is_seen{$pkg};                # Mark this package seen
        push @pkgs, @{"${pkg}::ISA"};    # Append what this inherits f
+rom
    }
    # Searched the inheritance tree, failed to find it, so...
    return 0;
}
[download]