The following works:

#!/usr/bin/perl

use strict;
use warnings;

use Test::More tests => 5;
use Parse::RecDescent ();

my $p = Parse::RecDescent->new(<<'__END_OF_GRAMMAR__');

{
   use strict;
   use warnings;
}

parse    : rec /\Z/ { $item[1] }
rec      : POS_INT rec_list[ $item[1] ] { [ $item[0] => $item[2] ] }
rec_list : { $arg[0] == 0 ? [] : undef }
         | ELEM rec_list[ $arg[0]-1 ] { [ $item[1], @{$item[2]} ] }
POS_INT  : /\d+/
ELEM     : /\S+/

__END_OF_GRAMMAR__


ok($p->parse('0'));
ok($p->parse('1 foo'));
ok($p->parse('2 foo bar'));
ok(!$p->parse('1'));
ok(!$p->parse('1 foo bar'));
[download]

Changes:

• rec_list recursively builds a list from one element and a list. The terminating condition of the recursion is the count of items, which is passed as an argument to the rule.

• I added a check for end of "file" (/\Z/). This catches "1 foo bar". It's always good to check if you have leftover text to parse (unless you want to allow leftover text).

• I prefer <<'__END_OF_GRAMMAR__' over q{...} because it handles backslashes more intuitively.

• Your use strict and use warnings are in a different scope than the grammar. For them to apply to the grammar, you need to include them in the grammar.

• I renamed int to pos_int to make it clear that signs are not acceptable. A check on the numbers magnitude inside of rec wouldn't hurt.

• I uppercased tokens. It's just a style I use.

This is the same grammar as above, but with (yet-to-be-customized) error reporting:

my $p = Parse::RecDescent->new(<<'__END_OF_GRAMMAR__');

{
   use strict;
   use warnings;
}

parse     : rec eof { $item[1] }
eof       : /\Z/
          | <error>
rec       : POS_INT rec_list[ $item[1] ] { [ $item[0] => $item[2] ] }
rec_list  : rec_list_[ $arg[0] ]
          | <error>
rec_list_ : { $arg[0] == 0 ? [] : undef }
          | ELEM rec_list_[ $arg[0]-1 ] { [ $item[1], @{$item[2]} ] }
POS_INT   : /\d+/
ELEM      : /\S+/

__END_OF_GRAMMAR__
[download]