CS61A Lab 3: Recursion and Midterm Review

Week 4, Spring 2013

Warm Up: Recursion Basics

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.

Exercise 1: In summation...

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.


Exercise 2: Hailstone 2, Recursive Boogaloo

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.


Exercise 3: 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

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.

Exercise 4: A Fistful of Functions

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

Exercise 5: For A Few Lambdas More

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

Exercise 6: The Good, The Bad, and The Curry

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

Exercise 7: The While Bunch

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.


Exercise 8: Butch Cassidy and the Environment Diagram

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)