**Homework 6: Call Yourself** **Reed CSCI 121 Spring 2025**   *complete the exercises by 9am on 3/11* This week you are to write several functions that *call themselves* to do their own work, that is, for each exercise you are asked to write a *recursive function*. A classic example of this is the factorial function, which computes $$ n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1 $$ This can be viewed as a recursive calculation because the product just above can be written as a product of the number `n` muliplied by the prior factorial, like so: $$ \begin{array}{rcl} n! & = & n \times ((n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1) \\ & = & n \times ((n-1)!) \end{array} $$ And so we can write factorial this way: ~~~ python def fact(n): if n > 1: return n * factorial(n-1) else: return 1 ~~~ The *recursive case* when `n` is larger than 1 (and so the product has several terms) is just the Python form of the expression `n * ((n-1)!)`, The *base case* occurs when the product is just a single term (when `n == 1`). This case is handled by the `else` within this function. For all of these below, you'll want to figure out a similar pattern in their calculation. Ask yourself: how can the actvity of the function be structured so as to rely on itself? You'll also want to ask: how do I handle the simple case(s)? These recursive functions rely on the simplest base cases so that this kind of unwinding terminates. As we saw in class, if you forget the base case then you'll probably get an error that your code's execution exceeded Python's maximum recursion depth. You should not be using any loops to solve these problems. Use recursion! (#) Problems (##) `[Hw6 Ex1]` print digits Write a *recursive* printing procedure `print_digits` that, when given a non-negative integer `n`, outputs the sequence of its digits, one digit on each line. It should output the digits in order of least significant to most significant. This means that the ones digit should be first, followed by the tens digit, followed by the hundreds digit, and so on. For example: ~~~ none >>> print_digits(1234) 4 3 2 1 >>> print_digits(3731) 1 3 7 3 >>> print_digits(7) 7 ~~~ Your procedure *must be recursive*. It should call itself somewhere within its own definition. A quick hint: note that we can think of this procedure, for numbers 10 or larger, as printing the ones digit, followed by printing the other digits. So for the second example. We output 1, and then we output the digits of 373. You need to worry about printing the digits of negative integers. Those will never be an input to this procedure. You should not get the digits of an integer by converting it to a string with `str`. Use the integer division operations `//` and `%` instead. (##) `[Hw6 Ex2]` collatz length Recall the Collatz sequences we experimented with in homework 3. They result from applying the following process: > *Start with some positive integer. If the number is odd, multiply it > by 3 and add 1. If it is even, divide it by 2. For every number > that has ever been tried, repeating this process eventually leads > to the number 1.* For example, starting with 6 we get the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1. This means that the length of 6's collatz sequence is 9. Write a *recursive* function `collatz_length` that takes a positive integer and returns the length of that integer's collatz sequence. ~~~ none >>> collatz_length(6) 9 >>> collatz_length(1) 1 >>> collatz_length(5) 6 ~~~ Your function *must be recursive*. (##) `[Hw6 Ex3]` sum to power of two Consider the following expressions made up of 1s, parentheses, and `+`. ~~~ none 1 (1+1) ((1+1)+(1+1)) (((1+1)+(1+1))+((1+1)+(1+1))) ~~~ Note that these sums are decompositions of successive powers of 2. The first is just $2^0$, the second sums to $2^1$ or 2, the third sums to $2^2$ or 4, and the fourth sums to $2^3$ or 8. Note also, that a sum is just the parenthesized sum of the prior expression, repeated. Write a *recursive* function `sum_power2` which, when given an $n$, returns the string that expresses a sum of this form for $2^n$. ~~~ none >>> sum_power2(0) '1' >>> sum_power2(1) '(1+1)' >>> sum_power2(2) '((1+1)+(1+1))' >>> sum_power2(4) '((((1+1)+(1+1))+((1+1)+(1+1)))+(((1+1)+(1+1))+((1+1)+(1+1))))' ~~~ (##) `[Hw6 Ex4]` flatten In this exercise we write a function `flatten` that takes lists that may have a complicated "nested" structure, and with integers scattered within that structure. We start by giving a few sample uses of `flatten` below: ~~~ >>> flatten([1, 2, 3]) [1, 2, 3] >>> flatten([1, [2, 3]]) [1, 2, 3] >>> flatten([[1, 2], [3, 1]]) [1, 2, 3, 1] >>> flatten([[1, [5, 3, 2]], [3, 1]]) [1, 5, 3, 2, 3, 1] >>> flatten([[1, [5, [3], 2]], [3, [2, 4], 1]]) [1, 5, 3, 2, 3, 2, 4, 1] >>> flatten([[[[[1]]]]]) [1] >>> flatten([1, [], 2, [[]], 3, [[], []]]) [1, 2, 3] ~~~ The function `flatten` takes as its input a single list. But that list itself might contain lists as its elements, and those lists might contain lists, and so on. The goal of `flatten` is to just list all the integer elements that occur in the input's structure in the order they occur. (You can assume that all list items within that structure are either lists or integers.) Write the code for the `flatten` function. You don't want to modify the list you are given. Instead you want to build a new list that is a summary of all the integers found in the list structure you are given. You can use a loop to scan through the list you are given and/or to build the list that you want to `return`. But it is *very tricky* to solve this entirely with loops. Using recursion allows you to handle any of the list items that are also lists. **Note:** If you have a Python value `thing` and you want to know whether it is a list, you can use the code `isinstance(thing, list)`. This will be `True` if `thing` is a list. It will be `False` if it is not a list (e.g. an integer value). **Hint:** You can think of the work performed by `flatten` as "flattening" all the lists it contains, and combining those results. (##) `[Hw6 Ex5]` `a`s and `b`s Write a *recursive* function `as_and_bs` which takes a non-negative integer `n` as input and then generates a list of all the strings of length `n` whose only characters are `'a'` and `'b'`. The order of the strings in the list does not matter. For example: ~~~ >>> as_and_bs(2) ['aa', 'ab', 'ba', 'bb'] >>> as_and_bs(3) ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb'] >>> as_and_bs(0) [''] >>> as_and_bs(1) ['a', 'b'] ~~~ **Hint:** If you look at the result for length 3, it is just a result of making two copies of the result for 2. In the first copy, we stick an `'a'` at the front of each string. So we use `['aa', 'ab', 'ba', 'bb']` to make the list `['aaa', 'aab', 'aba', 'abb']`. In the second copy, we stick a `'b'` at the front of each string. So we make the list `['baa', 'bab', 'bba', 'bbb']` from the list `['aa', 'ab', 'ba', 'bb']`. If we combine these two lists, we get the full listing of strings of length 3.