RecursionCMSC 433Bill Pugh andNelson Padua-PerezFixed schedule• Project 5 - Dense bags and Markov text– Due next Thursday, April 6th• 2nd Midterm, Monday, April 10th• Readings from now to midterm:– Chapter 7: Recursion– Section 8.1: Tree terminologyRecursionaka divide and conquor• General approach to solving problems• If the problem instance is simple/trivial, solve itdirectly• Otherwise,– break the problem instance down into one or moresmaller instances– solve them– combine solutions from smaller instances to getsolution for entire problemHow many ways are there toorder the numbers 1..n?• permutation(1) = 1• permutation(n) =– n different numbers that could occur first– remaining elements could appear inpermutation(n-1) different orders• thus, permutation(n) = n * permutation(n-1)= n!Iteration/Recursion• Iteration over a list/sequence is very similar to usingrecursion to combine the result from the first elementwith the result from the rest of the list– int countVowels(String s) { if (s.length() == 0) return 0; int tailResult = countVowels(s.substring(1)); switch (s.charAt(1)) { case ‘a’: case ‘e’: case ‘i’: case ‘o’: case ‘u’: return tailResult+1; default: return tailResult; }}Counting vowels with iteration– int countVowels(String s) { int result = 0; for(int i = 0; i < s.length(); i++) { switch (s.charAt(i)) { case ‘a’: case ‘e’: case ‘i’: case ‘o’: case ‘u’: result++; break; }return result;}Boring recursion• Using recursion where iteration would workjust as well isn’t that exciting– sometimes, a little to think about it as a recursiveproblem– In Java, it isn’t particularly efficient for long listsor deep recursion– In some languages (such as Scheme) that supporttail recursion, it is as efficient as iteration. In fact, itcan be the only/preferred way to implementiteration• has to be a special kind of recursion, called tail recursionSome interesting recursion• Binary search• Quicksort• MergesortnQueens• Place queens on a boardsuch that every row andcolumn contains onequeen, but no queen canattack another queen– place queens on nxn board– recursive approach: assumeyou’ve already placed kqueensrecursive permutationgeneration• Define a functioncalculatePermutations(int [] a)• that generates each permutation of a and callshandlePermutation(int [] a)• with each generated permutation• Hint: define a recursive helper functioncalculatePermutations(int [] a, int k)• permutes the values in a[k ... a.length-1]Change making• We’ve been asked to help devise a new set ofcoins for a country ruled by a mathematician.• Our task is to figure out what the denominations ofthe coins should be.– For example, in the US, the coins have denominations(in pennies) of: 1, 5, 10, 25 (we'll ignore half dollars fornow)• Assume we want to have only three coins.• What values should the coins have so as tominimize the average number of coins needed tomake any number of cents from 0 to 99.Greedy vs. nonGreedy• Greedy approach:– use as many of the largest coin possible, then go tothe next largest coin• Greedy is not always optimal– If your coins are 25, 10, 1, then to make change for30 cents, the greedy approach requires 6 coinswhereas only 3 dimes are required• For US coins, greedy is
View Full Document
Unlocking...