No recursion needed. Just keep all the possible paths and extend them $length - 1 times:

#!/usr/bin/perl
use warnings;
use strict;

my $length = 3;

my %calls = ( f1 => ['f2'],
              f2 => [qw[f3 f4]],
              f3 => [],
              f4 => ['f5'],
              f5 => [],
            );

my @adepts = map [$_], keys %calls;
for (1 .. $length - 1) {
    @adepts = map {
        my $list = $_;
        map [@$list, $_], @{ $calls{ $list->[-1] } };
    } @adepts;
}

{   local $" = '->';
    print "@$_\n" for @adepts;
}
[download]