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
    """
"*** YOUR CODE HERE ***"
if n == 1: return 1 return n + sum(n - 1)

Use OK to test your code:

python3 ok -q sum

Question 2: 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]
    """
"*** YOUR CODE HERE ***"
if n < 0: return ['-'] + decimal(-1 * n) elif n < 10: return [n % 10] else: return decimal(n // 10) + [n % 10]

Use OK to test your code:

python3 ok -q decimal

Question 3: 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
    """
"*** YOUR CODE HERE ***"
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

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Required Practice Problems Open in a new window

These questions are a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Use OK to test your code:

python3 ok -q practice_problems

Past Midterms

For your reference, here is a table of past midterms to study with! They can also be found on the resource page.

Name Blank Exam Solutions Professor(s) Walkthrough Video Notes
Spring 2016 Practice Link Link David Culler
Spring 2016 Link Link David Culler Link
Spring 2016 Retake Link Link David Culler Link Please see correction below for Q4.
Spring 2018 Link Link Gerald Friedland Link
Fall 2018 Link Link David Culler Link
Spring 2019 Link Link Gerald Friedland Link
Fall 2019 Link Link Michael Ball Link The correct calls to alt_fib(6) is 25 not 26.
Fall 2019 CSM Mock Midterm Link Link N/A