Exercise 2.13: Recursion A useful feature of user-defined functions is recursion, the ability of a function to call itself. For example, consider the following definition of the factorial n ! of a positive integer n : n!={1n(n1)!ifn=1,ifn>1. This constitutes a complete definition of the factorial which allows us to calculate the value of n ! for any positive integer. We can employ this definition directly to create a Python function for factorials, like this: def factorial (n): if n=1: return 1 else: return n*1actorial (n1) Note how, if n is not equal to 1 , the function calls itself to calculate the factorial of n1. This is recursion. If we now say "print (factorial (5))" the computer will correctly print the answer 120. a) We encountered the Catalan numbers Cn previously in Exercise 2.7 on page 46 . With just a little rearrangement, the definition given there can be rewritten in the form Cn=1n+14n2Cn16ifn=0ifn>0. Write a Python function, using recursion, that calculates CN. Use your function to calculate and print C100 - b) Euclid showed that the greatest common divisor g(m,n) of two nonnegative integers m and n satisfies g(m,n)={mg(n,mmodn)ifn=0,ifn>0. Write a Python function g(m,n) that employs recursion to calculate the greatest common divisor of m and n using this formula. Use your function to calculate and print the greatest common divisor of 108 and 192. Comparing the calculation of the Catalan numbers in part (a) above with that of Exercise 2.7, we see that it's possible to do the calculation two ways, either directly or using recursion. In most cases, if a quantity can be calculated without recursion, then it will be faster to do so, and we normally recommend taking this route if possible. There are some calculations, however, that are essentially impossible (or at least much more difficult) without recursion. We will see some examples later in this book