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 better programs: easier to modify, extend, verify (and sometimes more efficient!!) Sometimes recursion isn’t appropriate, when it’s bad it can be very bad---every tool requires knowledge and experience in how to use itÿ The basic idea is to get help solving a problem from coworkers (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 in reverse 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 only after 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 (or does it?) What’s the easiest value of n to compute xn? If you want to multiply only once, what can you ask a clone?/** @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 to 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 or other 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 sixth Fibonacci number, we must compute F(5) and F(4). What do we do to compute F(5)? Why is this a problem? Towers of Hanoio N disks on one of three pegs, transfer all disks to another peg, never put a disk on a smaller one, only on largero Every solution takes “forever” when N, number of disks, is largeCompSci 100E12.7Fibonacci: Don’t do this recursively/** @param n >= 0* @return n-th Fibonacci* number*/long recFib(int n){if (0 == n || 1 == n) {return 1;}else {return recFib(n-1) +recFib(n-2);}}ÿ How many clones/calls to compute 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 be in the far eastÿ Move n disks from one peg to another with restrictive rules/** disks moved from peg 'from‘* to peg 'to' using peg 'aux'* @param numDisks on peg # from* @param from source peg #* @parm to target peg #* @param aux peg # for parking */void move(int from, int to, int aux,int numDisks) {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 about efficiency unless you know you have toÿ In some examples, like Fibonacci numbers, recursive solution does extra work, we’d like to avoid the extra work Iterative solution is efficient The recursive inefficiency of “extra work” can be fixed if we remember intermediate solutions: instance variablesÿ Instance variable: maintains value over all function calls Local variables created each time function calledCompSci 100E12.10Fixing recursive Fibonacci/** @param n >= 0 and n <= 30* @return the n-th Fibonacci number */long recFib(int n) {long[] mem = new long[31];Arrays.fill(mem, 0);return recF (n, mem);}long recF(int n, long[] mem){if (0 == n || 1 == n) return 1;else if (mem[n] != 0) return mem[n];else {mem[n] = recF(n-1, mem) + recF(n-2, mem);return mem[n];}}ÿWhat does mem do? Why initialize to all zeros? Note the use of a wrapper method to allow the use of mem The recursive method has mem as an added parameterCompSci 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 0thelement/**@paramacontainsa.lengthelements,0<a.length* @return maximal element of a*/double max(double[] 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 of problem size that decreases (towards base case)?CompSci 100E12.12Recursive Max/**@paramacontainsa.lengthelements,0<a.length* @param first < a.length is index to start* @return maximal element of a[first..length-1]*/double recMax(double[] a, int first) {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:/** a is changed */void change(int[] a, int first, int last){if
View Full Document
Unlocking...