# Recursive function Catalan triangle

I'm trying to learn how to build a recursive function. However, I'm not sure to understand how to set a "limit".

Here is what I'm trying to make. I want a function that gives me the i,j number of the Catalan triangle. However, I have a recursion limit error. I never know how to set a limit. Is it with the 2 first values ? I thought my code was right, but it is obviously not.

Clear[catalan]
catalan[i, 0] = 1;
catalan[0, 1] = 0;

catalan[i_, j_] :=
catalan[i, j] = catalan[i - 1, j] + catalan[i, j - 1]
catalan[3, 2]


If you look at the error message given, you'll see that your algorithm eventually tries to evaluate something like catalan[-1019-1,2]. That's a clue to what's happening. Your algorithm doesn't provide any "cutoff" when we run off to the "left" of the triangle.

Also, catalan[i, 0] = 1 is probably not what you wanted, since i isn't a pattern. This is just giving a literal definition for catalan[i, 0].

Here is a walkthrough for what you might want:

• Define the initial case. You could do this very concretely with catalan2[0, 0] = 1, but we can also handle all of the elements at the "left edge" of the triangle:

catalan2[_, 0] = 1

• For the next bit, we'll look at the "body" of the triangle. We won't bother with anything that goes off to the right, so we'll apply a condition. It'll look something like this, catalan2[<args>] := <definition> /; a >= b. The /; bit is how we apply a condition.

catalan2[a_Integer?NonNegative, b_Integer?NonNegative] :=
catalan2[a - 1, b] + catalan2[a, b - 1] /; a >= b


Notice the constraints on the arguments. These aren't really necessary if we trust ourselves to always use integers, but they clarify the semantics. They also make it easier to define a default case (see next step). I skipped the memoization, for clarity.

• Now let's add a default. This allows us to avoid If in our definition, and it handles all of the "bad" cases.

catalan2[___] = 0


Okay, put it all together (and adding the memoization for fun):

Clear[catalan2];
catalan2[_, 0] = 1;
catalan2[a_Integer?NonNegative, b_Integer?NonNegative] :=
(catalan2[a, b] = catalan2[a - 1, b] + catalan2[a, b - 1]) /; a >= b;
catalan2[___] = 0

• Thank you for the detailed answer. The only part I'm not sure to understand is catalan2[___] = 0. It seems to keep only the number without the []. However, the doc talking about the blank sequence. I'm not so sure to fully understand that part. Dec 13, 2022 at 7:06
• Put simplistically, the pattern _ matches a single argument, the pattern __ matches a sequence of 1 or more arguments, and the pattern ___ matches a sequence of 0 or more arguments. So, catalan2[___] = 0 will match any expression with head catalan1 and any pattern of arguments whatsoever. So, this part of the definition is a catch-all. Dec 13, 2022 at 7:33
• DownValues are stored and checked in a particular order, and in this case this catch-all will be checked only after the previous two definitions. So, everything on the "outside" of the triangle will be 0. Also, malformed arguments (non-integers, fewer than 2 arguments, more than two arguments) will all just result in 0. Dec 13, 2022 at 7:33