Recursion vs. IterationEliminating RecursionCS 311 Data Structures and AlgorithmsLecture SlidesWednesday, September 30, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappellcontinued30 Sep 2009 CS 311 Fall 2009 2Unit OverviewRecursion & SearchingMajor Topics Introduction to Recursion Search Algorithms Recursion vs. Iteration Eliminating Recursion Recursive Search with Backtracking(part) 30 Sep 2009 CS 311 Fall 2009 3ReviewSearch Algorithms [1/3]Binary Search is an algorithm to find a given key in a sorted list. Here, key = thing to search for. Often there is associated data.  In computing, sorted = in (some) order.Procedure Pick an item in the middle: the pivot. Use this to narrow search to top or bottom half of list. Recurse.Example: Binary Search for 64 in the following list.5 8 9 13 22 30 34 37 41 60 63 65 82 87 90 911. Looking for 64 in this list.2. Pivot. Is 64 < 38? No.383. Recurse: Looking for 64 in this list.30 Sep 2009 CS 311 Fall 2009 4ReviewSearch Algorithms [2/3]Binary Search is much faster than Sequential Search, and so the amount of data it can process in the same amount of time is much greater.“The fundamental law of computer science: As machines become more powerful, the efficiency of algorithms grows more important, not less.”— Nick Trefethen40549,755,813,88840kRoughly 2kk20524,288201051210484343222111Maximum AllowableList Size:Sequential SearchMaximum AllowableList Size:Binary SearchNumber of Look-UpsWe Have Time toPerform30 Sep 2009 CS 311 Fall 2009 5ReviewSearch Algorithms [3/3]Equality vs. Equivalence “a == b” is equality. “!(a < b) && !(b < a)” is equivalence.Equality & equivalence may not be the same thing when objects being compared are not numbers.Using equivalence instead of equality: Maintains consistency with operator<. Allows for use with objects that do not have operator==.Iterator operations that can be done in more than one way.std::distance(iter1, iter2)iter2 – iter1std::advance(iter, n)iter += nUsing STL AlgorithmsWorks with all forward iteratorsStill fast with random-accessUsing OperatorsRandom-access iterators only30 Sep 2009 CS 311 Fall 2009 6ReviewRecursion vs. IterationThe Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, … To get the next Fibonacci number, add the two before it.They are defined formally as follows: We denote the nth Fibonacci number by Fn(n = 0, 1, 2, …). F0= 0. F1= 1. For n ≥ 2, Fn= Fn–2+ Fn–1.As before, recurrence relations often translate nicely into recursive algorithms.TO DO Write a recursive function to compute a Fibonacci number: given n, compute Fn.Another recurrence relationDone. See fibo1.cpp, on the web page.30 Sep 2009 CS 311 Fall 2009 7Recursion vs. IterationFibonacci Numbers — ProblemFor high-ish values of n (above 40, say) function fibo in fibo1.cpp is extremely slow. What can we do about this?TO DO Rewrite the Fibonacci computationin a fast iterative form.TO DO Figure out how to do a fast recursiveversion. Write it.continuedWow!Recursion is a lot slower than iteration!Wrong! Wrong, wrong, wrong, wrong, wrong, wrong.You’re wrong.Done. See fibo2.cpp, on the web page.Done. See fibo3.cpp, on the web page.30 Sep 2009 CS 311 Fall 2009 8Recursion vs. IterationFibonacci Numbers — Lessons [1/2]Choice of algorithm can make a huge difference in performance.As we will see, data structures can make a similar difference.F5F3F4F1F2F0F1F2F0F1F3F1F2F0F1F4F2F0F1F3F1F2F0F1F6F5& F6F6F4& F5F3& F4F2& F3F1& F2F0& F1F-1& F0In fibo1.cpp In fibo3.cppRecursive calls made to compute F6.30 Sep 2009 CS 311 Fall 2009 9Recursion vs. IterationFibonacci Numbers — Lessons [2/2]Some algorithms have natural implementations in both recursiveand iterative form. Iterative means making use of loops.A struct can be used to return two values at once. The template std::pair (declared in <utility>) can be helpful.Sometimes we have a workhorse function that does most of the processing and a wrapper function that is set up for convenient use. Often the wrapper just calls the workhorse for us. This is common when we use recursion, since recursion can place inconvenient restrictions on how a function is called. We have seen this in another context. Remember toString and operator<< in the package from Assignment #1.30 Sep 2009 CS 311 Fall 2009 10Recursion vs. IterationDrawbacks of RecursionTwo factors can make recursive algorithms inefficient. Inherent inefficiency of some recursive algorithms However, there are efficient recursive algorithms (fibo3.cpp). Function-call overhead Making all those function calls requires work: saving return addresses, creating and destroying automatic variables.And recursion has another problem. Memory-management issues Memory for automatic variables is allocated ina way that does not allow for normal errorhandling. Making too many recursive calls willcause stack overflow (resulting in a crash — or worse). When we use iteration, we can manage memory ourselves. This is more work, but it also allows us to handle errors properly.These two are important regardless of the recursive algorithm used.30 Sep 2009 CS 311 Fall 2009 11Recursion vs. IterationNote — Even Faster fiboThere is actually a simple formula for Fn(we must use floating-point).Let . This is called the “golden ratio”.Then for each nonnegative integer n, Fnis the nearest integer to .Here is fibo using this formula:int fibo(int n){const double sqrt5 = sqrt(5.);const double phi = (1. + sqrt5) / 2.; // "Golden ratio"double nearly = pow(phi, n) / sqrt5; // phi^n/sqrt(5)// Our Fibonacci number is the nearest integerreturn int(nearly + 0.5);}6180339887.1251≈+=ϕ5nϕSee fibo5.cpp, on the web page.30 Sep 2009 CS 311 Fall 2009 12Eliminating RecursionIn General [1/2]Fact. Every recursive function can be rewritten as an iterative function that uses essentially the same algorithm. Think: How does the system help you do recursion? It provides a Stack, used to hold return addresses for function calls, and values of automatic local variables. We can implement such a Stack ourselves. We need to be able to store: Values of automatic local variables, including parameters. The return value (if any). Some indication of where we have been in the function. Thus, we can eliminate