Bài giảng An Introduction to Computer Science Using Java - Chapter 14 Recursion

Chapter 14RecursionLecture Slides to AccompanyAn Introduction to Computer Science Using Java (2nd Edition)byS.N. Kamin, D. Mickunas, , E. ReingoldChapter PreviewIn 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(e.g. quicksort, merge sort, Guaussian elmination)introduce the linked list data structure and recursive implementations for several of its methodspresent programs for drawing two types of fractal curvesRecursionBasic problem solving technique is to divide a problem into smaller subproblemsThese subproblems may also be divided into smaller subproblemsWhen the subproblems are small enough to solve directly the process stopsA recursive algorithm is a problem solution that has been expressed in terms of two or more easier to solve subproblemsCounting DigitsRecursive definitiondigits(n) = 1 if (–9 0) { insertionSort(A, hi – 1); insertInOrder(A, hi, A[hi)); }}Insert in Orderprivate static void insertInOrder (double[] A, int hi, double x) { // Insert x into A[0]..A[hi-1], // filling in A[hi} in the process. // A[0]..A[hi – 1] are sorted. if ((hi == 0) || (A[hi – 1] lo + 1) { // 3 or more subarray values m = partition(A, lo, hi); quickSort(A, lo, m – 1); quickSort(A, m + 1, hi); } else // less than 3 subarray values if ((hi == lo + 1) && (A[lo] > A[hi]) swap(A, lo, hi);}Partitionstatic int partition (double[] A, int lo, int hi) {// choose middle element from A[lo}..A[hi]// move elements so A[lo]..A[m-1] are all A[m] swap(A, lo, medianLocationA, lo+1, hi, (lo+hi)/2)); int m = partition(A, lo+1, hi, A[lo]); swap(A, lo, m); return m;} Partition Helperstatic int partition (double[] A, int lo, int hi, double pivot) { if (hi == lo) if (A[lo] < pivot) return lo; else return lo – 1; else if (A[lo] <= pivot) // A[lo] in correct half return partition(A, lo + 1, hi, pivot); else { // A[lo] in wrong half swap(A, lo, hi); return parition(A, lo, hi – 1, pivot); } }Median Locationstatic int medianLocation (double[] A, int i, int j, int k) { if (A[i] <= A[j]) if (A[j] < A[k]) return j;0 else if (A[i] <= A[k]) return k; else return i; else // A[j] < A[i] if (A[i] <= A[k]) return i; else if (A9j] <= A[k]) return k; else return j;}Linear Systemsa11x1 + a12x2 + + a1nxn = b1 a11x1 + a12x2 + + a1nxn = b1 a11x1 + a12x2 + + a1nxn = b1 Solving Linear Systemssolve (System E of n equations in n unkonwns) { if (n == 1) // system is ax = b return (b/a); else { eliminate last equation yielding system E’; solve(E’), yielding x1, ,xn-1; xn = (bn – an,1x1 - - a1,n-2xn-1)/ an,n return (x1, , xn-1, xn); }}Integer List Classclass IntList { private int value; private IntList tail; public IntList(int v, IntList next) { value = v; tail = next; } public int getValue () { return value; } public intList getTail (){ return Tail; }Constructing a Linked ListOne approach would be:IntList list = new IntList(-14, null);list = new IntList(616, list);list = new IntList(10945, list);list = new IntList(17, list);Alternatively we could have written:IntList list = new IntList(17, new IntList(616, new IntList(10945, new IntList(17, null))));Constructing a Linked List from Input Intlist readReverseList () { int inputval; IntList front = null; Inputbox in = new IntputBox(); while (true){ inputval = in.readInt(); if (in.eoi)) break; front = new IntList(inputval, front); } return front;}Printing Linked Listvoid print (IntList list) { Output out new OutputBox(); while (list != null) { out.print(list.getValue() + “ “); list = list.getTail(); } out.println();}Computing List Length This method would be added to IntListpublic int length() { if (tail == null) return 1; else return 1 + tail.length();}Converting List to StringThis method would be added to IntListpublic String toString() { String myValue = Integer.toString(value); if (tail == null) return myValue; else return myValue + “, “ + tail.toString();}Retrieving nth List ElementThis method would be added to IntListpublic IntList nth(int n) { if (n = 0) return this; else if (tail == null) return null; else return tail.nth(n – 1);}Adding Element to End of ListThis method would be added to IntListpublic void addToEndM(int n) { if (tail != null) // in the middle of the list tail.addToEndM(n); else // at last cell tail = new IntList(n, null);}Adding Element to List in OrderThis method would be added to IntListpublic IntList addInorderM(int n) { if (n < value) return new IntList(n, this); else if (n == value) return this; if (tail != null){ tail = new IntList(n, null); return this; } else{ tail = tail.addInorderM(n); return this; }}MergeSortpublic static IntList mergeSort (IntList L) {// Sort L by recursively splitting and merging if ((L == null) || (L.getTail() == null); // zero or one item return L; else { // two or more items // Split the list into two parts IntListPair p = L.split(); // Sort and merge the two parts return mergeSort(p.x).merge(mergeSort(p.y)); }}IntListPairclass IntListPair { public IntList x, y; public IntListPair (IntList x, IntList y) { this.x = x; this.y = y; }}Splitting the ListThis method would be added to IntListPairpublic IntList split() { if (tail != null) return = new IntListPair(this, null); else{ IntListPair p = tail.split(); return new IntListPair(new IntList(value,p.y),p.y); }}Merging the ListaThis method would be added to IntListIntList merge(IntList L) { if (L = null) return this; if (value < L.value) if (tail == null) return new IntList(value, L); else return new IntList(value, tail.merge(L)); return new return new IntList(L.value,merge(L.tail)); }}