Chapter 11 Recursion PDF

Chapter 11 RECURSION 3/22/20 1 Chapter Goals To learn to “think recursively” recursive helper functions To be able to use To understand the relationship between recursion and iteration To understand when the use of recursion affects the efficiency of an algori...

Chapter 11 RECURSION 3/22/20 1 Chapter Goals To learn to “think recursively” recursive helper functions To be able to use To understand the relationship between recursion and iteration To understand when the use of recursion affects the efficiency of an algorithm To analyze problems that are much easier to solve by recursion than by iteration 3/22/20 Page 2 Contents Solving problems defined recursively Recursive Solution to general problems Problem Solving: Thinking Recursively Recursive Helper Functions 3/22/20 Page 3 Recursive Functions A recursive function is a function that calls itself A recursive computation solves a problem by using the solution of the same problem with simpler inputs For a recursion to terminate, there must be special cases for the simplest inputs 3/22/20 Page 4 Recursive Definitions Defining a problem in terms of a smaller version of itself Every recursive definition must have one (or more) base cases The general case must eventually reduce to a base case The base case stops the recursion 5 Factorial Example 0! = 1 (1) base case n! = n x (n-1)! if n > 0 (2) general case def fact(n) : if n == 0 : return 1 return (n* fact(n-1)) 3/22/20 Page 6  Tracing Execution of fact() Function 3/22/20 Page 7  Fibonacci Example Fibonacci sequence: Sequence of numbers defined by f1 = 1 f2 = 1 fn = fn-1 + fn-2 First ten terms: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 3/22/20 Page 8  Fibonacci Example Fibonacci sequence: Sequence of numbers defined by f1 = 1 f2 = 1 fn = fn-1 + fn-2 First ten terms: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 3/22/20 Page 9 Tracing fib() 3/22/20 Page 10 Recursive triangle Example def printTriangle(sideLength) : if sideLength < 1 : return printTriangle(sideLength - 1) print("[]" * sideLength) The function will call itself (and not output anything) until sideLength becomes < 1 It will then use the return statement and each of the previous iterations will print their results 1, 2, 3 then 4 3/22/20 Page 11 Recursive Calls and Returns 3/22/20 Page 12  Triangle Numbers Revisited Triangle shape of side length 4: [] [][] [][][] [][][][] Will use recursion to compute the area of a triangle of width n , assuming each [] square has an area of 1 3/22/20 Page 13 Handling Triangle of Width 1 The triangle consists of a single square Its area is 1 Take care of this case first: def triangleArea(sideLength) : if sideLength == 1 : return 1... 3/22/20 Page 14 Handling The General Case Assume we know the area of the smaller, colored triangle: [] [][] [][][] [][][][] Area of larger triangle can be calculated as area = smallerArea + sideLength To get the area of the smaller triangle Call the triangleArea() function: smallerSideLength = sideLength - 1 smallerArea = triangleArea(smallerSideLength) 3/22/20 Page 15 Computing the Area of a Triangle, width 4 triangleArea() function makes a smaller triangle of width 3 It calls triangleArea() on that triangle That function makes a smaller triangle of width 2 It calls triangleArea() on that triangle That function makes a smaller triangle of width 1 It calls triangleArea()on that triangle That function returns 1 The function returns smallerArea + sideLength = 1 + 2 = 3 The function returns smallerArea + sideLength = 3 + 3 = 6 The function returns smallerArea + sideLength = 6 + 4 = 10 3/22/20 Page 16 Recursive Computation A recursive computation solves a problem by using the solution to the same problem with simpler inputs Call pattern of a recursive function is complicated Key: Don’t think about it 3/22/20 Page 17 Successful Recursion Every recursive call must simplify the computation in some way There must be special cases to handle the simplest computations directly 3/22/20 Page 18 Other Ways to Compute Triangle Numbers The area of a triangle equals the sum: 1 + 2 + 3 +... + sideLength Using a simple loop: area = 0; for i in range (1, (sideLength+1), 1) : area = area + i Using math: 1 + 2 +... + n = n × (n + 1)/2 => n * (n + 1) / 2 3/22/20 Page 19 Trianglenumbers.py 3/22/20 Page 20 Common Error Infinite recursion: A function calling itself over and over with no end in sight. The computer needs some amount of memory for bookkeeping during each call. After some number of calls, all memory that is available for this purpose is exhausted. Your program shuts down and reports a “stack overflow”. Causes: The arguments don’t get simpler or because a special terminating case is missing. 3/22/20 Page 21 Largest Element in a List 3/22/20 Page 22 Thinking Recursively Problem: Test whether a sentence is a palindrome Palindrome: A string that is equal to itself when you reverse all characters: A man, a plan, a canal – Panama! Go hang a salami, I’m a lasagna hog Madam, I’m Adam 3/22/20 Page 23 Implement IsPalindrome() Function ## Tests whether a string is a palindrome. # @param text a string that is being checked # @return True if text is a palindrome, False otherwise # def isPalindrome(text) :... 3/22/20 Page 24 Thinking Recursively: Step 1 Consider various ways to simplify inputs. Several possibilities: Remove the first character Remove the last character Remove both the first and last characters Remove a character from the middle Cut the string into two halves 3/22/20 Page 25  Thinking Recursively: Step 2 (1) Combine solutions with simpler inputs into a solution of the original problem. Most promising simplification: Remove both first and last characters. “adam, I’m Ada” is a palindrome too! Thus, a word is a palindrome if The first and last letters match, and Word obtained by removing the first and last letters is a palindrome 3/22/20 Page 26  Thinking Recursively: Step 2 (2) What if first or last character is not a letter? Ignore it If the first and last characters are letters, check whether they match; if so, remove both and test shorter string If last character isn’t a letter, remove it and test shorter string If first character isn’t a letter, remove it and test shorter string 3/22/20 Page 27  Thinking Recursively: Step 3 Find solutions to the simplest inputs. - Strings with two characters No special case required; step two still applies - Strings with a single character They are palindromes The empty string It is a palindrome 3/22/20 Page 28  Thinking Recursively: Step 4 (1) Implement the solution by combining the simple cases and the reduction step. def isPalindrome(text) : length = len(text) # Separate case for shortest strings. if length = end : return True else : # Get first and last characters, converted to lowercase. first = text[start].lower() last = text[end].lower() Continued 3/22/20 Page 34 Recursive Helper function if first.isalpha() and last.isalpha() : if first == last : # Test substring that doesn’t contain the matching # letters. return substringIsPalindrome (text, start + 1, end - 1) else : return False elif not last.isalpha() : # Test substring that doesn’t contain the last character. return substringIsPalindrome(text, start, end - 1) else : # Test substring that doesn’t contain the first # character. return substringIsPalindrome(text, start + 1, end) 3/22/20 Page 35 Summary: A recursive computation solves a problem by using the solution of the same problem with simpler inputs For recursion to terminate, there must be special cases for the simplest inputs The key to finding a recursive solution is reducing the input to a simpler input for the same problem When designing a recursive solution, do not worry about multiple nested calls Simply focus on reducing a problem to a slightly simpler one 3/22/20 Page 36 Summary Identify recursive helper functions for solving a problem. Sometimes it is easier to find a recursive solution if you make a slight change to the original problem. Review a complex recursion example that cannot be solved with a simple loop. The permutations of a string can be obtained more naturally through recursion than with a loop. 3/22/20 Page 37