Problem Set 3—Recursive Algorithms

Purpose

This problem set reinforces your understanding of recursion, including your ability to design and program recursive algorithms, and your ability to prove them correct.

Background

This problem set is based on material covered in lectures on September 22 and 24. The basic concept behind recursion is also covered in the “Recursion” video at https://www.youtube.com/watch?v=t4MSwiqfLaY.

This exercise asks you to code and run some algorithms in a language of your choice. I recommend that you use a language that you are already familiar with and/or have easy access to on your own computer. See me if you want suggestions for languages or places to get them from.

Activity

For each of the following problems…

1. Design (in pseudocode) a recursive algorithm to solve it
2. Prove mathematically that your algorithm is correct
3. Code and run your algorithm in a programming language of your choice.

Coding and running your algorithms is important for seeing concretely that they work. This can sometimes be hard to believe, especially when first encountering recursion, even if all the theory says that the algorithm works.

Problem 1

Given a list of n values, A₁, A₂, …, A_n, find the smallest value in A. Use the recursive idea that in a list of only 1 element, that element is necessarily the smallest, while in a list of n > 1 elements, the smallest element is the minimum of A_n and the smallest element in A₁ through A_n-1. You may find that there are two versions of this algorithm, only slightly different, but with a huge difference in running times—more on this when we talk about time analysis and recursive algorithms.

Problem 2

The recursive multiplication algorithm we talked about in class on September 22 has an analogous algorithm for exponentiation. In particular, this algorithm is based on expressing xⁿ (for n a non-negative integer) in terms of x^n/2 when n is even, and in terms of x^n-1 when n is odd. Figure out the corresponding recursion, and then design, prove, and code an algorithm based on it.

Problem 3

The bisection method for finding roots of functions is based on the following idea: Suppose f is a continuous function on (at least) the interval [a,b], and that f(a) and f(b) differ in sign. Then by the Intermediate Value Theorem, f has at least one root between a and b. To find that root, evaluate f at (a+b)/2 (i.e., the midpoint of interval [a,b]), and check the sign of the result. If the result differs in sign from f(a), then find the root in the smaller interval [a,(a+b)/2]; if the result differs in sign from f(b), find the root in the interval [(a+b)/2,b]; in the highly unlikely event that f( (a+b)/2 ) is exactly equal to 0, then (a+b)/2 is the root.

Bisection is usually implemented iteratively, but the above description suggests a way to express it recursively. Do so. The base case for the recursion should be that b-a is less than some tolerance, and the correctness criterion should be that f has a root within that tolerance of the value returned by your algorithm.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.