We've provided a set of starter files with skeleton code for the exercises in the lab. You can get them in the following places:

*Lambda expressions* are one-line functions that specify two things:
the parameters; and the return value.

```
lambda [parameters]: [return value]
```

One difference between using the `def`

keyword and `lambda`

expressions is that `def`

is a *statement*, while lambda is an
*expression*. Evaluating a `def`

statement will have a side effect;
namely, it creates a new function binding in the current environment.
On the other hand, evaluating a `lambda`

expression will not change the
environment unless we do something with this expression. For instance,
we could assign it to a variable or pass it in as a function argument.

For each of the following expressions, what must `f`

be in order for
the evaluation of the expression to succeed, without causing an error?
Give a definition of `f`

for each expression such that evaluating the
expression will not cause an error.

```
>>> f = ______
>>> f
3
>>> f = ______
>>> f()
3
>>> f = ______
>>> f(3)
3
>>> f = ______
>>> f()()
3
>>> f = ______
>>> f()(3)()
3
```

Try drawing environment diagrams for the following code and predicting what Python will output:

```
# Q1
a = lambda x : x * 2 + 1
def b(x):
return x * y
y = 3
b(y)
_________
def c(x):
y = a(x)
return b(x) + a(x+y)
c(y)
_________
# Q2: This one is pretty tough. A carefully drawn environment
# diagram will be really useful.
g = lambda x: x + 3
def wow(f):
def boom(g):
return f(g)
return boom
f = wow(g)
f(2)
_________
g = lambda x: x * x
f(3)
_________
```

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have two important components:

- Base case(s), where the function directly computes an answer without calling itself. Usually the base case deals with the simplest possible form of the problem you're trying to solve.
- Recursive case(s), where the function calls itself as part of the computation.

Let's look at the canonical example, factorial:

```
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
```

We know by its definition that 0! is 1. So we choose n = 0 as our base case. The recursive step also follows from the definition of factorial, i.e. n! = n * (n-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

- Always start with the base case. The base case handles the simplest argument your function would have to handle. The answer is extremely simple, and often follows from the definition of the problem.
Make a recursive call with a slightly simpler argument. This is called the "leap of faith" - your simpler argument should simplify the problem, and you should assume that the recursive call for this simpler problem will just work. As you do more problems, you'll get better at this step.

Use the recursive call. Remember that the recursive call solves a simpler version of the problem. Now ask yourself how you can use this result to solve the original problem.

Write the recursive version of `summation`

, which
takes two arguments, a number `n`

and a function
`term`

, applies `term`

to every number
between 0 and `n`

, and returns the sum of those results.

The greatest common divisor of two positive integers `a`

and `b`

is the
largest integer which evenly divides both numbers (with no remainder).
Euclid, a Greek mathematician in 300 B.C., realized that the greatest
common divisor of `a`

and `b`

is one of the following:

- the smaller value if it evenly divides the larger value, OR
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if `a`

is greater than `b`

and `a`

is not divisible by
`b`

, then

```
gcd(a, b) == gcd(b, a % b)
```

Write the `gcd`

function using Euclid's algorithm.

For the `hailstone`

function from homework 1, you
pick a positive integer `n`

as the start. If `n`

is even, divide it
by 2. If `n`

is odd, multiply it by 3 and add 1. Repeat this process
until `n`

is 1. Write a recursive version of hailstone that prints out
the values of the sequence and returns the number of steps.

Consider an insect in an *M* by *N* grid. The insect starts at the top
left corner, *(0, 0)*, and wants to end up at the bottom right corner,
*(M-1, N-1)*. The insect is only capable of moving right or down. Write
a function `count_paths`

that takes a grid length and width and returns
the number of different paths the insect can take from the start to the
goal. (There is a closed-form solution to this problem, but try to
answer it procedurally using recursion.)

For example, the 2 by 2 brid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

```
def paths(m, n):
"*** YOUR CODE HERE ***"
```

Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.

```
>>> x = (1, 2, 3)
>>> x[0] # Q1
______
>>> x[3] # Q2
______
>>> x[-1] # Q3
______
>>> x[-3] # Q4
______
```

```
>>> x = (1, 2, 3, 4)
>>> x[1:3] # Q1
______
>>> x[:2] # Q2
______
>>> x[1:] # Q3
______
>>> x[-2:3] # Q4
______
>>> x[::2] # Q5
______
>>> x[::-1] # Q6
______
>>> x[-1:0:-1] # Q7
______
```

```
>>> y = (1,)
>>> len(y) # Q1
______
>>> 1 in y # Q2
______
>>> y + (2, 3) # Q3
______
>>> (0,) + y # Q4
______
>>> y * 3 # Q5
______
>>> z = ((1, 2), (3, 4, 5))
>>> len(z) # Q6
______
```

For each of the following, give the correct expression to get 7.

```
>>> x = (1, 3, 5, 7)
>>> x[-1] # example
7
>>> x = (1, 3, (5, 7), 9)
>>> # YOUR EXPRESSION INVOLVING x HERE
7
>>> x = ((7,),)
>>> # YOUR EXPRESSION INVOLVING x HERE
7
>>> x = (1, (2, (3, (4, (5, (6, (7,)))))))
>>> # YOUR EXPRESSION INVOLVING x HERE
7
```

Write a function `reverse`

that takes a tuple and returns the reverse.
Write both an iterative and a recursive version. You may use slicing
notation, but don't use `tup[::-1]`

.

```
def reverse_iter(tup):
"""Returns the reverse of the given tuple.
>>> reverse_iter((1, 2, 3, 4))
(4, 3, 2, 1)
"""
"*** YOUR CODE HERE ***"
def reverse_recursive(tup):
"""Returns the reverse of the given tuple.
>>> reverse_revursive((1, 2, 3, 4))
(4, 3, 2, 1)
"""
"*** YOUR CODE HERE ***"
```

Write a recursive function `merge`

that takes 2 *sorted* tuples `tup1`

and
`tup2`

, and returns a new tuple that contains all the elements in the
two tuples in sorted order.

```
def merge(tup1, tup2):
"""Merges two sorted tuples.
>>> merge((1, 3, 5), (2, 4, 6))
(1, 2, 3, 4, 5, 6)
>>> merge((), (2, 4, 6))
(2, 4, 6)
>>> merge((1, 2, 3), ())
(1, 2, 3)
"""
"*** YOUR CODE HERE ***"
```

One last thing about tuples: they're *immutable* data structures. This
means that once they are created, they can't be changed. For example,
try this:

```
>>> x = (1, 2, 3)
>>> x[0] = 4
```

This will cause TypeError complaining that tuples don't "support item
assignment." In other words, you can't change the elements in a tuple
because tuples are immutable. Later in the course, we'll see the
opposite -- *mutable* data structures.