Problem 5 [10 Points]. Computing the exponent of a number (i.e., n^k) can take O(n) time if done by simply multiplying by n, k number of times. A logarithmic way for computing exponents is by using the idea of successive squaring. For instance, rather than computing n^8 as: n * n * n * n * n * n *n * n, we can compute it by repeatedly squaring, beginning with n, computing n^2, n^4 and finally n^8. In general, the algorithm would do the following:

n^k = (n^(k/2))^2 if k is even n^k = n * n^(k-1) if k is odd

Write the lambda expression for this function. You will need to use the if function of the type required for Problem 4 (assume you have a correct implementation). Because this is a recursive function, you will have to nest the lambdas taking n and k within a lambda taking f the function which you will then recursively call within the body. Plus, you will have to precede this definition with the letter Y, which represents a special kind of lambda expression called the Y combinator, which actually makes the recursion happen. So, your solution will look something like:

Y lambda f . [rest of your solution]