Practice problems: Recursion

Easy

Question 1: In sum...

Write a function sum that takes a single argument n and computes the sum of all integers between 0 and n inclusive. Assume n is non-negative.

def sum(n):
    """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)

Question 2

Implement ab_plus_c, a function that takes arguments a, b, and c and computes a * b + c. You can assume a and b are both positive integers. However, you can't use the * operator. Try recursion!

def ab_plus_c(a, b, c):
    """Computes a * b + c.

    >>> ab_plus_c(2, 4, 3)  # 2 * 4 + 3
    11
    >>> ab_plus_c(0, 3, 2)  # 0 * 3 + 2
    2
    >>> ab_plus_c(3, 0, 2)  # 3 * 0 + 2
    2
    """
    "*** YOUR CODE HERE ***"
    if b == 0:
        return c
    return a + ab_plus_c(a, b - 1, c)

Question 3: Sine

Now we're going to approximate the sine trigonemetric function using 2 useful facts. One is that sin(x) is approximately equal to x as x gets small (for this question, below 0.0001). The other fact is the trigonometric identity

Using these two facts, write a function sine that returns the sine of a value in radians.

def sine(x):
    "*** YOUR CODE HERE ***"
    if abs(x) < 0.0001:
        return x
    return 3 * sine(x / 3) - 4 * pow(sine(x / 3), 3)

Medium

Question 4: repeated, repeated

In Homework 2 you encountered the repeated function, which takes arguments f and n and returns a function equivalent to the nth repeated application of f. This time, we want to write repeated recursively. You'll want to use compose1, given below for your convenience:

def compose1(f, g):
    """"Return a function h, such that h(x) = f(g(x))."""
    def h(x):
        return f(g(x))
    return h

def repeated(f, n):
    if n == 0:
        return lambda x: x #Identity 
    return compose1(f, repeated(f, n - 1))