Notes Recursion Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 7 1 7 2 of Rosen cse235 cse unl edu Recursive Algorithms Notes A recursive algorithm is one in which objects are defined in terms of other objects of the same type Advantages I Simplicity of code I Easy to understand Disadvantages I Memory I Speed I Possibly redundant work Tail recursion offers a solution to the memory problem but really do we need recursion Recursive Algorithms Analysis We ve already seen how to analyze the running time of algorithms However to analyze recursive algorithms we require more sophisticated techniques Specifically we study how to define solve recurrence relations Notes Motivating Example Notes Factorial Recall the factorial function 1 if n 1 n n n 1 if n 1 Consider the following recursive algorithm for computing n Algorithm Factorial 1 2 3 4 5 6 Input n N Output n if n 1 then return 1 end else return Factorial n 1 n end Motivating Example Notes Factorial Analysis How many multiplications M n does Factorial perform I When n 1 we don t perform any I Otherwise we perform 1 I Plus how ever many multiplications we perform in the recursive call Factorial n 1 I This can be expressed as a formula similar to the definition of n M 0 0 M n 1 M n 1 I This is known as a recurrence relation Recurrence Relations I Definition Definition A recurrence relation for a sequence an is an equation that expresses an in terms of one or more of the previous terms in the sequence a0 a1 an 1 for all integers n n0 where n0 is a nonnegative integer A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation Notes Recurrence Relations II Notes Definition Consider the recurrence relation an 2an 1 an 2 It has the following sequences an as solutions 1 an 3n 2 an n 1 and 3 an 5 Initial conditions recurrence relation uniquely determine the sequence Recurrence Relations III Notes Definition Example The Fibonacci numbers are defined by the recurrence F n F n 1 F n 2 F 1 1 F 0 1 The solution to the Fibonacci recurrence is n n 1 5 1 1 5 1 fn 2 2 5 5 your book derives this solution Recurrence Relations IV Notes Definition More generally recurrences can have the form T n T n f n T c or T n T n f n T c Note that it may be necessary to define several T initial conditions Recurrence Relations V Notes Definition The initial conditions specify the value of the first few necessary terms in the sequence In the Fibonacci numbers we needed two initial conditions F 0 F 1 1 since F n was defined by the two previous terms in the sequence Initial conditions are also known as boundary conditions as opposed to the general conditions From now on we will use numbers are fn f1 f0 the subscript notation so the Fibonacci fn 1 fn 2 1 1 Recurrence Relations VI Notes Definition Recurrence relations have two parts recursive terms and non recursive terms 2 T n 2T n 2 n 10 z z recursive non recrusive Recursive terms come from when an algorithm calls itself Non recursive terms correspond to the non recursive cost of the algorithm work the algorithm performs within a function We ll see some examples later First we need to know how to solve recurrences Solving Recurrences There are several methods for solving recurrences I Characteristic Equations I Forward Substitution I Backward Substitution I Recurrence Trees I Maple Notes Linear Homogeneous Recurrences Notes Definition A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an c1 an 1 c2 an 2 ck an k with c1 ck R ck 6 0 I Linear RHS is a sum of multiples of previous terms of the sequence linear combination of previous terms The coefficients are all constants not functions depending on n I Homogeneous no terms occur that are not multiples of the aj s I Degree k an is expressed in terms of k terms of the sequence Linear Homogeneous Recurrences Notes Examples Examples The Fibonacci sequence is a linear homogeneous recurrence relation As are the following an 4an 1 5an 2 7an 3 an 2an 2 4an 4 8an 8 How many initial conditions do we need to specify for these As many as the degree k 3 8 respectively So how do we solve linear homogeneous recurrences Solving Linear Homogeneous Recurrences I We want a solution of the form an rn where r is some real constant We observe that an rn is a solution to a linear homogeneous recurrence if and only if rn c1 rn 1 c2 rn 2 ck rn k We can now divide both sides by rn k collect terms and we get a k degree polynomial rk c1 rk 1 c2 rk 2 ck 1 r ck 0 Notes Solving Linear Homogeneous Recurrences II Notes rk c1 rk 1 c2 rk 2 ck 1 r ck 0 This is called the characteristic equation of the recurrence relation The roots of this polynomial are called the characteristic roots of the recurrence relation They can be used to find solutions if they exist to the recurrence relation We will consider several cases Second Order Linear Homogeneous Recurrences Notes A second order linear homogeneous recurrence is a recurrence of the form an c1 an 1 c2 an 2 Theorem Theorem 1 p462 Let c1 c2 R and suppose that r2 c1 r c2 0 is the characteristic polynomial of a 2nd order linear homogeneous recurrence which has two distinct1 roots r1 r2 Then an is a solution if and only if an 1 r1n 2 r2n for n 0 1 2 where 1 2 are constants dependent upon the initial conditions 1 we discuss how to handle this situation later Second Order Linear Homogeneous Recurrences Example Example Find a solution to an 5an 1 6an 2 with initial conditions a0 1 a1 4 I The characteristic polynomial is r2 5r 6 I Using the quadratic formula or common sense the root can be found r2 5r 6 r 2 r 3 so r1 2 r2 3 Notes Second Order Linear Homogeneous Recurrences Notes Example Continued I Using the 2nd order theorem we have a solution an 1 2n 2 3n I Now we can plug in the two initial conditions to get a system of linear equations a0 1 2 0 2 3 0 a1 1 2 1 2 3 1 1 1 2 1 4 2 1 3 2 2 Second Order Linear Homogeneous Recurrences Notes Example Continued I I Solving for 1 1 2 second 4 4 4 2 in 1 we can plug it into the 2 1 3 2 2 1 2 3 2 2 2 2 3 2 2 Substituting back into 1 we get 1 1 I Putting it all back together we …
View Full Document
Unlocking...