Recursive Algorithm and Induction

1. Give a recursive algorithm that takes as input two non-negative integers x and y and returns their sum, x + y. The only arithmetic operation your algorithm can perform is incrementing an integer value, e.g. x++, and decrementing an integer value, e.g. x.

2. Use induction to prove that your algorithm always returns a correct answer.

3. State a correct claim about the number of increment and decrement operations your algorithm makes to compute x + y and use induction to prove that your claim is correct.