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