Question

1. Recursion is ususally where a function calls itself; (another example of recursion is where function A calls function B, and B calls C and C calls A, creating a loop in the calls). Some problems are most naturally solved recursively, such as writing the factorial function, or finding all the perumutations of a sequence, or checking if a string is a palindrome. Since those examples were done in class, here we will give you a toy example, which normally would not be solved recursively, but which illustrates the process. Write a recursive function to add a positive integer b to another number a, add(a, b), where only the unit 1 can be added, For example add(5, 9) will return 14. The pseudocode is: # Base case: if b is 1, you can just return a + 1 # General case: otherwise, return the sum of 1 and what is returned by adding a and b - 1.

2. Here is another toy recursion example, but with less guidance. Write a function log2(x), which gives an integer approximation of of the log base 2 of a positive number x, but it does so using recursion. Use a base case where you return 0 if x is 1 or less. In the general case, add 1 to the answer and divide x by 2. (This is purposely vague so you can figure it out yourself.)

3. Write a recursive function reverse(sentence) for reversing a sentence. For example, reverse('Who let the dogs out?') will return '?tuo sgod eht tel ohW'. The idea is to remove the frst or last letter, reverse the shortened sentence, and then combine the two parts.

4. Write a recursive function power(x, n), where n is 0 or a postive integer. For example, power(2, 10) will return 1024. Write a suitable base case, and for the general case use the idea that x^n = x * x^n-1 .

Answer 1

def add(a, b):

if (b == 1):

return a + 1

return 1 + add(a, b-1)

def log2(n):

if (n <= 1):

return 0

return 1 + log2(n//2)

def reverse(s):

str = ""

for i in s:

str = i + str

return str

def power(x, y):

if (y == 0):

return 1

elif (int(y % 2) == 0):

return (power(x, int(y / 2)) * power(x, int(y / 2)))

else:

return (x * power(x, int(y / 2)) * power(x, int(y / 2)))

1 def add(a, b): if (b == 1): return a + 1 return 1 + add(a, b-1) def log2(n): if (n == 1): return return 1 + log2(n//2) def reverse(s): str = "" for i in s: str = i + str return str def power(x, y): if (y == 0): return 1 elif (int(y % 2) == 0): return (power(x, int(y / 2)) * power(x, int(y / 2))) else: return (x * power(x, int(y / 2)) * power(x, int(y / 2)))