Recursion (CMSC 201) PDF

CMSC 201 Eric Hamilton Recursion Eric Hamilton  What We Know Lists Conditional expressions ○ if, elif, else and how they branch. Iteration ○ For Loops ○ While Loops ○ Python’s built-in it...

CMSC 201 Eric Hamilton Recursion Eric Hamilton  What We Know Lists Conditional expressions ○ if, elif, else and how they branch. Iteration ○ For Loops ○ While Loops ○ Python’s built-in iteration through lists. Functions ○ Declaring functions ○ Calling functions ○ Returning values. *Not the Tower of Hanoi Problem, but a Tower in Hanoi  What is Basic Examples Recursion? What is under the turtle? ○ And it’s turtles all the way down. What is GNU? ○ GNU is Not Unix A python example: ○ PIP = PIP Installs Packages Applied Examples Inductive proofs and processes in math. Recursion theory in the theory Recursion is the idea of of logical quantifiers and in self reference. linguistics (cf. Noam Chomsky)  Recursion in Programming A Recursive Process is a process which calls itself during its execution. The main idea is to break each problem into one or more subproblems of smaller “complexity” and to solve them. Also an easy way to handle algorithms which branch. Here is a recursive function call, to perhaps the most pointless function ever: Trace-through of the Trivial Function  The Canonical Example - Factorial How do we go from this mathematical definition to an algorithm? Does this algorithm work? How do we know it terminates? What kind of things can break this? Trace-Through of the Factorial Recursion  Terminology The Recursive Case - The part of the function which subdivides the problem and makes one or more recursive calls to itself. The Base Case - Terminating Condition is the way to stop the recursion. If we don’t have something that kills the recursion, we will descend forever. This is similar to an infinite while loop whose condition is never false.  Example - Fibonacci Numbers Let’s imagine that we have one breeding pair of rabbits. They obey the following rules: 1. Each pair of rabbits takes one month to mature to breeding age. 2. Each pair of rabbits will give birth to a new pair every month, once mature. 3. Rabbits are immortal. Here is the mathematical definition: Fibonacci Continued - Recursive Solution In this case we need to branch by calling the recursive function more than once per step. With a pseudo-code model, it should be easy to translate it into python. Palindromes - A Less Mathy Example Let’s think of a way to test recursively if a string is a palindrome. How do we ignore commas, spaces, and capitalization?  Using Helper Functions It can be useful to use a helper function before calling the recursive algorithm. In this case is_palindrome is not itself recursive. The recursive function is a function that will not be called directly, but does the majority of the work.  Binary Search This is really the first application where using recursion is superior in terms of efficiency. Binary Search Example Non-Mario Edition  Binary Search Implemented Let’s say you have a list, and I ask you if an element is in a sorted list, with the return True or False. How can decrease the number of elements we have to search? Why does this perform Note: We used the python notation to slice to the end of a list. We could have also said so much better than a L[half_length: len(L)]. linear search?  Binary Search Comparison Performed over 100 searches in a randomly generated list of size 877,350. Search Type Search Time Step Count Linear 20.375 sec 84,598,679 Binary 0.007 sec 2469  Sierpinski's Triangle Let’s draw this thing, with it is defined recursively by the following rules: Rule 1: For any triangle, divide at the midpoints of each line and create a sub-triangle, and then erase that triangle, then apply Rule 2. Rule 2: For any remaining triangle (the three remaining) apply Rule 1. Rule 3: Start by drawing and filling in a triangle and applying Rule 1.  Pre-Implementation of Sierpinski’s Triangles 1. How do we terminate this recursion? We are going to use distance between points to terminate, if the triangle side is smaller than that distance. 2. What helper functions should we implement before we start? Draw_triangle, is_close, and midpoint. What arguments do these take, and what should they each return? Helper Functions for Sierpinski’s Triangle Don’t look at draw_triangle, take it as a black box which simply takes the window and three points and draws the correct triangle (or fills it in). Don’t forget to import graphics at the top of your code. Implementation of Sierpinski's Triangle And here it is. The mathematics may be a little complex, but thankfully the algorithm to draw it is rather simple once we have a good handle on how to subdivide the problem.  Computing Need more proof? Square Roots This sequence’s limit is the square root of A.  Implementing the √A Recursively 1. How do we figure out the base case? 2. What parameters does the function need? 3. We need three variables, the variable A where we are trying to compute the square root, the current approximation x, and the error bound.  The Square Root Coded Which is better? How do we determine which algorithm is a better one? ○ Iterative versus Recursive What does error = 0.01 mean? Are there any concerns about this function? Does it always converge to the same values depending on initial x given?