---

What's here?

These are solutions to a set of exercises, along with a fair amount of additional background explanation. Note that I've gone into more detail with those explanations than we would have wanted or expected students to do, but I'm using these as an opportunity to solidify your understanding; don't take this as an indication that you should be writing your answers in as much detail as I am here.

---

Problem 1

Writing the function recursively

There's more than one way you could apply recursion to a problem like this one, but all of them have the same requirement: The recursive function needs to use its parameters to track its progress (i.e., the parameters make clear how much of the problem is remaining to solve).

One way to write the find_max function recursively is for its parameter always to carry whatever portion of the list has yet to be processed. So, for example, we could use slicing to build gradually smaller lists, then pass them to a recursive call to the function.

def find_max(nums: list[int]) -> int:
    '''
    Finds the maximum value in the given list of integers,
    or None if the list is empty
    '''
    if len(nums) == 0:
        return None
    
    largest_after_first = find_max(nums[1:])

    if largest_after_first == None or largest_after_first < nums[0]:
        return nums[0]
    else:
        return largest_after_first

We could establish a shorthand for the "None-checking" we're doing, by writing a function that solves that part of the problem. This doesn't result in less code, per se, but it does give us a separate function that we can test separately, and makes our recursive function simpler and clearer.

def find_max(nums: list[int]) -> int:
    '''
    Finds the maximum value in the given list of integers,
    or None if the list is empty
    '''
    if len(nums) == 0:
        return None

    return _max_with_none(nums[0], find_max(nums[1:]))

def _max_with_none(value1: int, value2: int | None) -> int | None:
    if value2 == None or value1 > value2:
        return value1
    else:
        return value2

One downside of the approaches above, though, is the building and re-building of lists; each time we ask for a slice of the list, we end up building a brand-new list that's almost entirely a copy of one that we already had. If we're willing to write two functions, anyway, then we might as well split the problem up differently: A function that's called to solve the problem, then a separate recursive function that uses an additional parameter to keep track of how far we have left to go in the list.

def find_max(nums: list[int]) -> int:
    '''
    Finds the maximum value in the given list of integers,
    or None if the list is empty
    '''
    return _find_max_from(nums, 0)

def _find_max_from(nums: list[int], index: int) -> int:
    '''
    Finds the maximum value in a portion of the given list of integers
    starting with the given index, or None if there are no values in that
    portion of the list (i.e., the index is too large).
    '''
    if index >= len(nums):
        return None

    largest_after = _find_max_from(nums, index + 1)

    if largest_after == None or largest_after < nums[index]:
        return nums[index]
    else:
        return largest_after

There's another additional thing worth noting: If you're not comfortable with the idea that we've written two functions, we could also put the "helper" function into the find_max function. (I don't find it especially problematic to have two functions, especially since one of them is marked as protected; having them separate allows us to test them separately. Still, if you're curious how to avoid having two separate functions, below is how you could do that.)

def find_max(nums: list[int]) -> int:
    '''
    Finds the maximum value in the given list of integers,
    or None if the list is empty
    '''
    def find_max_from(nums: list[int], index: int) -> int:
        if index >= len(nums):
            return None
    
        largest_after = find_max_from(nums, index + 1)
    
        if largest_after == None or largest_after < nums[index]:
            return nums[index]
        else:
            return largest_after

    return find_max_from(nums, 0)

Finally, using a Python feature we've not seen — which allows a function's parameters to have a default value specified — we could write a function that optionally takes an index, but otherwise defaults to 0, allowing us to write a function that could be called as find_max([1, 2, 3, 4]), work recursively through the list, but not build slices of it.

def find_max(nums: list[int], index: int = 0) -> int:
    '''
    Finds the maximum value of the values in the given list of
    integers at and after the optionally-specified index (which
    defaults to zero), or None if the index is beyond the end of
    the list.
    '''
    if index >= len(nums):
        return None
    
    largest_after_first = find_max(nums, index + 1)

    if largest_after_first == None or largest_after_first < nums[index]:
        return nums[index]
    else:
        return largest_after_first

