Part IV: Recursive Algorithms (20 pt.) Given the following recursive algorithm: procedure foo(x, y) Input: x positive integer, y: integer Output?? if x=#1 then return y else return foo(x-1, y) + y 1. (4 pt., 2 pt. each) Trace algorithm foo for each of the following inputs: x=2 and y=5. x=3 and y-2. That is, show all steps performed by the algorithm for these inputs. 2. (1 pt.) What is the output of algorithm foo for any input x and y, where x is a positive integer and y is an integer? 3. (15 pt.) Prove that algorithm foo is correct using induction. Answer the following questions: a. b. c. d. e. What is the base case? Complete the basis step of the proof by showing that the base case is true. What is the inductive hypothesis? What do you need to show in the inductive step of the proof? Complete the inductive step of the proof