Recursive Approach If problem instance is simple / trivial ) Solve it directly Else Simplify problem instance into smaller instance(s) of the original problem Solve smaller instance using same algorithm Combine solution(s) to solve original problem (a) Based upon the following recursive formula, write a recursive algorithm in pseu- docode (or C++ code) to calculate the exponent function. 1, if n=0 = a, if n=1 ah, if n is even, n=2k all x a, if n is odd, n=2k+1 //Return an Il n is a natural number, n=0,1,2,... Exp (a,n) = 5 (b) Trace the execution of Exp(2,7): draw the recursion tree, and mark return values for each recursive calls. (c) (20 pts) Fill in the blank in the following binary search algorithm: V: Problem: Binary Search in a sorted (in \bf{descending) order) list Input: list A[left...right), i.e., list index starts from left value we are searching A[o...n-1) for left: the index of the left end of list A right: the index of the right end of list A and A[left]>=A[left+1]>=... >=A[right] Output: if v appears in list A[O...n-1), return the index of the its first appearance if v does not appear in the list, return the negation of the would-be index of v (i.e., the index of v if v is inserted into the sorted list and the descending order is to be maintained) for example, 1) list A[0..3]=[9,6,4,1), left=0, right=3, v=5, the function shall retu 2) list A[0..3]=[9,6,5,2], left=0, right=3, v=6, the function shall retu Algorithm: BinarySearch (A, v, left, right) //Hints: // As we need to return the would-be location if v does not appear in A, // we need to create two base cases, when left==right, or left+1==right (list i // This way, we have enough info. in base cases to return the would-be location if (left==right) //This means if v appears in A, it would have to be A[left if (A[left]==v) return left else if (A[left]A[left]) return //todo by you. else if (v=3 // This way: the two recursive calls will be at least a list of length 1 (i // not call the recursive function with a list of length 0 (left>right) mid = (left+right)/2 if (A[mid] ==value) return mid else if (Amid]>v) //Todo by you... else //Todo by you ... } (d) Use three-questions rule to verify the correctness of your answer to previous ques- tion