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