IntroductionRecurrence RelationsLinear Homogeneous Recurrences2nd OrderGeneralNonhomogeneousOther MethodsBack SubstitutionRecurrence TreesMapleRecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecursionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 6.1 - 6.2 of [email protected] / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecursive AlgorithmsA recursive algorithm is one in which objects are defined interms of other objects of the same type.Advantages:Simplicity of codeEasy to understandDisadvantages:MemorySpeedPossibly redundant workTail recursion offers a solution to the memory problem, butreally, do we need recursion?2 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecursive AlgorithmsAnalysisWe’ve already seen how to analyze the running time ofalgorithms. However, to analyze recursive algorithms, werequire more sophisticated techniques.Specifically, we study how to define & solve recurrencerelations.3 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating 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) × n5end64 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.5 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.6 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.7 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.8 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.9 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsMotivating ExampleFactorial - Analysis?How many multiplications M(n) does Factorial perform?When n = 1 we don’t perform any.Otherwise we perform 1.Plus how ever many multiplications we perform in therecursive call, Factorial(n − 1).This can be expressed as a formula (similar to thedefinition of n!.M(0) = 0M(n) = 1 + M (n − 1)This is known as a recurrence relation.10 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecurrence Relations IDefinitionDefinitionA recurrence relation for a sequence {an} is an equation thatexpresses anin terms of one or more of the previous terms inthe sequence,a0, a1, . . . , an−1for all integers n ≥ n0where n0is a nonnegative integer.A sequence is called a solution of a recurrence relation if itsterms satisfy the recurrence relation.11 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecurrence Relations IIDefinitionConsider the recurrence relation: an= 2an−1− an−2.It has the following sequences anas solutions:1an= 3n,2an= 2n, and3an= 5.Initial conditions + recurrence relation uniquely determine thesequence.12 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecurrence 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).13 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecurrence 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 define several T (δ), initialconditions.14 / 81RecursionCSE235IntroductionRecurrenceRelationsLinearHomogeneousRecurrencesNon-homogenousOtherMethodsRecurrence Relations VDefinitionThe initial conditions specify the value of the first fewnecessary terms in the sequence. In the Fibonacci numbers weneeded two initial conditions, F (0) = F (1) = 1 since F (n) wasdefined by the two 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 theFibonacci numbers
View Full Document
Unlocking...