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

1. 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.

2. 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:

1. 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.

2. 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.

3. 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.

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

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!

3. Now write the recursive version of `summation`. Recall that
`summation` takes two arguments, a number `n` and a function
`term`, and returns the result of applying `term` to every
number between 0 and `n` and taking the sum.

1. Recall 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.

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

This concludes the recursion portion of this lab. As a parting thought, keep in mind that recursion follows the same rules of evaluation that we've seen throughout the class. Try taking one of the above exercises and typing it into the online tutor! The remainder of the exercises will be various review problems.

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() f(3) f()() f()(3)()

Find the value of the following three expressions, using the given
values of `t` and `s`.

t = lambda f: lambda x: f(f(f(x))) s = lambda x: x + 1 t(s)(0) # 1 t(t(s))(0) # 2 t(t)(s)(0) # 3

Suppose we have an already curried function, `f`, and we want to
undo the currying to produce a function `g`, such that `f(x)(y)`
is equivalent to `g(x, y)`. Write `inverse_curry2` that does
exactly this. The definition of `curry2` is given below, as well as
an example.

def curry2(f): return lambda x: lambda y: f(x, y) def divide(x, y): return x / y >>>inverse_curry2(curry2(divide))(4, 2) 2.0

In lecture, you saw that it was possible to compute factorial iteratively. Let's
introduce a new function, a "falling" factorial that takes two arguments, `n`
and `k` and returns the product of `k` consecutive numbers, starting
from `n` and working downwards. We're going to write this iteratively - use a
`while` loop, instead of recursion.

Draw the environment diagram for the following code:

def blondie(f): return lambda x: f(x + 1) tuco = blondie(lambda x: x * x) angel_eyes = tuco(2)