3
$\begingroup$

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]
$\endgroup$

1 Answer 1

5
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Dec 13, 2022 at 7:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – lericr
    Dec 13, 2022 at 7:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – lericr
    Dec 13, 2022 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.