In this chapter we will: introduce recursion as a programming technique, show how recursion can be used to simplify the design of complex algorithms, present several well known recursive algorithms (. quicksort, merge sort, Guaussian elmination), introduce the linked list data structure and recursive implementations for several of its methods, present programs for drawing two types of fractal curves. | Chapter 14 Recursion Lecture Slides to Accompany An Introduction to Computer Science Using Java (2nd Edition) by . Kamin, D. Mickunas, , E. Reingold Chapter Preview In this chapter we will: introduce recursion as a programming technique show how recursion can be used to simplify the design of complex algorithms present several well known recursive algorithms (. quicksort, merge sort, Guaussian elmination) introduce the linked list data structure and recursive implementations for several of its methods present programs for drawing two types of fractal curves Recursion Basic problem solving technique is to divide a problem into smaller subproblems These subproblems may also be divided into smaller subproblems When the subproblems are small enough to solve directly the process stops A recursive algorithm is a problem solution that has been expressed in terms of two or more easier to solve subproblems Counting Digits Recursive definition digits(n) = 1 if (–9 <= n <= 9) 1 + digits(n/10) otherwise Example digits(321) = 1 + digits(321/10) = 1 +digits(32) = 1 + [1 + digits(32/10)] = 1 + [1 + digits(3)] = 1 + [1 + (1)] = 3 Counting Digits in Java int numberofDigits(int n) { if ((-10 < n) && (n < 10)) return 1 else return 1 + numberofDigits(n/10); } Recursion If you want to compute f(x) but can’t compute it directly Assume you can compute f(y) for any value of y smaller than x Use f(y) to compute f(x) For this to work, there has to be at least one value of x for which f(x) can be computed directly (. these are called base cases) Evaluating Exponents Recurisivley static int power(int k, int n) { // raise k to the power n if (n == 0) return 1; else return k * power(k, n – 1); } Divide and Conquer Using this method each recursive subproblem is about one-half the size of the original problem If we could define power so that each subproblem was based on computing kn/2 instead of kn – 1 we could use the divide and conquer principle Recursive divide and conquer algorithms | Chapter 14 Recursion Lecture Slides to Accompany An Introduction to Computer Science Using Java (2nd Edition) by . Kamin, D. Mickunas, , E. Reingold Chapter Preview In this chapter we will: introduce recursion as a programming technique show how recursion can be used to simplify the design of complex algorithms present several well known recursive algorithms (. quicksort, merge sort, Guaussian elmination) introduce the linked list data structure and recursive implementations for several of its methods present programs for drawing two types of fractal curves Recursion Basic problem solving technique is to divide a problem into smaller subproblems These subproblems may also be divided into smaller subproblems When the subproblems are small enough to solve directly the process stops A recursive algorithm is a problem solution that has been expressed in terms of two or more easier to solve subproblems Counting Digits Recursive definition digits(n) = 1 if (–9 <= n <= 9) 1 + .
