Question

g Consider the turning point problem again, but this time you are given a sequence of at least three integers, which consists of a decreasing subsequence followed by an increasing subsequence. Using the divide and conquer technique, develop a recursive algorithm that finds the index of the turning point in the sequence (that is, the point where it transitions from a decreasing subsequence to an increasing subsequence). For example, in the sequence [43 30 16 10 7 8 13 22], the integer 7 is the turning point and its index is equal to 4 (assuming the starting index is 0). So, the algorithm should return 4

Answer 1

Step-by-step explanation:

The following code is written in Python, it creates a recursive function that takes in a list as a parameter, then compares the first two items in the list if the first is greater, it increases the index by one and calls the function again. This is done until the turning point is found, it then prints out the position of the turning point int the list.

def find_turning_point(list, x=0):

if list[x] > list[x + 1]:

x += 1

return find_turning_point(list, x)

else:

return "The turning point position is: " + str(x)