**Homework 7: Call Yourself**
**Reed CSCI 121 Fall 2022**
*complete the exercises by 9am on 10/25*
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
(##) `[HW7 P1]` print digits
Write a printing procedure `def print_digits(n)` that, when given
a positive 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.
Notice that you only need to worry about printing the digits of positive
integers. We don't expect your code to work correctly for 0 or for negative
numbers.
You should not get the digits of an integer by converting it to a string
with `str`. Use the integer division operations `//` and `%`
instead.
(##) `[HW7 P2]` remainder
Consider the quotient and remainder operations when a non-negative
integer is divided by a positive integer. For example, 37 divided
by 10 is 3 with a remainder of 7. One way of thinking about the
remainder is that it is the amount left over after repeatedly
taking away the divisor from that number. So, since 7 is the
result of subtracting 10 three times from 37, is the remainder
due to that division by 10. 7 = 37-10-10-10.
Looking at this process, we can see that 37, 27, 17, and 7 all have
the same remainder when divided by 10.
Write a *recursive* function `def remainder(n,d)` that, for any
non-negative integer `n` and positive integer `d`, computes
the remainder `n % d` and returns it.
~~~ none
>>> remainder(37,10)
7
>>> remainder(15,5)
0
>>> remainder(20,7)
6
>>> remainder(3,7)
3
~~~
Do not use the `//` or `%` operators in your code. Also, do not import
anything else into your module.
Your function must be recursive.
You need not worry about dividing negative integers. Nor do you need to
deal with anything but positive divisors.
(##) `[HW7 P3]` quotient
Using the same ideas we outlined for `remainder`, instead
write a *recursive* function `def quotient(n,d)` that, for any
non-negative integer `n` and positive integer `d`, computes the quotient
`n // d` and returns it.
~~~ none
>>> quotient(37,10)
3
>>> quotient(15,5)
3
>>> quotient(20,7)
2
>>> quotient(3,7)
0
~~~
Note that the quotient of 37 divided by 10 is just one more than
the quotient of 27 divided by 10.
Do not use the `//` or `%` operators in your
code. Also, do not import anything else into your module.
Your function must be recursive.
You need not worry about dividing negative integers. Nor do you need to
deal with anything but positive divisors.
(##) `[HW7 P4]` collatz length
Consider 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 `def collatz_length(n)` that takes a
positive integer `n` 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.
(##) `[HW7 P5]` is power
Write a *recursive* function `def is_power(n,b)` that takes two positive
integers `n` and `b` and determines whether or not `n` is an integer
power of `b`. If it is, it should return `True`. If it is not, it
should return `False`.
~~~ none
>>> is_power(1000,10)
True
>>> is_power(9,3)
True
>>> is_power(1,3)
True
>>> is_power(16,2)
True
>>> is_power(9,2)
False
~~~
You should not use any of the built-in power operations `**` of `pow`, and
you should not import any libraries. Instead, just use the basic integer
arithmetic operations.
Your function must be recursive.
(##) `[HW7 P6]` 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 `def sum_power2(n)` which returns a 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))))'
~~~