Lab 6 Solutions

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

### Question 3: Binary

Write the recursive version of the function `binary`

which takes in `n`

, a number, and returns a list representing the representation of the number in base 2.

```
def binary(n):
"""Return a list representing the representation of a number in base 2.
>>> binary(55055)
[1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
>>> binary(-136)
['-', 1, 0, 0, 0, 1, 0, 0, 0]
"""
"*** YOUR CODE HERE ***"
if n < 0:
return ['-'] + binary(-1 * n)
elif n < 2:
return [n % 2]
else:
return binary(n // 2) + [n % 2]
```

Use OK to test your code:

`python3 ok -q binary`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`