## 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.

## Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• To receive full credit for this lab, all questions must be attempted.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

## Recursion

### Question 1: Sum

Using recursion, write a function sum that takes a single argument n and computes the sum of all integers between 0 and n inclusive. Do not write this function using a while or for loop. Assume n is non-negative.

def sum(n):
"""Using recursion, computes the sum of all integers between 1 and n, inclusive.
Assume n is positive.

>>> sum(1)
1
>>> sum(5)  # 1 + 2 + 3 + 4 + 5
15
"""
if n == 1: return 1 return n + sum(n - 1)

Use OK to test your code:

python3 ok -q sum

### Question 2: Has Seven

Write a function has_seven that takes a positive integer n and returns whether n contains the digit 7. Do not use any assignment statements - use recursion instead:

def has_seven(k):
"""Returns True if at least one of the digits of k is a 7, False otherwise.

>>> has_seven(3)
False
>>> has_seven(7)
True
>>> has_seven(2734)
True
>>> has_seven(2634)
False
>>> has_seven(734)
True
>>> has_seven(7777)
True
"""
if k % 10 == 7: return True elif k < 10: return False else: return has_seven(k // 10)

Use OK to test your code:

python3 ok -q has_seven

### Question 3: Filter

Write the recursive version of the function filter which takes

• filter - a one-argument function that returns True if the argument passed in should be included in the list, and False otherwise.
• s - a sequence of values
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]
"""
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 4: Decimal

Write the recursive version of the function decimal which takes in n, a number, and returns a list representing the decimal representation of the number.

def decimal(n):
"""Return a list representing the decimal representation of a number.

>>> decimal(55055)
[5, 5, 0, 5, 5]
>>> decimal(-136)
['-', 1, 3, 6]
"""