No, this isn't true, prototypes are not needed for recursive subroutine calls.The typical example of recursive routines is the calculation of the factorial of a number, which may be coded this way:

#!/usr/bin/perl

use strict;
use warnings;

my $input = shift;
chomp $input;
print factorial($input);

sub factorial {
    my $val = shift;
    return 1 if $val == 0 or $val == 1;
    return $val * factorial($val - 1);
}
[download]

As you can see, no prototype needed. Prototypes can be useful for some advanced constructs, but, as a beginner, just don't use them, at least until you are no longer a beginner and you really know what they are and what they really do.