Homework 6 Solutions
Recursion
Question 1: Count Digit
Write a function that takes a positive integer n and returns the
number of times the number digit appears. Do not use any assignment statements.
def count_digit(n, digit):
"""Return how many times digit appears in n.
>>> count_digit(55055, 5)
4
>>> count_digit(1231421, 1)
3
>>> count_digit(12, 3)
0
"""
if n == 0:
return 0
if n % 10 == digit:
return count_digit(n // 10, digit) + 1
else:
return count_digit(n // 10, digit)Use OK to test your code:
python3 ok -q count_digitQuestion 2: Reduce
Write the recursive version of the function reduce which takes
reducer- a two-argument function that reduces elements to a single valueseq- a sequence of valuesstart- the starting value in the reduction. This is usually the identity of the reducer
As a hint, think about the parameters of reduce.
from operator import add, mul
def reduce(reducer, seq, start):
"""Reduce a sequence under a two-argument function starting from a start value.
>>> def add(x, y):
... return x + y
>>> def mul(x, y):
... return x*y
>>> reduce(add, [1,2,3,4], 0)
10
>>> reduce(mul, [1,2,3,4], 0)
0
>>> reduce(mul, [1,2,3,4], 1)
24
"""
if seq == []:
return start
next_base = reducer(start, seq[0])
return reduce(reducer, seq[1:], next_base)Use OK to test your code:
python3 ok -q reduceQuestion 3: Remove Last from Sequence
Complete the recursive function remove_last which creates a new list identical to the input list lst but with the last element in the sequence that is equal to x removed.
Hint: Remember that you can use negative indexing on lists! For example
lst[-1]refers to the last element in a listlst,lst[-2]refers to the second to last element...
def remove_last(x, lst):
"""Create a new list that is identical to lst but with the last
element from the list that is equal to x removed.
>>> remove_last(1,[])
[]
>>> remove_last(1,[1])
[]
>>> remove_last(1,[1,1])
[1]
>>> remove_last(1,[2,1])
[2]
>>> remove_last(1,[3,1,2])
[3, 2]
>>> remove_last(1,[3,1,2,1])
[3, 1, 2]
>>> remove_last(5, [3, 5, 2, 5, 11])
[3, 5, 2, 11]
"""
if not lst:
return []
elif lst[-1] == x:
return lst[0:-1]
else:
return remove_last(x, lst[0:-1]) + [lst[-1]]Illustrated here is a more complete doctest that shows good testing methodology. It is a little cumbersome as documentation, but you'll want to think about it for your projects. Test every condition that might come up. Then you won't be surprised when it does.
Use OK to test your code:
python3 ok -q remove_lastQuestion 4: Map
Write the recursive version of the function map which takes
m- a one-argument function that you want to map onto each element in the list.s- a sequence of values
def map(f, seq):
"""
Map a function f onto a sequence.
>>> def double(x):
... return x * 2
>>> def square(x):
... return x ** 2
>>> def toLetter(x):
... alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
... return alpha[x%26]
>>> map(double, [1,2,3,4])
[2, 4, 6, 8]
>>> map(square, [1, 2, 3, 4, 5, 10])
[1, 4, 9, 16, 25, 100]
>>> map(toLetter, [3, 0, 19, 0])
['d', 'a', 't', 'a']
"""
if seq == []:
return seq
return [f(seq[0])] + map(f, seq[1:])Use OK to test your code:
python3 ok -q mapQuestion 5: Hailstone
For the hailstone function from previously, you pick a positive
integer n as the start. If n is even, divide it by 2. If n is
odd, multiply it by 3 and add 1. Repeat this process until n is 1.
Write a recursive version of hailstone that prints out the values of
the sequence and returns the number of steps.
def hailstone_iterative(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_iterative(10)
10
5
16
8
4
2
1
>>> a
7
"""
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone_iterative(n // 2)
else:
return 1 + hailstone_iterative(3 * n + 1)
def hailstone_recursive(n):
"""Print out the hailstone sequence starting at n, and return the
number of elements in the sequence.
>>> a = hailstone_recursive(10)
10
5
16
8
4
2
1
>>> a
7
"""
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone_recursive(n // 2)
else:
return 1 + hailstone_recursive(3 * n + 1)Use OK to test your code:
python3 ok -q hailstone_iterative
python3 ok -q hailstone_recursiveTree Recursion
Question 6: Count Generations
Consider the following "family tree":
family_tree = [("Jordan", "Alex"), [
[("Taylor", "Morgan"), [
[("Riley", None), []],
[("Avery", None), []]
]]
]]
In this family tree, we see a series of nested lists which takes the format [(parents), [children]]. An empty list means that person has no children.
This tree represents 3 generations.
The goal is to count the maximum number of "generations" represented in the family tree. In this simple tree, there are 3 generations.
Here is a visualization of the simple tree:
Here is a visualization of a more complicated tree covered in the last doctest:
Hint: Subtrees are also family trees
def count_generations(family_tree):
"""
Count the number of generations in a nested list-based family tree.
>>> count_generations([("A"), []])
1
>>> count_generations([("A"), [[("B"), []], [("C"), []] ] ])
2
>>> family_tree = [("Jordan", "Alex"), [
... [("Taylor", "Morgan"), [
... [("Riley", None), []],
... [("Avery", None), []]
... ]]
... ]]
>>> count_generations(family_tree)
3
>>> family_tree = [("Jordan", "Alex"), [
... [("Taylor", "Morgan"), [
... [("Riley", "Sam"), [
... [("Avery", None), []]
... ]]
... ]],
... [("Casey", "Jamie"), [
... [("Quinn", "Chris"), [
... [("Dakota", None), []],
... [("Skyler", None), []]
... ]],
... [("Jesse", "Jordan"), []]
... ]]
... ]]
>>> count_generations(family_tree)
4
"""
if not family_tree:
return 0
parents = family_tree[0]
children = family_tree[1]
max_gen = 0
# for child in children:
# gen = count_generations(child)
# if gen > max_gen:
# max_gen = gen
if len(children) > 0:
max_gen = max([count_generations(child) for child in children])
return 1 + max_genUse OK to test your code:
python3 ok -q count_generations