Misunderstanding Recursion

[Andrew_Levenson]

Last night I happened upon DigitalKitty's Recursion: The Towers of Hanoi problem, which opened my eyes to the world of recursion (thanks for that, by the way). Never had the thought occurred to me that I could call a loop from within that loop. So I revisited my old prime script with this new tool in hand.

After toying with it a bit, I gave it a go. Extremely fast for up to 1000. Then it started to slow down, which puzzled me. When doing up to one million (not a problem for previous versions) it got hung up around 700,000.

Why, oh why, fellow monks, does this script

$n=1; 
$lim=1000000;
print "2 ";
prime($n+=2);
sub prime{
    exit if $n>=$lim;
    for($i=3;$i<=sqrt($n);$i+=2){
        prime($n+=2) if $n/$i==int($n/$i);
    }
    print "$n ";
    prime($n+=2) if $n<$lim;
}

run so much slower than this script?

use strict;
use warnings;
for my $i(2..1000000){
    print "$i " if $i==2;
    my $even=0;
       my $notprime=0;
       my $j=$i/2;
   next if int($j)==$j;    
    my $n=$i**(1/2);
    for(3..$n){my $o=$i/$_;
    $notprime=1 if int($o)==$o;
    last if int($o)==$o;}
    print "$i " if $even==0 && $notprime==0;
}

From my (severely limited) point of view, it should run a lot faster/be more efficient than the latter. Is there some feature of recursion that I don't know about that is causing me to choke?

Thanks in advanced!