Due Date: Wednesday, March 8, 2023.

a. Consider the following tail-recursive C++ function that returns a random element of an array L. Note that the function does not give each element of the array an equal chance to be selected. The last element has one chance in two to be chosen, the second to last 1/4, the third to last 1/8, and so on.

int randomSelect (int A[], int size) 
{
    if (size == 0)
        return -1;
    else if (size == 1)
        return A[0];
    else if (rand() % 2 == 0)
        return A[size-1];
    else
        return randomSelect(A, size-1);
}

The code of this function along with a test for it is provided in tail_rec.cc.

Transform this function into an iterative one using the transformation for tail-recursive functions discussed in class, and add it to the code of the file tail_rec.cc. Add a few examples of calling this function as a comment at the end of the file.

b. Apply the same transformation to the following tail recursive function:

void printN(int n)
{
    if (n < 0)
        cout << endl;
    else 
    {
        cout << n << " ";
        printN(n - 1);
    }
}

The code of this function can also be found in tail_rec.cc.

Consider the following function that is not tail recursive, counting the occurrences of a value in an array. You can also find the code in the same source file listed in Exercise 1.

int countVal (int A[], int size, int val)
{
    if (size == 0)
        return 0;
    else if (A[size - 1] == val)
        return 1 + countVal(A, size-1, val);
    else
        return countVal(A, size - 1, val);
}

For example, if the array A contains {1, 3, 2, 7, 1, 7, 2, 7}, then countVal(A, 8, 7) should return 3.

a. Convert this function to a tail-recursive one by adding an extra parameter, as seen in class.

b. Convert the resulting tail-recursive function into an iterative one using the transformation described in class.

Upload the modified file tail_rec.cc to Canvas, Homework 8.