Write recursive function:

1. to calculate x power y. Use idea of recursive factorial function

2. to calculate x power y. Try another approach that is:

?? power ?? = ?? power ?? /2. ?? power ?? /2, if y is even number

?? power ?? = ?? power ??/ 2. ?? power ?? /2. ??, if y is odd number that is ?? power 5 = ?? power 2 . ?? power 2 . ??

The idea is instead of calling recursion twice with power y/2, call it once, and store in variable result. Later multiply the result with itself to get complete xy . Roughly, compare the complexity of both functions

Ackermanns function:

A(0, n)=n+1 for n>= 0

A(m, 0)=A(m 1, 1) for m>0

A(m, n)=A(m 1,A(m, n 1) for m>0 and n > 0

3. to calculate Ackermanns function. Calculate the following values. If it is impossible to obtain any of these values, explain why?

A(0, 0) A(0, 9) A(1, 8) A(2, 2) A(2, 0) A(2, 3) A(3, 2) A(4, 2) A(4, 3) A(4, 0)

4. to convert a string of digits into the integer it represents. For example, "13531" represents the integer 13531

Array Recursive Functions

Write recursive functions:

1. for binary search

2. to count pair of adjacent elements in ascending order

3. to find whether there exist two adjacent pair of same elements, means 4, 7 exist twice in the array, where 4 & 7 are adjacent elements and 4 is before 7

4. to find whether there exist two adjacent pair of elements having equal sum

5. to do merge sort