The notation index: int = 0 in the function's list of parameters means that we can call this function with either one argument (which will correspond to nums, with index defaulting to 0) or two arguments (the first of which will correspond to nums and the second of which will correspond to index).

Should we write the function recursively?

Certainly, there are reasons why our natural biases might have led us to prefer the loop-based solution. In my experience, students who learned about loops before recursion tended to find loop solutions "cleaner" and found it difficult to adapt to using recursion instead; meanwhile, students who learned about recursion before loops (which was how we taught a different introductory computer science sequence many years ago) tended to find recursive solutions "cleaner" and found it difficult to adapt to using loops instead.

But this question doesn't really revolve around aesthetics; it revolves around things that are more practical. Recursion has a cost and that cost is not to be underestimated.

• The act of calling a function is more expensive than you might imagine. Think about what happens when we call a function. Arguments are calculated and passed into parameters. We need to remember enough about where we came from that we can pick up where we left off when the function ends. Only then can we safely jump into the function. Once the function ends, a value is returned, then things are otherwise put back the way they were. This is certainly not without cost; relative to the cost of jumping to the top of, say, a while loop, a function call is quite costly.
• When a function is called, we remember enough about the calling function that we can return to it when the called function ends. This information is stored on what's sometimes called a run-time stack. The run-time stack grows proportionally with the depth of function calls — it gets larger whenever we call a function and smaller whenever a function returns. This means that unbounded recursion is a real problem, but even recursion with boundaries can be problematic, since Python has a depth limit. (If you don't believe me, try find_max(list(range(100000))) on both an iterative and recursive version of find_max.)

It should be pointed out that different programming languages behave differently in this regard. Some have implementations in which recursion would be a better choice than loops in cases where the tradeoff might be different in Python. Some only have recursion as a form of repetition and don't offer loops at all. For some carefully-written kinds of recursion, some programming languages offer a way to solve both of these problems — using an optimization with a fancy name: tail-call elimination, which basically means "If you know you don't need to come back to the function that called you for any reason, don't bother" — but Python does not offer this optimization. Given that, we avoid recursion in Python except when we need it, which is to say that we not only need to repeat something, but we need to remember the entire state of our computation when we return from each part of it.

As a result of this, our find_max problem is best written iteratively (i.e., using a loop), where we won't pay the cost of the function calls involved in the recursion, and where we won't have a limit on that recursion's depth that imposes an unnecessary limit on how large of a problem our function can solve.

---

Problem 2

There are multiple reasonable solutions to these problems, but below is an example solution for each. Two key ideas shows up in both of them:

• We use recursion to deal with the nested lists, but not to iterate through the lists one element at a time. See the longer discussion in the Problem 1 solution for an explanation of why.
• We look at the type of each element to determine what to do at each step, but otherwise rely on our assumptions about those types (e.g., since we know the input in the first_chars problem is a nested list of strings, we know that each element will either be a string or a list).

For each function, we'd want to consider normal and boundary cases, though there aren't really error cases to be considered (i.e., given our assumption about the types of input, we're tolerant of all inputs that meet that assumption, and we aren't mandating a particular kind of failure when inputs don't meet it, so there's nothing to test).

def first_chars(nested_list: 'nested list of strings') -> str:
    result = ''

    for element in nested_list:
        if type(element) == list:
            result += first_chars(element)
        elif len(element) > 0:
            result += element[0]

    return result

# When all strings have a first character and no nesting
assert first_chars(['a', 'b', 'c', 'd']) == 'abcd'
assert first_chars(['apple', 'banana', 'cantaloupe', 'date']) == 'abcd'

# When all strings have a first character and nesting is involved
assert first_chars(['f', ['g', 'h'], 'j', ['k'], 'l']) == 'fghjkl'
assert first_chars(['b', ['c', ['d', ['f', ['g'], 'h'], 'j'], 'k'], 'l']) == 'bcdfghjkl'

