RecurrencesSlide 2RecursionRecursive algorithmsA Call Tree for fact(3)Goal: Analyzing recursive algorithmsDeriving a Recurrence Equation for a Recursive AlgorithmDeriving a Recurrence Equation for a Recursive AlgorithmSlide 9Deriving DirectSolutionCount for FactorialDeriving a GeneralCount for FactorialSolving recurrence equationsDeriving the count using the recursion tree methodIteration for binary searchBuilding the recursion treeSlide 16Example: recursive factorialAfter the first unrollingAfter the second unrollingAfter the third unrollingThe recursion treeDivide and ConquerSlide 23Slide 24Binary searchSlide 26Slide 27Worst case analysisRecursion tree for BinarySearch (BS)After first unrollingAfter second unrollingAfter third unrollingTerminating the unrollingSlide 34Merge SortMerge Sort ExampleDeriving a recurrence equation for Merge Sort:Recurrence Equation (cont’d)After first unrolling of mergeSortSlide 40Slide 41Slide 42Slide 43The sum for each depthMaster TheoremMaster method examplesRecurrences Execution of a recursive program Deriving & solving recurrence equationsRecursionWhat is the recursive definition of n! ?Programint fact(int n) {if (n<=1) return 1; else return n*fact(n-1);}// Note '*' is done after returning from fact(n-1)otherwise )1)!-((1or 0 is if 1!nnnnRecursive 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”fact(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**26Goal: 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.Deriving 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 equation When we solve the recurrence equation above we will find that T(n)=n, and any such recursive algorithm is linear in n.Deriving 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 )(ntGeneralCouizeDirectSolSsizeountDirectSolCsizeTDeriving 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kiinTDeriving DirectSolutionCount for Factorial int fact(int n) {if (n<=1) return 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)Deriving a GeneralCount 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) (if, *, -, return)The only recursive call, requiring T(n - 1) operations1for )1()1(1for )1()(nnTnnT Operationscounted in t(n)Solving recurrence equationsTechniques for solving recurrence equations:Recursion treeIteration methodRecall the time complexity analyses for n! and binary search we did on the board last timeT(n) = T(n-1) + cT(n) = T(n/2) + c (See the next slide)Master Theorem (master method)Characteristic equationsWe discuss these methods with examples.Deriving the count using the recursion tree methodRecursion trees provide a convenient way to represent the unrolling of recursive algorithmIt is not a formal proof but a good technique to compute the count.Once the tree is generated, each node contains its “non recursive number of operations” t(n) or DirectSolutionCountThe count is derived by summing the “non recursive number of operations” of all the nodes in the treeFor convenience we usually compute the sum for all nodes at each given depth, and then sum these sums over all depths.Iteration for binary search         W n W nW n W nW n W nk W n k W kn nk( ) ( / )( ( / / )) ( / )( ( / )) ( / )...( / ) ( )lg (lg )                1 21 1 2 2 2 42 1 8 3 82 1 11 Building the recursion treeThe initial recursion tree has a single node containing two fields: The recursive call, (for example Factorial(n)) and the corresponding count T(n) .The tree is generated by: unrolling the recursion of the node depth 0, then unrolling the recursion for the nodes at depth 1, etc.The recursion is unrolled as long as the size of the recursive call is greater than DirectSolutionSizeBuilding the recursion treeWhen the “recursion is unrolled”, each current leaf node is substituted by a subtree containing a root and a child for each recursive call done by the algorithm.The root of the subtree contains the recursive call, and the corresponding “non recursive count”.Each child node contains a recursive call, and its corresponding count.The unrolling continues,