A little number theory

1. Write a method called power that computes , using the following recursive definition of exponentiation:

   In the comments of the method, indicate how many recursions it requires as a function of x and n.

2. Write an improved version of power called morePower that takes advantage of the following recurrence:

   In the comments of the method, indicate how many recursions it requires as a function of x and n.

3. Ackerman's function, A(m, n) is defined:

   Write a method named ack that evaluates Ackerman's function. Can you prove that this method terminates?

CREDIT: These exercises are from Standish, Data Structures in Java, Addison Wesley. Do Exercises 1, 2 and 4 on page 113 of the text.