[SPOILER] Simple but slow recursive solution to QOTW #23

I'll just note in addition to this solution that another way to
calculate Catalan numbers (aside from what I posted before) is given
by

  sub catalan {
    my $n=shift;
    my $ret=0;
    for my $i (1..$n) {
      $ret += catalan($i-1) * catalan($n-$i);
    }
    return $ret;
  }

It should be obvious without running it that the program below
therefore produces at the very least the correct number of lines.
(well, when the kernel doesn't kill it for sucking up too much memory)

#! /usr/bin/perl

use warnings;
use strict;

# A string of balanced parentheses is either the empty string
# or a string of the form "($a)$b", where $a and $b are strings
# of balanced parentheses.
#
# That statement is essentially my program - the rest is accounting
# and perl syntax.

sub parensList {
  # Given n, return a list of all possible balanced paren strings
  # with that many pairs of parentheses.
  my $n = shift;

  if (0 == $n) { return (""); }

  my @ret = ();
  for my $i (1..$n) {
    my @a = parensList($i - 1);
    my @b = parensList($n - $i);
    for my $a (@a) {
      for my $b (@b) {
        push @ret, "($a)$b";
      }
    }
  }
  return @ret;
}

# Only starts to make a visible difference for n > 10
use Memoize;
memoize('parensList');

die "Usage: parens.pl number" if 1 != @ARGV;

my $ngiven = shift() + 0;

die "Very funny" if $ngiven < 0;

print "$_\n" for parensList($ngiven);

__END__