CompSci 100E12.1Solving Problems Recursivelyÿ Recursion is an indispensable tool in a programmer’s toolkitþ Allows many complex problems to be solved simplyþ Elegance and understanding in code often leads to betterprograms: easier to modify, extend, verify (and sometimes moreefficient!!)þ Sometimes recursion isn’t appropriate, when it’s bad it can bevery bad---every tool requires knowledge and experience in howto use itÿ The basic idea is to get help solving a problem fromcoworkers (clones) who work and act like you doþ Ask clone to solve a simpler but similar problemþ Use clone’s result to put together your answerÿ Need both concepts: call on the clone and use the resultCompSci 100E12.2Print words entered, but backwardsÿ Can use a vector, store all the words and print inreverse orderþ The vector is probably the best approach, but recursion works toovoid printReversed() { // some I/O details omittedString word;word = console.readLine();if (word.length() > 0) { // get something?printReversed(); // print the rest reversedSystem.out.println(word); // then print the word}}// somewhere in main---.printReversed();þ The function printReversed reads a word, prints the word onlyafter the clones finish printing in reverse orderþ Each clone has its own version of the code, its own word variableCompSci 100E12.3Exponentiationÿ Computing xnmeans multiplying n numbers (ordoes it?)þ What’s the easiest value of n to compute xn?þ If you want to multiply only once, what can you ask aclone?/** @return x^n */double power(double x, int n){if (n == 0){return 1.0;}return x * power(x, n-1);}ÿWhat about an iterative version?CompSci 100E12.4Faster exponentiationÿ How many recursive calls are made t o computer 21024?þ How many multiplies on each call? Is this better?/** @return x^n */double power(double x, int n){if (n == 0) {return 1.0;}double semi = power(x, n/2);if (n % 2 == 0) {return semi*semi;}return x * semi * semi;}ÿ What about an iterative version of this function?CompSci 100E12.5Keys to Recursionÿ Recursive functions have two key attributesþ There is a base case, sometimes called the halting or exit case,which does notmake a recursive callo See print reversed, exponentiation, factorial for examplesþ All other cases make a recursive call, with some parameter orother measure that decreases or moves towards the base caseo Ensure that sequence of calls eventually reaches the base caseo “Measure” can be tricky, but usually it’s straightforwardÿ Example: sequential search in a vectorþ If first element is search key, done and returnþ Otherwise look in the “rest of the vector”þ How can we recurse on “rest of vector”?CompSci 100E12.6Classic examples of recursionÿ For some reason, computer science uses these examples:þ Factorial: we can use a loop or recursion. Is this an issue?þ Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, …o F(n) = F(n-1) + F(n-2), why isn’t this enough? What’s needed?o Classic example of bad recursion, to compute F(6), the sixthFibonacci number, we must compute F(5) and F(4). What dowe do to compute F(5)? Why is this a problem?þ Towers of Hanoio N disks on one of three pegs, transfer all disks to anotherpeg, never put a disk on a smaller one, only on largero Every solution takes “forever” when N, number of disks, islargeCompSci 100E12.7Fibonacci: Don’t do this recursivelylong recFib(int n)// precondition: 0 <= n// postcondition: returns// the n-th Fibonacci// number{if (0 == n || 1 == n) {return 1;}else {return recFib(n-1) +recFib(n-2);}}ÿ How many clones/calls tocompute F(5)?543 232021110101How many calls of F(1)?How many total calls?consider caching codeCompSci 100E12.8Towers of Hanoiÿ The origins of the problem may bein the far eastÿ Move n disks from one peg toanother in a set of threevoid move(int from, int to, int aux,int numDisks)// pre: numDisks on peg # from,// move to peg # to// post: disks moved from peg 'from‘// to peg 'to' via 'aux'{if (numDisks == 1) {System.out.println("move " +from+"to"+to);}else {move(from,aux,to, numDisks - 1);move(from,to,aux, 1);move(aux,to,from, numDisks - 1);}}Peg#1 #2 #3CompSci 100E12.9What’s better: recursion/iteration?ÿ There’s no single answer, many factors contributeþ Ease of developing code assuming other factors okþ Efficiency (runtime or space) can matter, but don’t worry aboutefficiency unless you know you have toÿ In some examples, like Fibonacci numbers, recursive solutiondoes extra work, we’d like to avoid the extra workþ Iterative solution is efficientþ The recursive inefficiency of “extra work” can be fixed if weremember intermediate solutions: instance variablesÿ Instance variable: maintains value over all function callsþ Local variables created each time function calledCompSci 100E12.10Fixing recursive Fibonaccilong[] storage = new long[31];long recFib(int n) {// pre: 0 <= n <= 30// post: returns the n-th Fibonacci numberArrays.fill(storage, 0);return recF (n);}long recF(int n){if (0 == n || 1 == n) return 1;else if (storage[n] != 0) return storage[n];else {storage[n] = recF(n-1) + recF(n-2);return storage[n];}}ÿWhat does storage do? Why initialize to all zeros?þ Instance variables initialized first time function calledþ Maintain values over calls, not reset or re-initializedCompSci 100E12.11Thinking recursivelyÿ Problem: find the largest element in a vectorþ Iteratively: loop, remember largest seen so farþ Recursive: find largest in [1..n], then compare to 0thelementdouble max(double[] a)// pre: a contains a.length elements, 0 < a.length// post: return maximal element of a{int k;double max = a[0];for(k=0; k < a.size(); k++) {if (max < a[k]) max = a[k];}return max;}þ In a recursive version what is base case, what is measure ofproblem size that decreases (towards base case)?CompSci 100E12.12Recursive Maxdouble recMax(double[] a, int first)// pre: a contains a.length elements, 0 < a.length// first < a.length// post: return maximal element a[first..length-1]{if (first == a.length-1){ // last element, donereturn a[first];}double maxAfter = recMax(a, first+1);if (maxAfter < a[first]) return a[first];else return maxAfter;}ÿWhat is base case (conceptually)?ÿ We can use recMax to implement max as followsreturn recMax(a,0);CompSci 100E12.13Recognizing recursion:void change(int[] a, int first, int last)// post: a is changed{if (first < last){int temp = a[first]; // swap a[first], a[last]a[first] = a[last];a[last] = temp;change(a, first+1,
View Full Document
Unlocking...