CS116 Chapter Notes - Chapter 4: Quicksort, Sorting Algorithm, Insertion Sort
24 Aug 2016
School
Department
Course
Professor
Document Summary
Based on recursive definition of input data values. Standard templates accumulative recursion some algorithms do not fall into either of these categories builds up intermediate results on recursive calls specialized template. Gcd the greatest common divisor of 2 natural numbers is the largest natural number that divides evenly into both. Write the gcd function using the standard count down template gcd (m, 0) = m gcd (m, n) = gcd (n, m mod n) not structural (not counting up or down by 1), not accumulative. Generative recursion still has a base case still has a recursive case, but problem is broken down in a new way allows more creativity in solutions removes restrictions on solutions may allow for improved efficiency. May be more intuitive for some problems breaking into more natural subproblems: divide the problem into subproblems, determine base cases figure out how to combine subproblem solutions to solve the original problem.
