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