DOC PREVIEW
UW-Madison CS 240 - Introduction to Discrete Mathematics

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS/Math 240: Introduction to Discrete Mathematics 2/24/2011Lecture 11 : RecursionInstructor: Dieter van Melkebeek Scribe: Dalibor Zelen´yDRAFTLast time we started talking about recursion. It is convenient for solving problems whosesolutions can be reduced to easier instances of the same pr obl em . We’ve seen last time how toconvert some earlier algorithms from class into recursive programs. Today we discuss correctnessof recursive programs.11.1 Correctness of Recursive ProgramsWhen we show correctness, we show that the program meets its specification. We use the wordpreconditions for the conditions a valid input must satisfy, and the word postconditions for the con-ditions the output of t he program must satisfy after r ec e i v i ng an input satisfying the precondi t i ons.Using this terminology, a cor r e ct program must satisfy the f ol l owing condition:Condition (∗): For all possible i npu t s that satisfy the preconditions, the program produ ces anoutput that satisfies the postconditions, assuming it halts.We phrase the program corr e c tne ss requirement this way because sometimes the program isdesigned to work only on some input s. We saw an example of this l ast class when our greatestcommon divisor algorithm worked only on positive inputs, even though the greatest common divisorof zero and a positive number is also defined. Pr e con di ti on s are also important when we arguecorrectness of recursive algorithms by induction. As part of the induction hypothesis, we assumethat all recursive calls for which the i n put satisfies the preconditions te rm i nate and return thecorrect value.The breakup of correctness into part i al correctness and termination remains when proving thecorrectness of recursive programs.1. Partial correctness: The program produces correct output, assuming the input satisfies thepreconditions and condition (∗) holds for all the r ec ur si ve calls.2. Termination: On all inputs that satisfy the preconditions, the program produces some output.We now give correctness proofs of the re c ur si ve algorithms we presented last lec tur e .11.1.1 Greatest Common DivisorWe restate the recursive algorithm for computing greatest common divisors as function GCD, andthen prove its correctness.Algorithm GCD(a, b)Input: a, b ∈ N, a > 0, b > 0Output: gcd(a, b)(1) if a = b then return a(2) if a < b then return GCD(a, b − a)(3) if a > b then return GCD(a − b, b)1Lecture 11: Recursion 11.1. Correctness of Recursive ProgramsLet’s start with partial correctness. The structure of the proof will follow the structure of thealgorithm. We will have one case for each of t he lines in the descripti on of the algorithm.Case 1: a = b. In this case, the algor i t hm returns a, and this is the correct answer becausegcd(a, b) = gcd(a, a) = a. (Think of this case as the base case of an inductive proof.)Case 2: a < b. In this case gcd(a, b) = gcd(a, b − a) by a result from last lecture . Since b > a, aand b − a ar e both positive int ege r s, so t he precondi ti on s of GCD are satisfied. Hence, Condition (∗)implies t hat the call GCD(a,b-a) returns gcd (a, b − a) = gcd(a, b), and that’s what we return. Thus,we get partial correctness i n this case as well.Case 3: a > b. The argument for this case is similar to the one for Case 2, except the roles ofa and b are interchanged.This completes the proof of partial cor r e ct ne ss.Now let’s argue termination. We give a proof by induction on a + b. Again, we break down theproof based on the three cases i n the algorithm.Since a, b > 0 by the preconditions, the small es t a + b can be is 2. In that case a = b = 1, sothe algorithm returns. This proves the base case.For the inductive step, assume that when a + b ≤ n and a and b satisfy the preconditions, thealgorithm terminates.Case 1: a = b. In this case, a = b, so the algorithm returns right away and terminates.Case 2: a 6= b. The algorithm calls GCD on input a′, b′that satisfies the preconditions, anda′+ b′< a + b (one of a or b is reduced by at least 1 to obtain a′and b′). The recursive call the nreturns by the induction hypothesis, and the algorithm returns ri ght after that happens.The completes the proof that the algorithm terminat es , and also conclud es the proof of correct-ness of the algorithm.When we prove partial correctness, we don’t argue that the progr am actually halts at somepoint. We can take that as an assumption since we onl y prove the implication “if the programhalts, the re tu rn ed val u e is corre c t” when we prove partial corre c tne ss . For this reason, we canprove partial correctness of a program that doesn’t always halt. For example, if our sp e c i fic ati onwere to allow a = 0 or b = 0, the call GCD(a,b-a) would be the same as the call GCD(a,b), so GCDwould just be calling it se l f over and over again. But since both inputs to the recurs i ve call satis fythe preconditions in this case, Condition (∗) gives us the postconditions, i. e. , the result returnedfrom the recursive call GCD(a,b-a) is correct. The result we retur n is then cor r e ct too. However,this argument doesn’t tell us that we got closer to the solution by returning a correct answer s i nc eCondition (∗) assumes that t he program terminates.Finally, we remark that the kind of recursion used to describe function GCD is called tail recur-sion. In tail recursion, we only make a recursive call at the very end before we re tu r n, and returnthe value returned by the recursive call.11.1.2 Grade School Multiplication AlgorithmNow we prove correctness of the recursive version of the grade school multiplication algorithm.This becomes more complicated because we need some more computation in order to produce theresult after the recursive calls return.Recall that we wrote b = 2q + r where q = ⌊b/2⌋ and r ∈ {0, 1} is the remain de r after dividingb by 2. Now multiply both side s by a to get ab = 2aq + ar. The right-hand side expresse s themultiplication ab as three simpler multiplication problems and one addition. See the note s fromprevious lecture for more detail on this. We just restate the algorithm here.2Lecture 11: Recursion 11.1. Correctness of Recursive ProgramsAlgorithm MULT(a,b)Input: a, b ∈ NOutput: a · b(1) if b = 0 then return 0(2) if b is even then return 2 · MULT(a, ⌊b/2⌋)(3) else return 2 · MULT(a, ⌊b/2⌋) + aFirst let’s prove partial correctness of this algorithm. Like in the previous proof, the proofstructure


View Full Document

UW-Madison CS 240 - Introduction to Discrete Mathematics

Download Introduction to Discrete Mathematics
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Discrete Mathematics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Discrete Mathematics 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?