RecursionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 6.1 - 6.2 of [email protected] AlgorithmsA recursive algorithm is one in which objects are defined in termsof other objects of the same type.Advantages:ISimplicity of codeIEasy to understandDisadvantages:IMemoryISpeedIPossibly redundant workTail recursion offers a solution to the memory problem, but really,do we need recursion?NotesRecursive AlgorithmsAnalysisWe’ve already seen how to analyze the running time of algorithms.However, to analyze recursive algorithms, we require moresophisticated techniques.Specifically, we study how to define & solve recurrence relations.NotesMotivating ExampleFactorialRecall the factorial function.n! =1 if n = 1n · (n − 1)! if n > 1Consider the following (recursive) algorithm for computing n!:Algorithm (Factorial)Input : n ∈ NOutput : n!if n = 1 then1return 12end3else4return Factorial(n − 1) × n5end6NotesMotivating ExampleFactorial - Analysis?How many multiplications M (n) does Factorial perform?IWhen n = 1 we don’t perform any.IOtherwise we perform 1.IPlus how ever many multiplications we pe rform in therecursive call, Factorial(n − 1).IThis can be expressed as a formula (similar to the definition ofn!.M(0) = 0M(n) = 1 + M(n − 1)IThis is known as a recurrence relation.NotesRecurrence Relations IDefinitionDefinitionA recurrence relation for a sequence {an} is an equation thatexpresses anin terms of one or more of the previous terms in thesequence,a0, a1, . . . , an−1for all integers n ≥ n0where n0is a nonnegative integer.A sequence is called a solution of a recurrence relation if its termssatisfy the recurrence relation.NotesRecurrence Relations IIDefinitionConsider the recurrence relation: an= 2an−1− an−2.It has the following sequences anas solutions:1. an= 3n,2. an= 2n, and3. an= 5.Initial conditions + recurrence relation uniquely determine thesequence.NotesRecurrence Relations IIIDefinitionExampleThe Fibonacci numbers are defined by the recurrence,F (n) = F (n − 1) + F (n − 2)F (1) = 1F (0) = 1The solution to the Fibonacci recurrence isfn=1√5 1 +√52!n−1√5 1 −√52!n(your book derives this solution).NotesRecurrence Relations IVDefinitionMore generally, recurrences can have the formT (n) = αT (n − β) + f(n), T (δ) = corT (n) = αTnβ+ f(n), T (δ) = cNote that it may be necessary to defi ne several T (δ), initialconditions.NotesRecurrence Relations VDefinitionThe initial conditions specify the value of the first few necess aryterms in the sequence. In the Fibonacci numbers we needed twoinitial conditions, F (0) = F (1) = 1 since F (n) was defined by thetwo previous terms in the sequence.Initial conditions are also known as boundary conditions (asopposed to the general conditions).From now on, we will use the subscript notation, so the Fibonaccinumbers arefn= fn−1+ fn−2f1= 1f0= 1NotesRecurrence Relations VIDefinitionRecurrence relations have two parts: recursive terms andnon-recursive terms.T (n) = 2T (n − 2)| {z }recursive+ n2− 10| {z }non-recrusiveRecursive terms come from when an algorithm calls itself.Non-recursive terms correspond to the “non-recursive” cost of thealgorithm—work the algorithm performs within a function.We’ll see some examples later. First, we need to know how tosolve recurrences.NotesSolving RecurrencesThere are several methods for solving recurrences.ICharacteristic EquationsIForward SubstitutionIBackward SubstitutionIRecurrence TreesIMaple!NotesLinear Homogeneous RecurrencesDefinitionA linear homogeneous recurrence relation of degree k withconstant coefficients is a recurrence re lation of the forman= c1an−1+ c2an−2+ ··· + ckan−kwith c1, . . . , ck∈ R, ck6= 0.ILinear: RHS is a sum of multiples of previous terms of thesequence (linear combination of previous terms). Thecoefficients are all constants (not functions depending on n).IHomogeneous: no terms occur that are not multiples of theaj’s.IDegree k: anis expressed in terms of k terms of the sequence.NotesLinear Homogeneous RecurrencesExamplesExamplesThe Fibonacci sequence is a linear homogeneous recurrencerelation. As are the following.an= 4an−1+ 5an−2+ 7an−3an= 2an−2+ 4an−4+ 8an−8How many initial conditions do we need to spec ify for these? Asmany as the degree, k = 3, 8 resp ec tively.So, how do we solve linear homogeneous recurrences?NotesSolving Linear Homogeneous Recurrences IWe want a solution of the form an= rnwhere r is some (real)constant.We observe that an= rnis a solution to a linear homogeneousrecurrence if and only ifrn= c1rn−1+ c2rn−2+ ··· + ckrn−kWe can now divide both sides by rn−k, collect terms, and we ge t ak-degre e polynomial.rk− c1rk−1− c2rk−2− ··· − ck−1r − ck= 0NotesSolving Linear Homogeneous Recurrences IIrk− c1rk−1− c2rk−2− ··· − ck−1r − ck= 0This is called the characteristic equation of the recurrence relation.The roots of this polynomial are called the characteristic roots ofthe recurrence relation. They can be used to find solutions (if theyexist) to the recurrence relation. We will consider several cases.NotesSecond Order Linear Homogeneous RecurrencesA second order linear homogeneous recurrence is a recurrence ofthe forman= c1an−1+ c2an−2Theorem (Theorem 1, p414)Let c1, c2∈ R and suppose that r2− c1r − c2= 0 is thecharacteristic polynomial of a 2nd order linear homogeneousrecurrence which has two distinct1roots, r1, r2.Then {an} is a solution if and only ifan= α1rn1+ α2rn2for n = 0, 1, 2, . . . where α1, α2are constants dependent upon theinitial conditions.1we discuss how to handle this situation later.NotesSecond Order Linear Homogeneous RecurrencesExampleExampleFind a solution toan= 5an−1− 6an−2with initial conditions a0= 1, a1= 4IThe characteristic polynomial isr2− 5r + 6IUsing the quadratic formula (or common sense), the root canbe found;r2− 5r + 6 = (r − 2)(r − 3)so r1= 2, r2= 3NotesSecond Order Linear Homogeneous RecurrencesExample ContinuedIUsing the 2nd-order theorem, we have a solution,an= α1(2n) + α2(3n)INow we can plug in the two initial conditions to get a systemof linear equations.a0= α1(2)0+ α2(3)0a1= α1(2)1+ α2(3)11 = α1+ α2(1)4 = 2α1+ 3α2(2)NotesSecond Order Linear Homogeneous RecurrencesExample ContinuedISolving for α1= (1 − α2) in (1), we can plug it into
View Full Document
Unlocking...