1. Prove that the RecursivePower algorithm below is correct. You may find the following facts about even and odd integers useful for your proof. (a) All integers are either even or odd. (b) If x is even, then x/2 is an integer. (c) If x is odd, x - 1 is even.

Input: n: a nonnegative integer Output: 2n 1 Algorithm: RecursivePower 2 if n 0 then 3return 1 4 else if n is even then temp = RecursivePower(n/2) 6 return temp temp 7 else stempRecursivePower( (n 1)/2) 9 rn 2 temp temp 10 end