2 things:
If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
# Compute Fibonacci numbers, straight from Memoize docs
use Memoize;
memoize('fib');
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
my $foo = fib(24);
Such a strategy stores the results of previous iterations for later use, so you only have to calculate each result once. Once you do, it's stored (behind the scenes) in a hash which reconstructs it on demand. This makes things much faster.
But more importantly, I would offer this verson of an answer as a possible contender. It's a one-liner, but of a different style:
sub fib{int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}
enjoy!