Luckely, there's a module on CPAN that can help:

#!/usr/bin/perl

use strict;
use warnings;

use Algorithm::Graphs::TransitiveClosure qw /floyd_warshall/;

my $g;

while (<DATA>) {
    my ($from, $to) = split;
    $g -> {$from} -> {$to} = 1;
}

floyd_warshall $g;

while (my ($key, $value) = each %$g) {
    print "Recursion for function '$key'\n" if exists $g -> {$key} {$k
+ey};
}


__DATA__
aaa bbb
bbb ccc
bbb ddd
ccc ddd
ddd aaa
ddd eee
[download]

Abigail

Sadly, that's not good enough as a general approach. It only works on the static cases, not on ones that only show up dynamically. When you use this approach on some of those, it also rules out non-recursive stuff that has closed loops it will never actually follow. Those are potentially recursive but not actually recursive. Of course, those will also throw a pre-processor, so that is what you really need to detect here - the problem isn't really "recursion detection" at all. And with stack emulation that you might be able to do inside the toy language, you don't need to stay within the limits of the pre-processor anyway. (What is the toy language, by the way?) Here's an example of potential but non-actual recursion I came across once. You have a number of intercepting calls here and there, that drop status information into a sort of error handler. It reports the status, to console or to printer. But what if the anomaly shows up within console driving code or printer driving code? You make the calls have flags that indicate whether to output to console and/or to printer. That way you never get an error call handing its results on to the code that called it, so you avoid actual recursion - but the links between functions look recursive to a static analysis. Oh, my first thought on analysing the graphs was to see if the inverses of related matrices always existed; if there are loops, things related like the Leontiev matrix of economics don't always have inverses. PML.

Well, if you want to determine what can happen at runtime, and rule out the cases that will not happen, all you have to do is solve the halting problem. But you need something more complex than a Turing Machine to do that.

Abigail

package func;

use strict;

sub new {
    my $self = {};
    shift;
    $self->{CALLED} = [];
    $self->{MARK} = 0;
    $self->{NAME} = shift;
    bless $self;
    return $self;
}

sub call {
    my ($self, $called) = @_;
    push @{$self->{CALLED}}, $called;
}

sub mark {
    my $result = 0;
    my ($self, $mark, $current_chain) = @_;
    if ($self->{MARK} != $mark) {
        $self->{MARK} = $mark;
        my $called;
        foreach $called (@{$self->{CALLED}}) {
            push @{$current_chain}, $called->{NAME};
            $result |= $called->mark($mark, $current_chain);
        }
    } else {
        $result = 1;
        print(join("->", @{$current_chain})."\n");
    }
    pop @{$current_chain};
    $self->{MARK} = 0;
    return $result;
}

1;

func.pl:
use func;
use Data::Dumper;

use strict;

my %funcs;
while (<DATA>) {
    chomp;
    my ($calling, $called) = split(' ');
    if (!exists($funcs{$calling})) {
        $funcs{$calling} = new func($calling);
    }
    if (!exists($funcs{$called})) {
        $funcs{$called} = new func($called);
    }
    $funcs{$calling}->call($funcs{$called});
}

my $mark = 0;
my $func;
print "Bad calling chains:\n";
foreach $func (keys %funcs) {
    $mark ++;
    my $current_chain = [];
    push @{$current_chain}, $func;
    $funcs{$func}->mark($mark, $current_chain);
}
print "End of bad calling chains\n";

__DATA__
aaa bbb
aaa ccc
bbb ccc
ccc bbb
ddd aaa
ddd eee


testing result
Bad calling chains:
bbb->ccc->bbb
aaa->bbb->ccc->bbb
aaa->ccc->bbb->ccc
ccc->bbb->ccc
ddd->aaa->bbb->ccc->bbb
ddd->aaa->ccc->bbb->ccc
End of bad calling chains
[download]