Due Date: Monday, November 6, 2023.

Consider the following recursive function, that we can assume to be called with non-negative numbers:

int mystery(int n, int m)
{
    if (n == m)
        return n;
    else if (n == 0)
        return m;
    else if (m == 0)
        return n;
    else
        return mystery(m, n % m);
}

a. Tracing the execution

Trace the execution of the function calls  mystery(363, 55) ,  mystery(126, 49) ,  and  mystery(81, 37)  by hand.
Specifically, make sure you answer these questions: How many calls do each of them make until they return the answer? What is the value of the parameters in each of the calls? Which base case do they reach?

b. Solve the mystery

What does the function actually do? Can you connect it to a known algorithm for solving this problem?

Consider the following recursive function, for which again, we can assume the parameters to be non-negative numbers. This function computes the combinations of k out of n objects using Pascal's triangle formula.

int combinations(int k, int n)
{
    if (k > n)
        return 0;
    else if (n == k || k == 0)
        return 1;
    else
        return combinations(k-1, n-1) + combinations(k, n-1);
}

a. Draw the recursion tree for computing combinations(4, 7).

b. How many nodes does the runtime stack contain at the most for the function call above, not including the main?

c. How many repeated function calls can you observe in the tree? Give an example. Is this an indication that the function is inefficient?

Upload the answers to exercises 1 and 2 to Canvas in Assignments - Homework 8. If you write them down on paper, take a picture of it and upload it.