Recursion Sections 7 1 and 7 2 of Rosen Fall 2008 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Introduction Motivating Example Recurrence Relations Definition general form initial conditions terms Linear Homogeneous Recurrences Form solution characteristic equation characteristic polynomial roots Second order linear homogeneous recurrence Double roots solution examples Single root example General linear homogeneous recurrences distinct roots any multiplicity Linear Nonhomogenous Recurrences Other Methods Backward substitution Recurrence trees Cheating with Maple CSCE 235 Fall 2008 Recursion 2 Recursive Algorithms A recursive algorithm is one in which objects are defined in terms of other objects of the same type Advantages Simplicity of code Easy to understand Disadvantages Memory Speed Possibly redundant work Tail recursion offers a solution to the memory problem but really do we need recursion CSCE 235 Fall 2008 Recursion 3 Recursive Algorithms Analysis We have already discussed how to analyze the running time of iterative algorithms To analyze recursive algorithms we require more sophisticated techniques Specifically we study how to defined solve recurrence relations CSCE 235 Fall 2008 Recursion 4 Motivating Examples Factorial Recall the factorial function 1 if n 1 n n 1 if n 1 n Consider the following recursive algorithm for computing n Factorial Input n N Output n 1 If n 1 2 Then Return 1 3 Else Return n Factorial n 1 4 Endif 5 End CSCE 235 Fall 2008 Recursion 5 Factorial Analysis How many multiplications M x does factorial perform When n 1 we don t perform any Otherwise we perform one plus how ever many multiplications we perform in the recursive call Factorial n 1 This relation is known as a recurrence relation CSCE 235 Fall 2008 Recursion 6 Recurrence Relations 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 a2 an 1 for all integers n n0 where n0 is a nonnegative integer A sequence is called a solution of a recurrence if its terms satisfy the recurrence relation CSCE 235 Fall 2008 Recursion 7 Recurrence Relations Solutions Consider the recurrence relation an 2an 1 an 2 It has the following sequences an as solutions an 3n an n 1 an 5 The initial conditions recurrence relation uniquely determine the sequence CSCE 235 Fall 2008 Recursion 8 Recurrence Relations 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 fn 1 5 1 5 2 n 1 5 1 5 2 n The solution is derived in your textbook CSCE 235 Fall 2008 Recursion 9 Outline Introduction Motivating Example Recurrence Relations Definition general form initial conditions terms Linear Homogeneous Recurrences Form solution characteristic equation characteristic polynomial roots Second order linear homogeneous recurrence Double roots solution examples Single root example General linear homogeneous recurrences distinct roots any multiplicity Linear Nonhomogenous Recurrences Other Methods Backward substitution Recurrence trees Cheating with Maple CSCE 235 Fall 2008 Recursion 10 Recurrence Relations General Form 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 which are the initial conditions CSCE 235 Fall 2008 Recursion 11 Recurrence Relations Initial Conditions 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 is defined by the two previous terms in the sequence Initial conditions are also known as boundary conditions as opposed to general conditions From now on we will use the subscript notation so the Fibonacci numbers are fn fn 1 fn 2 f1 1 f0 1 CSCE 235 Fall 2008 Recursion 12 Recurrence Relations Terms Recurrence relations have two parts recursive terms and nonrecursive terms T n 2T n 2 n2 10 Recursive terms come from when an algorithms calls itself Non recursive terms correspond to the non recursive cost of the algorithm work the algorithm performs within a function We will see examples later First we need to know how to solve recurrences CSCE 235 Fall 2008 Recursion 13 Solving Recurrences There are several methods for solving recurrences Characteristic Equations Forward Substitution Backward Substitution Recurrence Trees Mapple CSCE 235 Fall 2008 Recursion 14 Outline Introduction Motivating Example Recurrence Relations Definition general form initial conditions terms Linear Homogeneous Recurrences Form solution characteristic equation characteristic polynomial roots Second order linear homogeneous recurrence Double roots solution examples Single root example General linear homogeneous recurrences distinct roots any multiplicity Linear Nonhomogenous Recurrences Other Methods Backward substitution Recurrence trees Cheating with Maple CSCE 235 Fall 2008 Recursion 15 Linear Homogeneous Recurrences Definition A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an c1an 1 c2an 2 ckan k with c1 c2 ck R ck 0 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 Homogeneous no terms occur that are not multiples of aj s Degree k an is expressed in terms of k terms of the sequences CSCE 235 Fall 2008 Recursion 16 Linear Homogeneous Recurrences Examples The Fibonacci sequence is a linear homogeneous recurrence relation So are the following relations 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 relations As many as the degree k k 3 8 respectively So how do solve linear homogeneous recurrences CSCE 235 Fall 2008 Recursion 17 Solving Linear Homogeneous Recurrences 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 c1rn 1 c2rn 2 ckrn k We can now divide both sides by rn k collect terms and we get a k degree polynomial rk c1rk 1 c2rk 2 ck 0 This equation is called the characteristic equation of the recurrence relation The roots of this polynomial are called the characteristics roots of the recurrence relation They can be used to find the solutions if they exist to the
View Full Document
Unlocking...