Recursion CSE235 Recursion Introduction Recurrence Relations Linear Homogeneous Recurrences Slides by Christopher M Bourke Instructor Berthe Y Choueiry Nonhomogenous Other Methods Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 7 1 7 2 of Rosen 1 47 Recursive Algorithms Recursion CSE235 A recursive algorithm is one in which objects are defined in terms of other objects of the same type Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods Advantages Simplicity of code Easy to understand Disadvantages Memory Speed Possibly redundant work 2 47 Tail recursion offers a solution to the memory problem but really do we need recursion Recursive Algorithms Analysis Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 3 47 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 Motivating Example Factorial Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences 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 Nonhomogenous Other Methods 1 2 3 4 5 6 4 47 Input n N Output n if n 1 then return 1 end else return Factorial n 1 n end Motivating Example Factorial Analysis Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 5 47 How many multiplications M n does Factorial perform Motivating Example Factorial Analysis Recursion CSE235 How many multiplications M n does Factorial perform Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 5 47 When n 1 we don t perform any Motivating Example Factorial Analysis Recursion CSE235 How many multiplications M n does Factorial perform Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 5 47 When n 1 we don t perform any Otherwise we perform 1 Motivating Example Factorial Analysis Recursion CSE235 How many multiplications M n does Factorial perform Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 5 47 When n 1 we don t perform any Otherwise we perform 1 Plus how ever many multiplications we perform in the recursive call Factorial n 1 Motivating Example Factorial Analysis Recursion CSE235 How many multiplications M n does Factorial perform Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods When n 1 we don t perform any Otherwise we perform 1 Plus how ever many multiplications we perform in the recursive call Factorial n 1 This can be expressed as a formula similar to the definition of n M 0 0 M n 1 M n 1 5 47 Motivating Example Factorial Analysis Recursion CSE235 How many multiplications M n does Factorial perform Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods When n 1 we don t perform any Otherwise we perform 1 Plus how ever many multiplications we perform in the recursive call Factorial n 1 This can be expressed as a formula similar to the definition of n M 0 0 M n 1 M n 1 This is known as a recurrence relation 5 47 Recurrence Relations I Definition Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 6 47 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 Recurrence Relations II Definition Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 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 7 47 Recurrence Relations III Definition Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 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 1 1 5 1 5 fn 2 2 5 5 your book derives this solution 8 47 Recurrence Relations IV Definition Recursion CSE235 Introduction More generally recurrences can have the form Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods T n T n f n or n T n T f n T c T c Note that it may be necessary to define several T initial conditions 9 47 Recurrence Relations V Definition Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 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 the subscript notation so the Fibonacci numbers are fn fn 1 fn 2 f1 1 f0 1 10 47 Recurrence Relations VI Definition Recursion CSE235 Introduction Recurrence relations have two parts recursive terms and non recursive terms Recurrence Relations Linear Homogeneous Recurrences Nonhomogenous Other Methods 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 11 47 Solving Recurrences Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences 2nd Order General Nonhomogenous Other Methods 12 47 There are several methods for solving recurrences Characteristic Equations Forward Substitution Backward Substitution Recurrence Trees Maple Linear Homogeneous Recurrences Recursion CSE235 Introduction Recurrence Relations Linear Homogeneous Recurrences 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 2nd Order General
View Full Document
Unlocking...