Lab 6: Recursion and Tree Recursion
Due at 11:59:59 pm on 7/13/2024.
Starter Files
Download lab06.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.
Recursion
Question 1: AB Plus C
Implement ab_plus_c
, a function that takes arguments a
, b
, and
c
and computes a * b + c
. You can assume a and b are both nonnegative
integers. However, you can't use the *
operator. Try recursion!
def ab_plus_c(a, b, c):
"""Computes a * b + c.
>>> ab_plus_c(2, 4, 3) # 2 * 4 + 3
11
>>> ab_plus_c(0, 3, 2) # 0 * 3 + 2
2
>>> ab_plus_c(3, 0, 2) # 3 * 0 + 2
2
"""
"*** YOUR CODE HERE ***"
if b == 0:
return c
return a + ab_plus_c(a, b - 1, c)
Use OK to test your code:
python3 ok -q ab_plus_c
Question 2: Filter
Write the recursive version of the function filter
which returns a list and takes in
f
- a one-argument function that returnsTrue
if the passed in argument should be included in the resulting list orFalse
otherwiseseq
- a list of values
Note that this is different from the built in filter
function we learned previously, which returns a filter object, not a list.
def filter(f, seq):
"""Filter a sequence to only contain values allowed by filter.
>>> def is_even(x):
... return x % 2 == 0
>>> def divisible_by5(x):
... return x % 5 == 0
>>> filter(is_even, [1,2,3,4])
[2, 4]
>>> filter(divisible_by5, [1, 4, 9, 16, 25, 100])
[25, 100]
>>> filter(is_even, [1])
[]
>>> filter(is_even, [2])
[2]
>>> filter(is_even, [])
[]
"""
"*** YOUR CODE HERE ***"
if seq == []:
return seq
if f(seq[0]):
return [seq[0]] + filter(f, seq[1:])
return filter(f, seq[1:])
Use OK to test your code:
python3 ok -q filter
Question 3: Decimal
Write the recursive version of the function decimal
which takes in an integer n
and returns a list of its digits, the decimal representation of n
. See the doctests to handle the case where n < 0
.
def decimal(n):
"""Return a list representing the decimal representation of a number.
>>> decimal(0)
[0]
>>> decimal(2)
[2]
>>> decimal(-8)
['-', 8]
>>> decimal(-136)
['-', 1, 3, 6]
>>> decimal(55055)
[5, 5, 0, 5, 5]
"""
"*** YOUR CODE HERE ***"
if n < 0:
return ['-'] + decimal(-1 * n)
elif n < 10:
return [n]
else:
return decimal(n // 10) + [n % 10]
Use OK to test your code:
python3 ok -q decimal
Question 4: Insect Combinatorics
Consider an insect in an M by N grid. The insect starts at the
bottom left corner, (0, 0), and wants to end up at the top right
corner, (M-1, N-1). The insect is only capable of moving right or
up. Write a function paths
that takes a grid length and width
and returns the number of different paths the insect can take from the
start to the goal. (There is a closed-form solution to this problem,
but try to answer it procedurally using recursion.)
For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 different paths (only 3 are shown above). Note that this problem uses tree recursion.
def paths(m, n):
"""Return the number of paths from one corner of an
M by N grid to the opposite corner.
>>> paths(2, 2)
2
>>> paths(5, 7)
210
>>> paths(117, 1)
1
>>> paths(1, 157)
1
"""
"*** YOUR CODE HERE ***"
if m == 0 or n == 0:
return 0
if m == 1 and n == 1:
return 1
return paths(m - 1, n) + paths(m, n - 1)
Use OK to test your code:
python3 ok -q paths
Submission
When you are done, submit your file to Gradescope. You only need to upload the following files:
lab06.py