Simple Recursive AlgorithmsA short list of categoriesSimple recursive algorithmsSome example algorithmsFactorialPermutationsFinding all permutations of n objectsA program to find permutationspermutationsOf(String), part IpermutationsOf(String), part IIInsert in all positionsTreesTree traversalsFlood fillQuicksortTowers of HanoiSolution to Towers of HanoiAckermann’s functionRecursion isn’t necessaryTree traversals, againLoops aren’t necessaryClosing commentsThe EndJan 14, 2019Simple Recursive Algorithms2A short list of categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithms3Simple recursive algorithmsA simple recursive algorithm:Solves the base cases directlyRecurs with a simpler subproblem or subproblemsMay do some extra work to convert the solution to the simpler subproblem into a solution to the given problemI call these “simple” because several of the other algorithm types are inherently recursive4Some example algorithmsWe will look briefly at the following simple recursive algorithms:FactorialAll permutationsTree traversalFlood fillQuicksortTowers of HanoiAckermann’s functionWe will also consider the equivalence of loops and recursion5FactorialThe factorial function is the “Hello World” of recursionpublic static long factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1);}The problem with this example is that it can be done almost as easily with a loop (so why bother learning recursion?)public static long factorial(int n) { int result = 1; while (n > 1) { result *= n; n--; }}In the following slides, we look at some example problems for which recursion really is simpler6PermutationsA permutation of a set of objects is a particular ordering of those objectsWhen we speak of “all permutations” of a set, we mean all possible ways of ordering those objectsExamples:Given the empty set { }, the only possible permutation is { }Given the set {A}, the only possible permutation is {A}Given the set {A, B}, the possible permutations are {AB, BA}Given the set {A, B, C}, the possible permutations are{ABC, ACB, BAC, BCA, CAB, CBA}Etc.7Finding all permutations of n objectsTo find all permutations of n objects:Find all permutations of n-1 of those objectsInsert the remaining object into all possible positions of each permutation of n-1 objectsExample: To find all permutations of 3 objects {A, B, C}Find all permutations of 2 of the objects, say B and C: B C and C BInsert the remaining object, A, into all possible positions (marked by ^) in each of the permutations of B and C: ^ B ^ C ^ and ^ C ^ B ^ ABC BAC BCA ACB CAB CBA8A program to find permutationsWe will develop complete Java code to find all permutations of a nonempty String of charactersArrayList<String> permutationsOf(String s) { if (s.length() == 1) { // return a new ArrayList containing just s } else { // separate the first character from the rest // get all permutationsOf ( the rest of the characters ) // for each permutation, // add the first character in all possible positions, and // put each result into a new ArrayList } // return the new ArrayList}9permutationsOf(String), part IArrayList<String> permutationsOf(String s) { ArrayList<String> result = new ArrayList<String>(); if (s.length() == 1) { // base case // return a new ArrayList containing just s result.add(s); return result; } // continued...10permutationsOf(String), part II else { // separate the first character from the rest char first = s.charAt(0); String rest = s.substring(1); // get all permutationsOf the rest of the characters ArrayList<String> simpler = permutationsOf(rest); // recursive step // for each permutation, for (String permutation : simpler) { // extra work // add the first character in all possible positions, and ArrayList additions = insertAtAllPositions(first, permutation); // put each result into a new ArrayList result.addAll(additions); } return result; }}11Insert in all positionsGiven one String representing one permutation of n-1 characters, we want to return all permutations resulting from inserting a given character in all n possible positions private ArrayList<String> insertAtAllPositions(char ch, String s) { ArrayList<String> result = new ArrayList<String>(); for (int i = 0; i <= s.length(); i++) { String inserted = s.substring(0, i) + ch + s.substring(i); result.add(inserted); } return result;}12A tree is composed of nodesEach node contains a valueEach node may have childrenOne special node is called the root of the treeNodes with children are called internal nodesNodes without children are called leavesTreesACB D EGF H J KIL M Nrootinternal nodesleaves13Tree traversalsIt’s easy to traverse (“walk”) a tree recursivelyHere’s a recursive method which, if called with the root of a tree, will print out all the values in the tree:void printTree(Node n) { print the value in node n; for each child c of n, printTree(c)Or, in actual Java:void printTree(Node n) { System.out.println(n.getValue()); Iterator iter = node.getChildren().iterator(); while (iter.hasNext()) { printTree(iter.next()); }}Many data structures are best handled recursively14Flood fillTo “flood fill” an area with color oldColor, starting from a particular pixel of color newColor:void floodFill(Pixel p, Color oldColor, Color newColor) { if p is not oldColor, just return else { set color of p to newColor for each pixel q adjacent to p (horizontally or vertically), floodFill(q, oldColor, newColor) }}15QuicksortQuicksort is (in some sense) the fastest sorting algorithm knownFrom an array of numbers, pick one to use as a pivot45 3 17 48 72 25 8 99 14 9 12 21 81 64 33 12(we’ll use 45 as the pivot)Partition the numbers into those smaller than or equal to the pivot, and those larger than the pivot3 17 25 8 14 9
View Full Document
Unlocking...