Recursion and Recurrence EquationsRecursionRecursive algorithmsA Call Tree for fact(3)Slide 5Slide 6Goal: Analyzing recursive algorithmsDeriving a Recurrence Equation for a Recursive AlgorithmDeriving a Recurrence Equation for a Recursive AlgorithmSlide 10Deriving DirectSolutionCount for FactorialDeriving a GeneralCount for FactorialDeriving a Recurrence Equation for MysteryDeriving a DirectSolutionCount for MysteryDeriving a GeneralCount for MysterySlide 16Deriving a Recurrence Equation for MultiplySlide 18Deriving a recurrence equation for minimumSlide 20Deriving a recurrence equation for Merge Sort:Recurrence Equation for cost.Computing xnRecursion - PowerDeriving a Recurrence Equation for PowerRecursion and Recurrence Equations•The execution of a recursive program• Deriving recurrence equations01/14/19 Cutler/Head 2Recursion•What is the recursive definition of n! ?•Translating to Java/cint fact(int n) {if (n<=1) return 1; // Note '*' is done after returning from fact(n-1)else return n*fact(n-1);}otherwise )1)!-((1or 0 is if 1!nnnn01/14/19 Cutler/Head 3Recursive algorithms•A recursive algorithm typically contains recursive calls to the same algorithm•In order for the recursive algorithm to terminate, it must contain code for solving directly some “base case(s)”•A direct solution does not include recursive calls. •We use the following notation:•DirectSolutionSize is the “size” of the base case•DirectSolutionCount is the count of the number of operations done by the “direct solution”01/14/19 Cutler/Head 4fact(3)321fact(2)fact(1)A Call Tree for fact(3)The Run Time Environment •The following 2 slides show the program stack after the third call from fact(3)•When a function is called an activation records('ar') is created and pushed on the program stack.•The activation record stores copies of local variables, pointers to other ‘ar’ in the stack and the return address.•When a function returns the stack is popped.int fact(int n) {if (n<=1) return 1;else return n*fact(n-1);}returns 61**2601/14/19 Cutler/Head 5ep2Program stackValfact: <ipF,ep0>N =3function value [=?]return addressstatic link = ep0dynamic link =ep1free memoryAR(Driver)AR(fact 3)Snapshot of the environmentat end of third call to factep0N =2function value [=?]return addressstatic link = ep0dynamic link =ep2AR(fact 2)ep1EPN =1function value [=1]return addressstatic link = ep0dynamic link = EPAR(fact 1)AR=Activation Recordep= environmental pointerEPProgram stackValfact: <ipF,ep0>N =3function value [=?]return addressstatic link = ep0dynamic link = ep1free memoryAR(Driver)AR(fact 3)Snapshot of the environmentat end of second call to factep0N =2function value [=2]return addressstatic link = ep0dynamic link = EPAR(fact 2)ep101/14/19 Cutler/Head 6EPProgram stackValfact: <ipF,ep0>N =3function value [=6]return addressstatic link = ep0dynamic link = EPfree memoryAR(Driver)AR(fact 3)Snapshot of the environmentat end of first call to factep0EPProgram stackValfact: <ipF,ep0>free memoryAR(Driver)Snapshot of the environmentafter fact l returns01/14/19 Cutler/Head 7Goal: Analyzing recursive algorithms•Until now we have only analyzed (derived a count) for non-recursive algorithms.•In order to analyze recursive algorithms we must learn to:•Derive the recurrence equation from the code•Solve recurrence equations.01/14/19 Cutler/Head 8Deriving a Recurrence Equation fora Recursive Algorithm •Our goal is to compute the count (Time) T(n) as a function of n, where n is the size of the problem•We will first write a recurrence equation for T(n)For example T(n)=T(n-1)+1 and T(1)=0•Then we will solve the recurrence equationWhen we solve the recurrence equation above we will find that T(n)=n, and any such recursive algorithm is linear in n.Solving: Next lecture01/14/19 Cutler/Head 9Deriving a Recurrence Equation for a Recursive Algorithm 1. Determine the “size of the problem”. The count T is a function of this size2. Determine DirectSolSize, such that for size DirectSolSize the algorithm computes a direct solution, and the DirectSolCount(s).otherwise )(ntGeneralCouizeDirectSolSsizeountDirectSolCsizeT01/14/19 Cutler/Head 10Deriving a Recurrence Equation for a Recursive Algorithm To determine GeneralCount:3. Identify all the recursive calls done by a single call of the algorithm and their counts, T(n1),…,T(nk) and compute RecursiveCallSum =4. Determine the “non recursive count” t(size) done by a single call of the algorithm, i.e., the amount of work, excluding the recursive calls done by the algorithmotherwise )(Re )(sizetlSumcursiveCalizeDirectSolSsizeountDirectSolCsizeT)(1kiinT01/14/19 Cutler/Head 11Deriving DirectSolutionCount for Factorial int fact(int n) {if (n<=1) return 1; // Note '*' is done after returning from fact(n-1)else return n*fact(n-1);1. Size = n 2.DirectSolSize is (n<=1)3. DirectSolCount is (1)The algorithm does a small constant number of operations (comparing n to 1, and returning)01/14/19 Cutler/Head 12Deriving a G eneralCount for Factorial int fact(int n) {if (n<=1) return 1; // Note '*' is done after returning from fact(n-1)else return n * fact(n-1);3. RecursiveCallSum = T( n - 1)4. t(n) = (1) (for if, *, -, return)The only recursive call, requiring T(n - 1) operations1for )1()1(1for )1()(nnTnnT Operationscounted in t(n)01/14/19 Cutler/Head 13Deriving a Recurrence Equation for MysteryIn this example we are not concerned with what mystery computes. Our goal is to simply write the recurrence equationmystery (n)1. if n  12. then return n3. else return (5 * mystery(n -1) -6* mystery(n -2) )01/14/19 Cutler/Head 14Deriving a DirectSolutionCount for Mystery1. Size = n2. DirectSolSize is (n<=1)3. DirectSolCount is (1) The algorithm does a small constant number of operations (comparing n to 1, and returning) 1for 1for )1()(nntGeneralCounnT01/14/19 Cutler/Head 15Deriving a G eneralCount for Mysterymystery (n)1. if n  12. then return n3. else return (5 * mystery(n -1) -6 * mystery(n - 2) )A recursive call toMystery requiring T(n - 1)A recursive call toMystery requiring T(n - 2)Operations counted in t(n)01/14/19 Cutler/Head 16Deriving a Recurrence Equation for Mystery3. RecursiveCallSum = T(n-1) + T(n-2)4. t (n)= (1)The non recursive count includes the comparison n<=1, the 2 multiplications,