20060929recurse iter2

50 %
50 %
Information about 20060929recurse iter2
Education

Published on January 16, 2008

Author: Marianna

Source: authorstream.com

Recursion and Iteration, cont’d:  Recursion and Iteration, cont’d CS 311 Data Structures and Algorithms Lecture Slides Friday, September 29, 2006 Glenn G. Chappell Department of Computer Science University of Alaska Fairbanks CHAPPELLG@member.ams.org © 2006 Glenn G. Chappell Review: Recursion and Iteration — Fibonacci Numbers [1/2]:  Review: Recursion and Iteration — Fibonacci Numbers [1/2] The 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 as follows: We denote the nth Fibonacci number by Fn. F0 = 0. F1 = 1. For n ≥ 2, Fn = Fn–2 + Fn–1. As before, recurrence relations often translate nicely into recursive algorithms. How can we compute Fibonacci numbers using a recursive function? Write it! Done. See fibo1.cpp, on the web page. Another recurrence relation Review: Recursion and Iteration — Fibonacci Numbers [2/2]:  Review: Recursion and Iteration — Fibonacci Numbers [2/2] For high-ish values of n (above 30, say) function fibo is extremely slow. What can we do about this? To Do Rewrite the Fibonacci computation in a fast iterative (looping) form. Done. See fibo2.cpp, on the web page. Can similar benefits be realized by a recursive function? If so, write one. Done. See fibo3.cpp, on the web page. Recursion and Iteration, cont’d: Fibonacci Numbers — Lessons:  Recursion and Iteration, cont’d: Fibonacci Numbers — Lessons Choosing the right algorithm can make a huge difference in performance. As we will see, data structures can make a similar difference. Some algorithms have natural implementations in both recursive and 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. Recursion and Iteration, cont’d: Drawbacks of Recursion:  Recursion and Iteration, cont’d: Drawbacks of Recursion Regardless of the algorithm used, recursion has two important drawbacks: Function-Call Overhead Making a function call requires a significant amount of work: saving and retrieving the return address, initializing and destroying automatic variables. Iteration avoids having to do this. Memory-Management Issues Memory for automatic variables is allocated in a way that does not allow for normal error handling. Making too many recursive calls will probably crash the program. When we use iteration, we can manage memory ourselves. This is more work, but it also allows us to handle errors properly. Recursion and Iteration, cont’d: Caching/Memoization [1/3]:  Recursion and Iteration, cont’d: Caching/Memoization [1/3] Our original recursive function for computing Fibonacci numbers was very inefficient. At right we show how it would compute F6. One way to look at the problem is that not enough information is “passed up”. We wrote a more efficient version that computed and returned 2 consecutive Fibonacci numbers. At right we show how it would handle the same task. F5 F3 F4 F1 F2 F0 F1 F2 F0 F1 F3 F1 F2 F0 F1 F4 F2 F0 F1 F3 F1 F2 F0 F1 F6 F5 & F6 F6 F4 & F5 F3 & F4 F2 & F3 F1 & F2 F0 & F1 F-1 & F0 Recursion and Iteration, cont’d: Caching/Memoization [2/3]:  Recursion and Iteration, cont’d: Caching/Memoization [2/3] There is another way to look at the problem: redundancy. We compute things we have already computed before. F0 is computed 5 times, F1 is computed 8 times, F2 is computed 5 times, F3 is computed 3 times, and F4 is computed 2 times. Solution: When we compute a value, we save it. The next time we need it, we can look it up. This is a form of caching, often called memoization. At right is an illustration of how a memoizing recursive function would compute F6. Bold squares are already computed. Re-running the algorithm for these duplicates effort. F5 F1 F2 F0 F1 F2 F0 F1 F3 F1 F2 F0 F1 F4 F2 F0 F1 F3 F1 F0 F1 F6 F3 F4 F2 F5 F4 F2 F0 F1 F3 F6 F3 F4 F1 F2 Already computed. Do look-up. Recursion and Iteration, cont’d: Caching/Memoization [3/3]:  Recursion and Iteration, cont’d: Caching/Memoization [3/3] To Do Write a memoizing recursive function to compute a Fibonacci number. Done. See fibo4.cpp, on the web page. Notes Contrast the memoizing and return-two versions of function fibo in terms of: The number of function calls. The recursion depth. Memoization and other forms of caching have little to do with recursion; they can be used in non-recursive contexts. These techniques are useful when: Values are time-consuming to compute (or retrieve). Values will likely be required several times. Calling a function with the same parameters always produces the same result. Recursion and Iteration, cont’d: Even Faster fibo [1/2]:  Recursion and Iteration, cont’d: Even Faster fibo [1/2] By the way, there is a simple formula for Fn. It requires floating-point computations. Let . This often called the “golden ratio”. Then, for each nonnegative integer n, Fn is the nearest integer to . Recursion and Iteration, cont’d: Even Faster fibo [2/2]:  Recursion and Iteration, cont’d: Even Faster fibo [2/2] We can implement function fibo using this formula: int fibo(int n) { const double sqrt5 = std::sqrt(5); const double phi = (1. + sqrt5) / 2.; // "Golden ratio" double nearly = std::pow(phi, n) / sqrt5; // phi^n/sqrt(5) // Our Fibonacci number is the nearest integer return int(nearly + 0.5); } See fibo5.cpp, on the web page. Recursion and Iteration, cont’d: Eliminating Recursion — General [1/2]:  Recursion and Iteration, cont’d: Eliminating Recursion — General [1/2] 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: Variable values. Some indication of where we have been in the function. Recursion and Iteration, cont’d: Eliminating Recursion — General [2/2]:  Recursion and Iteration, cont’d: Eliminating Recursion — General [2/2] To rewrite any recursive function in iterative form: Declare an appropriate stack. Put a big loop around the function body. Probably “while (true) { … }”. Replace each recursive call with: Push variable values and current execution location on the stack. Set up the parameters with the appropriate values. Go to the beginning of the loop (probably “continue”). Replace each “return” with: If the stack is empty, really return. Otherwise, pop, set the variables to their old values, and restart the loop, skipping to the appropriate place in the code. This can be done using lots of if’s or, if you must, a goto <shudder>. This method is primarily of theoretical interest. In practice, when we eliminate recursion, we usually give the matter some thought, rather than using this “brute-force” method. We will look at this further when we study Stacks. “Brute-force” method Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [1/4]:  Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [1/4] A special kind of recursion is tail recursion. Tail recursion is when a recursive call is the last thing a function does. Tail recursion is important because it makes the recursion → iteration conversion very easy. That is, we like tail recursion because it is easy to eliminate. In fact, tail recursion is such an obvious thing to optimize that some compilers automatically convert it to iteration. Note: I am speaking generally here, not specific to C++. Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [2/4]:  Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [2/4] For a void function, tail recursion looks like this: void foo(TTT a, UUU b) { … foo(x, y); } For a function returning a value, tail recursion looks like this: SSS bar(TTT a, UUU b) { … return bar(x, y); } Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [3/4]:  Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [3/4] The reason tail recursion is so easy to eliminate is that we never need to return from the recursive call to the calling function. Because there is nothing more for the calling function to do. Thus, we can replace the recursive call by something essentially like a goto. Eliminating Tail Recursion Surround the function body with a big loop, as before. Replace the tail recursive call with: Set parameters to their new values and restart the loop. There is no need to make any changes to non-recursive return statements, that is, the base case(s). If the only recursive call in a function is at the end, then eliminating tail recursion converts the function into non-recursive form. Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [4/4]:  Recursion and Iteration, cont’d: Eliminating Recursion — Tail Recursion [4/4] Let’s eliminate the recursion in binsearch2.cpp. First, modify function binSearch so that it has exactly one recursive call, and this is at the end of the function. This should be easy. Done. See binsearch3.cpp, on the web page. Next, eliminate tail recursion. This might be a little trickier, but not too hard. Done. See binsearch4.cpp, on the web page.

Add a comment

Related presentations