4. If a list of size n has an element that appears more than n/2 times, let's call it a "majority element". For example, the list [2,2,5,1,5,5,1,5,5] has a majority element (5) but the list [2,2,5,1,5,5,1,5] does not. Use Python and recursion to write a function that expects one argument, a Python list, and returns the majority element. If there isn't a majority element, your program should return None. Here's a sketch of a recursive algorithm to find the majority element: Step 1: Find the possible majority elements in the list Step 2: Verify whether each possibility is actually a majority element Step 1 is the recursive part. To find a possible majority element in the list A, create a second (empty) list B. Compare and A[11. If their values are equal, add one of them to B Otherwise, don't do anything. Then compare A[2] and A[3]. If they are equal, add one of them to B. Continue on in this way until all of A has been read. Then, recursively find the possible majority elements in B. The recursion will end when there are two or fewer elements in the list. These are the final possible majority elements for the original list. Step 2 can be accomplished by a simple sequential search through the list A to verify if any possible majority element constitutes more than half of the original list Some notes: Draw some test cases, follow the algorithm, and convince yourself of how it works If the list has an odd number of elements, do the pairing comparisons as described above, leaving the last element unpaired. Add this unpaired element to B Write two functions: findPossibilities (list) will accomplish step 1. It expects a Python list as an argument and returns a Python list of possible majority elements. verifyPossibilities(list, possibilities) wi accomplish step 2. It expects the original Python list and the Python list of possible majority elements as arguments. It returns the majority element if there is one or None otherwise. For problems 5 and 6, assume that you have constructed a linked list using the Node) class from your textbook. Here is one such example: >>> n 1 = Node ( 1 0 ) >>> n2 = Node (20) >n3Node (30) >>n4 Node (40) >>>n2.setNext (nl) >>n3.setNext (n2) >>n4.setNext (n3)