Catalan Numbers Program $($version $1)(15$ points$)$

Given here is an algorithm to compute the $$

$$ Catalan number.

CATALAN$()$

$=01$

$=0$

$=1$

$=+$ CATALAN$(1)$ CATALAN$()$

$$

Write a program in either Java $17$ or later $($called CN$1.$java$)$ or Python $3\mathrm{.}11$ or later $($called cn$1.$py$)$ that:

$$ implements the method CATALAN given in the above pseudocode;

$$ contains a main method that computes and prints the first $21$ Catalan numbers, that is$,$ for the

values $=0$ to $20.$ Each output line should contain the value of $$ and the $$

$$ Catalan number.

To check whether your code is working correctly, compute the first few Catalan numbers by hand and

compare the results to your program$$s output.

Catalan Numbers Program $($version $2)(15$ points$)$

Create a new program, called CN$2.$java or cn$2.$py$,$ that does the same thing as the program written for

the previous problem but that also counts the number of times the multiplication in the fifth line of the

pseudocode is done. I suggest using a global variable that is initialized in the main part of the program.

As above, the program should print the first $21$ Catalan numbers, but this time each print line will

contain $,$ the $$

$$ Catalan number, and the number of multiplications performed.