# When some strings don't have a first character, they are skipped
assert first_chars(['g', '', 'h', '', 'j', '', 'k']) == 'ghjk'
assert first_chars(['r', ['s', ''], ['', 't'], 'v']) == 'rstv'

# When some sublists are empty or have no non-empty strings, they are skipped
assert first_chars(['g', [], ['h', ''], ['', '', ''], 'j']) == 'ghj'

# When all strings are empty, the output is empty
assert first_chars(['', '', '', '', '']) == ''
assert first_chars(['', ['', ''], ['', ['', [''], ''], ''], [''], '']) == ''

# When there are no strings at all, the output is empty
assert first_chars([]) == ''


def count_bigger(nested_list: 'nested list of objects', threshold: int | float) -> int:
    result = 0

    for element in nested_list:
        if type(element) == list:
            result += count_bigger(element, threshold)
        elif type(element) == int or type(element) == float:
            if element > threshold:
                 result += 1

    return result

# When there is no nesting and only integers
assert count_bigger([2, 4, 6, 8, 10], 0) == 5
assert count_bigger([2, 4, 6, 8, 10], 3) == 4
assert count_bigger([2, 4, 6, 8, 10], 7) == 2
assert count_bigger([2, 4, 6, 8, 10], 11) == 0

# When there is no nesting and only floats
assert count_bigger([2.5, 4.25, 6.75, 8.125, 10.0625], 0) == 5
assert count_bigger([2.5, 4.25, 6.75, 8.125, 10.0625], 3) == 4
assert count_bigger([2.5, 4.25, 6.75, 8.125, 10.0625], 3.0) == 4
assert count_bigger([2.5, 4.25, 6.75, 8.125, 10.0625], 7) == 2
assert count_bigger([2.5, 4.25, 6.75, 8.125, 10.0625], 11.0) == 0

# When the threhsold value occurs in the list, it isn't counted
assert count_bigger([4, 5, 6, 7, 8], 5) == 3
assert count_bigger([4, 5, 6, 7, 8], 5.0) == 3
assert count_bigger([4.125, 5.75, 6.25, 7.875, 8.0625], 6.25) == 2

# When there are non-numbers, they are skipped
assert count_bigger([2, 'a', 4, 'b', 6, 'c', 8, 'd', 10, 'e'], 0) == 5

# When there is nesting, values in sublists are counted
assert count_bigger([2, [4, [6], 8], 10], 3) == 4
assert count_bigger([2, [4], [6], [8], 10], 3) == 4

# When there is nesting, non-numbers in nested lists are skipped
assert count_bigger([2, ['a', 4], ['b', 6], ['c', 8], ['d', 10], ['e']], 0) == 5

# When there no numbers, the result is always zero
assert count_bigger(['Boo', 'is', 'happy', 'today'], 13) == 0
assert count_bigger(['Boo', ['is'], ['happy', ['today']]], 13) == 0

# When sublists are empty, they aren't counted
assert count_bigger([2, [4], [], [6], [], [8], [], 10], 3) == 4

# When the list is empty, the result is always zero
assert count_bigger([], 10) == 0

---

Problem 3

1. The expression __name__ == '__main__' is true when it's evaluated within the Python script that was used to launch a new program. It's false when evaluated within any Python script that was imported by that "launch" script.
2. The reason we use the if __name__ == '__main__': technique is to allow us to write scripts that behave differently when they're executed than they do when they're imported. We expect executing a script to cause a program to be executed (i.e., we expect things to happen), whereas we expect importing a module to cause code to become available, but not for code to run, per se.
3. If we assign to a variable in an if __name__ == '__main__': statement at the top level of our script (i.e., not within a function), then that variable becomes a global variable. Its scope is now the entire module, and it lives for as long as the module does. This tells us that we shouldn't be assigning to variables within an if __name__ == '__main__': statement; the if statement in Python doesn't establish a scope, like you might think, so it doesn't "hide" the variables assigned within it, which might be different from programming languages you've learned in the past.

---

Problem 4

There are a lot of reasonable variations, but one possible solution to this problem can be found below.

• problem4.py