This is the sort of situation that'd be perfect for coroutines, but we'll have to wait 'til perl6 for native support of that. In the mean time you need to unroll your recursion, which involves building a stack to iterate over e.g

use strict;

use File::Spec::Functions 'catfile';
use IO::Dir;

sub _dircnts {
  my $dir = shift;
  my $do  = IO::Dir->new($dir) or die "Couldn't open '$dir': $!";
  return
    map catfile($dir, $_),
    grep !/^\.\.?$/, $do->read;
}

sub rec_readdir {
  my $dir  = shift;
  my @cnts = _dircnts $dir;

  my $iter; $iter = sub {
    my $f = pop @cnts;
    return unless defined $f;

    push @cnts, _dircnts $f
      and return &$iter
        if -d $f;

    return $f;
  };

  return $iter;
}

my $di = rec_readdir(shift);
while(my $file = &$di) {
  # do stuff here
}
[download]

That basically builds up a listing of a given directory and pushes it on a stack, the stack is then iterated through and if a directory is found then its contents are pushed on the stack and so on.

Although if you're actually iteratively walking a directory tree then File::Find::Rule will do a much more reliable job (as it in turn uses File::Find) and is oh-so useful :)