There shall be no else after return/die/croak. Ever!

sub leonardo{
    my $n = shift;
    if($n == 0 || $n == 1){
        return 1;
    }
    else{
        return leonardo($n-2)+leonardo($n-1)+1;
    }
}
[download]

SHould be rewritten to either

sub leonardo {
    my $n = shift;
    $n == 0 || $n == 1 and
        return 1;
    return leonardo ($n - 2) + leonardo ($n - 1) + 1;
    }
[download]

or using a ternary

sub leonardo {
    my $n = shift;
    $n == 0 || $n == 1 ? 1 : leonardo ($n - 2) + leonardo ($n - 1) + 1
+;
    }
[download]

with your personal preference to whitespace and indentation of course.

The else in an if is there to give alternative code in a control flow where the code after the if/else contruct is executed for both branches. As the if branch ends with a return statement, immediatly exiting the routine, the code after if/else is never executed and only written for the else branch making the code harder to read and maintain.