Consider a recursive function halve that accepts an integer n and a list of integers ints and returns a list where all of the integers of ints less than or equal to n appear before all of the integers of ints greater than n. For example, halve (2, (3, 1, 4, 1, 5, 9]) might return [1, 1, 9, 5, 4, 3] (because all elements less than or equal to 2 appear before all elements greater than 2). Also, halve(4, (3, 1, 4, 1, 5, 9]) might return (3, 1, 4, 1, 9, 5] (because all elements less than or equal to 4 appear before all elements greater than 4). (a) What is the base case of the recursion?
(b) What is the recursive step? Describe the subproblem and how you will use its solution to find the solution of the bigger problem.
(c) Write the recursive function halve. (An iterative solution will earn no credit.)