Problem 2: Tracing list comprehensions and recursion

50 points; individual-only

Put your answers for this problem in a plain-text file named ps4pr2.txt.

1.Consider the following Python program:

def mystery1(x): lc = [2*y - 1 for y in range(x)] return sum(lc) x = 5 y = 4 y = mystery1(y) print(x, y) x = mystery1(x) print(x, y) 

Trace the execution of this program. Your answer should include:

a table for the variables in the global scope that illustrates how their values change over time. You can begin it as follows:

 x | y ----------- 5 | 4 

one or more separate tables that illustrate the changes in the local variables that belong to the function; you can either use a different table for each function call, or one table for the function as a whole.

Your table(s) for the function should have the following columns:

 x | y | lc ------------------ | | 

In the column for lc, you should show the how the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehensions runner variable, you should show the current partial result of the list comprehension.

We included a similar table for a method called myst as part of the solution to a clicker question in the lecture notes on Recursive Design.

a separate section that specifies the output of the program (i.e., the values that are printed).

2: Consider the following Python function:

def mystery2(vals): """ takes a list of numbers and does something with them """ scored_vals = [[x**2, x] for x in vals] best_pair = max(scored_vals) return best_pair[1] 

Trace the execution of the following call to this function. e.g. mystery2([-2, 1, -5, 4])

Your answer should include:

a table that illustrates the changes in the values of x and scored_vals as the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehensions runner variable, you should show the current partial result of the list comprehension.

the value assigned to the variable bestpair

the return value of the function call

3. Briefly describe what the function mystery2 (from the previous part of this problem) does in general. In other words, for an arbitrary list of numbers vals, what will mystery2 return?

4.Consider the following recursive function:

def mystery4(s): """ takes a string s and does something with it """ if len(s) <= 1: return '' # the empty string, with nothing between the quotes else: result_rest = mystery4(s[1:]) if s[0] == s[-1]: return result_rest else: return result_rest + s[0] 

Trace the execution of the following call to this function. e.g. mystery4('banana')

Your answer should illustrate the sequence of function calls that are made from the initial call to the base case. Include a separate section for each call, taking an approach that is similar to the one we have often used in lecture. Begin each section with the call itself (e.g., `mystery4(banana)). Then include a line that explicitly states the value assigned to the parameter. Next, if the call is a base case, you can just show the value that is returned. If the call is a recursive case, you should show the recursive call and its result, along with the value that is ultimately returned. We also encourage you to use indenting to emphasize the way in which one call occurs in the context of prior calls.

For example, recall the num_vowels function from lecture. When tracing the call num_vowels('ate'), you would start by getting all the way down to the base case:

num_vowels('ate') ----------------- s = 'ate' num_in_rest = num_vowels('te') num_vowels('te') ---------------- s = 'te' num_in_rest = num_vowels('e') num_vowels('e') --------------- s = 'e' num_in_rest = num_vowels('') num_vowels('') -------------- s = '' return 0 

Note that we have left blank lines between sections. Then, once you have reached the base case, you can go back and add in both the results of the recursive calls and the values returned by the earlier calls, using the space provided by the blank lines:

num_vowels('ate') ----------------- s = 'ate' num_in_rest = num_vowels('te') = 1 return 1 + 1 = 2 num_vowels('te') ---------------- s = 'te' num_in_rest = num_vowels('e') = 1 return 0 + 1 = 1 num_vowels('e') --------------- s = 'e' num_in_rest = num_vowels('') = 0 return 1 + 0 = 1 num_vowels('') -------------- s = '' return 0 

Take this same approach when tracing mystery4('banana').

5: What is the final result of the call mystery4('banana')?