A useful feature of user-defined functions is recursion, the ability of a functi

Question

A useful feature of user-defined functions is recursion, the ability of a function to call itself. Foir example, consider the following definition of the factorial n! of a positive integer n: n x (n-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 functiorn for factorials, like this: def factorial (n): If n=-1: return 1 else: return n*factorial (n-1) Note how, if n is not equal to 1, the function calls itself to calculate the factorial of n -1. 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 Cn4n - 2 If n > 0.

Explanation / Answer

Part(a) Solution

def catalan(n):
   if n == 0:
       return 1
   else:
       return ((4*n-2)*catalan(n-1))/(n+1)   

#catalan(100) comes out to be 896519947090131496687170070074100632420837521538745909320

Part(b) Solution

def gcd(m, n):
   if n == 0:
       return m
   else:
       return gcd(n, m%n)

#gcd(192,108) comes out to be 12

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.