Solving Problems RecursivelyFundamentals of RecursionRecursive exampleSlide 4Classic examples of recursionTowers of HanoiFibonacci: Don’t do this recursivelyPrint words entered, but backwardsExponentiationFaster exponentiationRecursive and Iterative log powersWhat’s better: recursion/iteration?Fixing recursive Fibonacci: recfib2.cppThinking recursivelyRecursive MaxRecognizing recursion:More recursion recognitionOne more recognitionNon-recursive versionBlob Counting: Recursion at WorkCounting blobs, the first slideIdentifying Larger BlobsIdentifying smaller blobsIssues that arise in studying codeRecursive helper functionsConceptual Details of BlobFillA Computer Science Tapestry10.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!! See expotest.cpp)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 resultA Computer Science Tapestry10.2Fundamentals of RecursionBase case (aka exit case)Simple case that can be solved with no further computationDoes not make a recursive callReduction step (aka Inductive hypothesis)Reduce the problem to another smaller one of the same structureMake a recursive call, with some parameter or other measure that decreases or moves towards the base case•Ensure that sequence of calls eventually reaches the base case•“Measure” can be tricky, but usually it’s straightforwardThe Leap of Faith!If it works for the reduction step is correct and there is proper handling of the base case, the recursion is correct.What row are you in?A Computer Science Tapestry10.3Recursive examplevoid WriteBinary(int n)// Writes the binary representation // of n to cout.{ if (n < 0) { cout << "-"; WriteBinary(-n); } else if (n < 2) cout << n; else { WriteBinary(n/2); cout << n % 2; } } n:A Computer Science Tapestry10.4Recursive examplevoid mystery(int n){ if (n <= 1) cout << n; else { mystery(n/2); cout << “, ” << n; }}n:A Computer Science Tapestry10.5Classic examples of recursionFor some reason, computer science uses these examples:Factorial: we can use a loop or recursion (see facttest.cpp), is this an issue?Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, …•F(n) = F(n-1) + F(n-2), why isn’t this enough? What’s needed?•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 Hanoi•N disks on one of three pegs, transfer all disks to another peg, never put a disk on a smaller one, only on larger•Every solution takes “forever” when N, number of disks, is largeA Computer Science Tapestry10.6Towers of HanoiThe origins of the problem/puzzle may be in the far eastMove n disks from one peg to another 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) { cout << "move " << from << " to " << to << endl; } else { Move (from,aux,to, numDisks - 1); Move (from,to,aux, 1); Move (aux,to,from, numDisks - 1); }}Peg#1 #2 #3A Computer Science Tapestry10.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 to compute F(5)?543 232021110101How many calls of F(1)?How many total calls?See recfib2.cpp for caching codeA Computer Science Tapestry10.8Print 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(){ string word; if (cin >> word) // reading succeeded? { PrintReversed(); // print the rest reversed cout << word << endl; // then print the word }}int 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 variableA Computer Science Tapestry10.9ExponentiationComputing xn means 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?double Power(double x, int n)// post: returns x^n{ if (n == 0) { return 1.0; } return x * Power(x, n-1);}What about an iterative version?A Computer Science Tapestry10.10Faster exponentiationHow many recursive calls are made to computer 21024?How many multiplies on each call? Is this better? double Power(double x, int n)// post: returns x^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?A Computer Science Tapestry10.11Recursive and Iterative log powersIn the program expotest.cpp we calculate xn using log(n) multiplications (basically). We do this both iteratively and recursively using BigInt variablesWe saw the iterative code in Chapter 5 with doubles BigInt has overloaded operators so these values work like ints and doublesWe use the CTimer class to time the difference in using these functions (ctimer.h)The recursive version is faster, sometimes much fasterUsing doubles we wouldn’t notice a differenceArtifact of algorithm? Can we “fix the problem”?Natural version of both in programs, optimizing tough.A Computer Science Tapestry10.12What’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