Provided by: libsub-recursive-perl_0.05-1_all 
NAME
Sub::Recursive - Anonymous memory leak free recursive subroutines
SYNOPSIS
use Sub::Recursive;
# LEAK FREE recursive subroutine.
my $fac = recursive {
my ($n) = @_;
return 1 if $n < 1;
return $n * $REC->($n - 1);
};
# Recursive anonymous definition in one line, plus invocation.
print recursive { $_[0] <= 1 ? 1 : $_[0] * $REC->($_[0] - 1) } -> (5);
# Experimental interface
use Sub::Recursive qw/ mutually_recursive %REC /;
my ($odd, $even) = mutually_recursive(
odd => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
);
DESCRIPTION
Recursive closures suffer from a severe memory leak. "Sub::Recursive" makes the problem go
away cleanly and at the same time allows you to write recursive subroutines as expressions
and can make them truly anonymous. There's no significant speed difference between using
"recursive" and writing the simpler leaking solution.
The problem
The following won't work:
my $fac = sub {
my ($n) = @_;
return 1 if $n < 1;
return $n * $fac->($n - 1);
};
because of the recursive use of $fac which isn't available until after the statement. The
common fix is to do
my $fac;
$fac = sub {
my ($n) = @_;
return 1 if $n < 1;
return $n * $fac->($n - 1);
};
Unfortunately, this introduces another problem.
Because of perl's reference count system, the code above is a memory leak. $fac references
the anonymous sub which references $fac, thus creating a circular reference. This module
does not suffer from that memory leak.
There are two more reasons why I don't like to write recursive closures like that: (a) you
have to first declare it, then assign it thus requiring more than a simple expression (b)
you have to name it one way or another.
The solution
This module fixes all those issues. Just change "sub" for "recursive" and use
"$REC->(...)" for the recursive call:
use Sub::Recursive;
my $fac = recursive {
my ($n) = @_;
return 1 if $n < 1;
return $n * $REC->($n - 1);
};
It also makes it easy to pass it directly to a subroutine,
foo(recursive { ... });
just as any other anonymous subroutine.
EXPORTS
If no arguments are given to the "use" statement $REC and "recursive" are exported. If any
arguments are given only those given are exported. ":ALL" exports everything exportable.
$REC - exported by default
$REC holds a reference to the current subroutine inside subroutines created with
"recursive". Don't ever touch $REC inside or outside the subroutine except for the
recursive call.
"recursive" - exported by default
"recursive" takes one argument and that's an anonymous sub defined in the same package as
the call to "recursive" is in. It's prototyped with "&" so bare-block calling style is
encouraged.
recursive { ... }
The return value is an anonymous closure that has "$REC->(...)" working in it.
%REC
This is an experimental part of the API.
%REC holds the subroutine references given to &mutually_recursive, with the same keys.
Don't ever touch %REC inside or outside the subroutines except for the recursive calls.
"mutually_recursive"
This is an experimental part of the API.
"mutually_recursive" works like "recursive" except it takes a list of key/value pairs
where the key names are the names used for the keys in %REC and the values are the
subroutine references. The return values in list context are the subroutine references,
ordered as given to "mutually_recursive".
my ($odd, $even) = mutually_recursive(
odd => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
);
BUGS
If you follow the rest of the manual you don't have to read this section. I include this
section anyway to make debugging simpler.
$REC is a package global and as such there are some gotchas. You won't encounter any of
these bugs below if you just use
recursive { ... }
and don't mention $REC outside of such an expression. In short: it's quite unlikely you'll
get bitten by any of these bugs.
"my" and "our"
Don't declare $REC with "my". That'll make $REC mean your lexical variable rather than
the global that "Sub::Recursive" uses.
Don't declare $REC with "our". In particular, problem arise the "our" scopes over
several packages. If you do
package Foo;
use Sub::Recursive;
our $REC;
# Below, in the same file:
package Bar;
my $fatal = recursive { $REC->() };
$REC in $fatal will be using the value of $Foo::REC but "Sub::Recursive" has no way of
knowing that and will think you use $Bar::REC.
If you for some reason need to have $REC declared you can as a last resort get around
both these issues by fully qualifying $REC to the package in which the subroutine is
created.
package Foo;
use Sub::Recursive;
my $REC; # Bad.
my $fatal = recursive { $Foo::REC->() }; # Still works.
Subroutine reference defined in another package
This is a really far out edge case.
If the subroutine reference given to "recursive" is defined in another package than
the call to "recursive" in it then it won't work.
package Foo;
my $foo = sub { $REC->() };
package Bar;
use Sub::Recursive;
my $bar = &recursive($foo); # Won't work.
The subroutine referenced by $foo is using $Foo::REC but "recursive" thinks it's using
$Bar::REC. Note that you have to circumvent prototyping in order to encounter this
bug.
Why you'd want to do this escapes me. Please contact me if you find a reason for doing
this.
EXAMPLE
Some algorithms are perhaps best written recursively. For simplicity, let's say I have a
tree consisting of arrays of array with arbitrary depth. I want to map over this data
structure, translating every value to another. For this I might use
my $translator = recursive {
[ map { ref() ? $REC->($_) : $translate{$_} } @{$_[0]} ]
};
my $bar = $translator->($foo);
Now, a tree mapper isn't perhaps the best example as it's a pretty general problem to
solve, and should perhaps be abstracted but it still serves as an example of how this
module can be handy.
A similar but more specialized task would be to find all men who share their Y chromosome.
# A person data structure looks like this.
my $person = {
name => ...,
sons => [ ... ], # objects like $person
daughters => [ ... ], # objects like $person
};
my @names = recursive {
my ($person) = @_;
return
$person->{name},
map $REC->($_), @{$person->{sons}}
} -> ($forefather);
This particular example isn't a closure as it doesn't reference any lexicals outside
itself (and thus could've been written as a named subroutine). It's easy enough to think
of a case when it would be a closure though. For instance if some branches should be
excluded. A simple flag would solve that.
my %exclude = ...;
my @names = recursive {
my ($person) = @_;
return if $exclude{$person};
return
$person->{name},
map $REC->($_), @{$person->{sons}}
} -> ($forefather);
Hopefully this illustrates how this module allows you to write recursive algorithms inline
like any other algorithm.
AUTHOR
Johan Lodin <lodin@cpan.org>
COPYRIGHT
Copyright 2004-2015 Johan Lodin. All rights reserved.
This library is free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
SEE ALSO
perlref