Problem 1 A. Consider the following recursive method. def foo1(n): if n == 2: return 1 else: return 3 * foo1(n – 1) What value is returned as a result of the call foo1(5)? Show the recursive calls generated. B. Consider the following recursive method. def foo2(n): if n > 0: print(n, end=’ ‘) foo2(n-1) What is the output of the call foo2(5) Problem 2 Make sure your code is readable and well-documented. Each function must also begin with a title block that describes the task of the function, input parameters and return value. Write a recursive function that takes a string as an input and returns the reverse of the string. 2. Write a recursive function rec_string that produces the output shown below for the corresponding function calls. Write a main function to test the function. Method call rec_string(‘abcde’), will produce the following output: * e de cde bcde abcde Method call rec_string(‘abc’), will produce the following output: * c bc abc 3. Write a recursive function for Euclid's algorithm to find the greatest common divisor (gcd) of two positive integers. gcd is the largest integer that divides evenly into both of them. For example, the gcd(102, 68) = 34. You may recall learning about the greatest common divisor when you learned to reduce fractions. For example, we can simplify 68/102 to 2/3 by dividing both numerator and denominator by 34, their gcd. Finding the gcd of huge numbers is an important problem that arises in many commercial applications. We can efficiently compute the gcd using the following property, which holds for positive integers p and q: If p > q, the gcd of p and q is the same as the gcd of q and p % q.
Problem 1
A. Consider the following recursive method.
def foo1(n):
if n == 2:
return 1
else:
return 3 * foo1(n – 1)
What value is returned as a result of the call foo1(5)? Show the recursive calls generated.
B. Consider the following recursive method.
def foo2(n):
if n > 0:
print(n, end=’ ‘)
foo2(n-1)
What is the output of the call foo2(5)
Problem 2
Make sure your code is readable and well-documented. Each function must also begin with a title block that describes the task of the function, input parameters and return value.
- Write a recursive function that takes a string as an input and returns the reverse of the string.
2. Write a recursive function rec_string that produces the output shown below for the corresponding function calls. Write a main function to test the function.
Method call rec_string(‘abcde’), will produce the following output:
*
e
de
cde
bcde
abcde
Method call rec_string(‘abc’), will produce the following output:
*
c
bc
abc
3. Write a recursive function for Euclid's
If p > q, the gcd of p and q is the same as the gcd of q and p % q.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
