Question

The functions are tested in the following main():

def recSum1(somelist):
    if len(somelist) == 1:
        return somelist[0]
    else:
        a = recSum1(somelist[:len(somelist)//2])
        b = recSum1(somelist[len(somelist)//2:])
        return a + b

def recSum2(somelist):
    if len(somelist) == 1:
        return somelist[0]
    else:
        return somelist[0] + recSum2(somelist[1:])

import random

def main():
    N = 100
    myList = [random.randint(-500, 500) for i in range(N)]

    print(myList)
    print("The sum of the numbers is: " + str(sum(myList)))
    print("The sum of the numbers using recSum1 is: " + str(recSum1(myList)))
    print("The sum of the numbers using recSum2 is: " + str(recSum2(myList)))

if __name__ == "__main__":
    main()

1. Using the recSum1() function as a template, create a recursive function that will find the minimum value of the values in a list. The minimum value is the smaller of minimums of the two halves. You will need to modify the main to test your new function.

2. Create a recursive function that will compute xⁿ, (x to the nth power) where n is an integer. If n is an integer, then the xⁿ can be defined as:

This means that, if you compute recursive x to the half of n, then the answer is that result times itself if n is even, or the answer is that result times itself times x if n is odd.

Answer 1

Problem 1:

The following is the code for above question. It involves the concept of divide and conquer where we can reduce the time complexity to log n.

def find_min(l,left,right,min): #here left and right indicates the positions of elements in the list
  if left==right:  #if left and right elements are equal
    if min>l[right]:
      min=l[right]
    return min
  if right-left==1:        
    if l[left]<l[right]:  # If the element at left is less than the element at right
      if min>l[left]:   
        min=l[left]
    else:
      if min>l[right]:  # If min is greater the element at the right of list
        min=l[right]
  mid=(left+right)//2  #mid is nothing but the element at half of the list
  a=find_min(l,left,mid,min) #find the min for the first half of the list
  b=find_min(l,mid+1,right,min) #find the min for the last half of the list
  if a>b: #compare minimum among a and b
    min=b
  else:
    min=a
  return min  #return min
l=[4,3,6,2,8,2,8]
find_min(l,0,len(l)-1,l[0])

Output and Screenshots:

Problem 2:

The following is the code for above question. It also involves the concept of divide and conquer.

def power(x,n):
  if n==0:  #if n is 0, return 1 i.e any number power 0 is 1
    return 1
  if x==0:  #if any number is 0, then result will be 0. i.e 0 power anything is 0
    return 0
  if n%2==0:  # if power is even, then the answer is that result times itself 
    return power(x*x,n//2)
  else:  #else, n is odd, then answer is that result times itself times x 
    return x*power(x*x,n//2)

if __name__=="__main__":
  p=power(3,5)
  print("The result x^n is: "+str(p)) #print the result

Output and Screenshots:

#Please dont forget to upvote if you find the solution helpful. Feel free to ask doubts if any, in the comments section. Thank you.