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

Daniel Martin <[email protected]> writes:

> 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;
>   }

Of course, I left out the base case.  Insert a

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

at the appropriate point.

And it appears that my recursive solution is identical to Rod Adams's
'Nested' Routine.  My iterative solution bears something in common
with two of his other routines, but it's essentially on its own.

(And I like the approach taken by insert - hadn't thought of that -
though the %seen hash is doubtless brutal on memory for large n)