Answer the following 2 questions. Please answer it all clearly and show all work/explanations. Also for the parts that require the code, make it such that i can copy paste the code. Make sure all work is legible. Make sure to answer everything and all parts

3. 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? Solve it. (2 points) (b) What is the recursive step? Describe the subproblem and how you will use its solution to find the solution of the bigger problem. (4 points) (c) Write the recursive function halve. (An iterative solution will earn no credit.) (6 points) 4. Let n and r be nonnegative integers. One way to calculate nCr is to use a two-dimensional array, which is filled by adding adjacent entries. A faster recursive function uses the identity nCr n.(n-1)(n-2)(n-r+2)(n-r+1) r.(r-1).(r-2)...2.1 = a (n-1) Cr-1). (Hint: If r = 0 and n > 0, nC, = 1. If r = 0 and n