Recursion Principles in Programming

Delve into the vital principles of recursion in programming. Explore how to approach tasks, define base and recursive cases, and make progress towards terminating functions effectively. Uncover examples and guidelines for mastering recursion techniques in coding.

• Recursion
• Programming
• Functions
• Principles
• Implementation

karimahho Follow

Uploaded on Mar 05, 2025 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Recursion Review Spring 2019 CS 1110

2. Before you Begin Plan out how you will approach the task before writing code Consider the following: How can you divide and conquer the task? Do you understand the spec? How would you describe the implementation of the function using words? Recursion Review 2

3. Steps to Recursion 1.Base case 2.Recursive case 3.Ensure the recursive case makes progress towards the base case Recursion Review 3

4. Base Case Create cases to handle smallest units of data Ideal base cases depend on what type of data is being handled and what the function must do on that data Recursion Review 4

5. Recursive Case Divide and conquer: how to divide the input so that we can call the function recursively on smaller input When calling the function recursively, assume that it works exactly as the specification states it does -- don t worry about the specifics of your implementation here Use this recursive call to handle the rest of the data, besides the small unit being handled Recursion Review 5

6. Make Progress Recursive calls must always make some sort of progress towards the base cases This is the only way to ensure the function terminates properly Risk having infinite recursion otherwise Recursion Review 6

7. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" Recursion Review 7

8. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 Recursion Review 8

9. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 #Divide and conquer #Divide the list into the first element s[0], and the rest s[1:] Recursion Review 9

10. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 #Divide and conquer #Divide the string into the first element s[0], and the rest s[1:] #s[0] -> check if it is a vowel #s[1:] -> recursive call that returns the number of vowels in the rest of the string #Finally, put it back together Recursion Review 10

11. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 #Recursive Case with divide and conquer #divide into s[0] and s[1:] if(s[0] in [ a , e , i , o , u ]): # `left` stores number vowels in s[0] left = 1 else: left = 0 Recursion Review 11

12. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 #Recursive Case with divide and conquer #divide into s[0] and s[1:] if(s[0] in [ a , e , i , o , u ]): # `left` stores number vowels in s[0] left = 1 else: left = 0 right = count_vowels(s[1:]) #`right` stores number vowels in s[1:] Recursion Review 12

13. Example def count_vowels(s): """Returns: The number of vowels (defined here as a , e , i , o , u ) in the string s. Precondition: s is a string""" if len(s) == 0: #Base case return 0 #Recursive Case with divide and conquer #divide into s[0] and s[1:] if(s[0] in [ a , e , i , o , u ]): # `left` stores number vowels in s[0] left = 1 else: left = 0 right = count_vowels(s[1:]) #`right` stores number vowels in s[1:] return left + right #Putting it back together Recursion Review 13

14. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. Precondition: s is a string""" 1 if len(s) == 0: 2 return 0 3 if(s[0] in [ a , e , i , o , u ]): 4 left = 1 5 else: 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 14

15. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7 count_vowels count_vowels s fo fo Precondition: s is a string""" 1 if len(s) == 0: 0 0 left 2 return 0 3 if(s[0] in [ a , e , i , o , u ]): 4 left = 1 5 else: 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 15

16. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7 count_vowels count_vowels s fo fo Precondition: s is a string""" 1 if len(s) == 0: 0 0 left 2 return 0 1, 3, 4, 7 count_vowels count_vowels 3 if(s[0] in [ a , e , i , o , u ]): s o o 4 left = 1 1 1 5 else: left 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 16

17. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7 count_vowels count_vowels s fo fo Precondition: s is a string""" 1 if len(s) == 0: 0 0 left 2 return 0 1, 3, 4, 7 count_vowels count_vowels 3 if(s[0] in [ a , e , i , o , u ]): s o o 4 left = 1 1 1 5 else: left 1,2 count_vowels count_vowels 6 left = 0 s 7 right = count_vowels(s[1:]) 8 return left + right 0 0 RETURN Call: count_vowels( efo ) Recursion Review 17

18. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7 count_vowels count_vowels s fo fo Precondition: s is a string""" 1 if len(s) == 0: 0 0 left 2 return 0 1, 3, 4, 7, 8 count_vowels count_vowels 3 if(s[0] in [ a , e , i , o , u ]): right s o o 0 0 4 left = 1 1 1 1 1 5 else: left RETURN 1,2 count_vowels count_vowels 6 left = 0 s 7 right = count_vowels(s[1:]) 8 return left + right 0 0 RETURN Call: count_vowels( efo ) Recursion Review 18

19. Visualization 1, 3, 4, 7 count_vowels count_vowels s efo efo 1 1 left def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7, 8 count_vowels count_vowels right s fo fo 1 1 Precondition: s is a string""" 1 if len(s) == 0: 1 1 0 0 left RETURN 2 return 0 1, 3, 4, 7, 8 count_vowels count_vowels 3 if(s[0] in [ a , e , i , o , u ]): right s o o 0 0 4 left = 1 1 1 1 1 5 else: left RETURN 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 19

20. Visualization 1, 3, 4, 7, 8 count_vowels count_vowels right s efo efo 1 1 2 2 1 1 left RETURN def count_vowels(s): """Returns: The number of vowels in the string s. 1, 3, 5, 6, 7, 8 count_vowels count_vowels right s fo fo 1 1 Precondition: s is a string""" 1 if len(s) == 0: 1 1 0 0 left RETURN 2 return 0 3 if(s[0] in [ a , e , i , o , u ]): 4 left = 1 5 else: 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 20

21. Visualization 1, 3, 4, 7, 8 count_vowels count_vowels right s efo efo 1 1 2 2 1 1 left RETURN def count_vowels(s): """Returns: The number of vowels in the string s. Precondition: s is a string""" 1 if len(s) == 0: 2 return 0 3 if(s[0] in [ a , e , i , o , u ]): 4 left = 1 5 else: 6 left = 0 7 right = count_vowels(s[1:]) 8 return left + right Call: count_vowels( efo ) Recursion Review 21

22. Practice Worksheet Pair up with a neighbor and work on the practice problems! Raise your hand if you have any questions. Recursion Review 22

23. Recursion with Objects class TreeNode (object): """ Attributes: value: An int, the value of this TreeNode object 341 left: A TreeNode object, or None right: A TreeNode object, or None """ 2 377 50 9 1110 Recursion Review 23

24. Understanding the Objects Structure id1 TreeNode 341 value id3 id2 TreeNode id2 left TreeNode id3 right 377 value 2 value id5 left id6 left id4 right None right id5 id4 id6 TreeNode TreeNode TreeNode 9 1110 value value 50 value None None left left None left None None right right None right Recursion Review 24

25. Recursion with Objects def contains (t, v): """ Returns: A boolean. Returns True if any of the TreeNode objects in the entire tree have a value equivalent to v. Let us define the tree as the TreeNode t, as well as the TreeNodes accessible through the left and right attributes of the node (if not None), as well as the TreeNodes accessible through the left and right attributes of those TreeNodes, etc. Precondition: t is a TreeNode, or None """ Recursion Review 25

26. Base Case Comparison Strings Lists Tree id6 1 Element [1] 1 TreeNode 1 value None left None right 0 Elements [] None Recursion Review 26

27. Recursion with Objects def contains (t, v): """ Returns: A boolean. Returns True if any of the TreeNode objects in the entire tree have a value equivalent to v. Let us define the tree as the TreeNode t, as well as the TreeNodes accessible through the left and right attributes of the node (if not None), as well as the TreeNodes accessible through the left and right attributes of those TreeNodes, etc. Precondition: t is a TreeNode, or None """ if t is None: #Case: None/non-existent Tree return False Recursion Review 27

28. Recursion with Objects def contains (t, v): """ Returns: A boolean. Returns True if any of the TreeNode objects in the entire tree have a value equivalent to v. Let us define the tree as the TreeNode t, as well as the TreeNodes accessible through the left and right attributes of the node (if not None), as well as the TreeNodes accessible through the left and right attributes of those TreeNodes, etc. Precondition: t is a TreeNode, or None """ if t is None: #Case: None/non-existent Tree return False elif t.value == v: #Case: Found value return True Recursion Review 28

29. Divide and Conquer on Trees Recall the tree structure... 341 They can be easily divided into left and right subtrees! 2 377 50 9 1110 Recursion Review 29

30. Divide and Conquer on Trees Recall the tree structure... 341 They can be easily divided into left and right subtrees! Right subtree Left subtree 2 377 50 9 1110 Recursion Review 30

31. Divide and Conquer on Trees Recall the tree structure... 341 They can be easily divided into left and right subtrees! Right subtree Left subtree 2 377 Recursion on left Recursion on right Put result back together 50 9 1110 Recursion Review 31

32. Recursion with Objects def contains (t, v): """ Returns: A boolean. Returns True if any of the TreeNode objects in the entire tree have a value equivalent to v. Let us define the tree as the TreeNode t, as well as the TreeNodes accessible through the left and right attributes of the node (if not None), as well as the TreeNodes accessible through the left and right attributes of those TreeNodes, etc. Precondition: t is a TreeNode, or None """ if t is None: #Case: None/non-existent Tree return False elif t.value == v: #Case: Found value return True return contains(t.left, v) or contains(t.right, v) branches #Recursively check Recursion Review 32

33. Recursion with Objects def contains (t, v): """ Returns: A boolean. Returns True if any of the TreeNode objects in the entire tree have a value equivalent to v. Let us define the tree as the TreeNode t, as well as the TreeNodes accessible through the left and right attributes of the node (if not None), as well as the TreeNodes accessible through the left and right attributes of those TreeNodes, etc. Precondition: t is a TreeNode, or None """ if t is None: #Case: None/non-existent Tree return False elif t.value == v: #Case: Found value return True return contains(t.left, v) or contains(t.right, v) branches #Recursively check Recursion Review 33

34. Practice Worksheet (contd.) Continue working on the problems! Raise your hand if you have any questions. Recursion Review 34

35. sumDigits def sumDigits(n): """Returns: Given a non-negative int n, return the sum of its digits recursively (no loops). For example sumDigits(126) 9 sumDigits(49) 13 sumDigits(12) 3 Hint: recall the mod operator % that gives you the remainder during division""" if n // 10 == 0: return n else: return n % 10 + sumDigits(n//10) Recursion Review 35

36. fib def fib(n): """Returns: the nth Fibonacci number. Fibonacci number sequence is a sequence that goes like 0 1 1 2 3 5 8 13 ... Precondition: n is an int. 0th element is 0.""" if n == 0: return 0 elif n == 1: return 1 return fib(n-1) + fib(n-2) Recursion Review 36

37. delimStr def delimStr(s, delim): """Returns: returns the given word s with str delim after each letter, e.g. delimStr( hello , "*") h*e*l*l*o* delimStr( hi , "_") h_i_ """ if len(s) == 0: return s else: return s[0] + delim + delimStr(s[1:], delim) Recursion Review 37

38. canSum def canSum(list, target): """Returns: True if you can sum elements of integer list <list> to target, e.g. canSum([2,4,5],7) -> True canSum([2,4,5],8) -> False canSum([],0) -> True """ if target == 0: return True if len(list) > 0: return canSum(list[1:],target-list[0]) or canSum(list[1:],target) else: return False #CHALLENGE QUESTION: This function is more difficult than what you would be expected to accomplish on a prelim; its main difficulty does not come from recursion, but from the algorithm to determine whether the elements are summable or not Recursion Review 38

39. count_ints def count_ints(lst): """Returns: The number of integers in a multi-dimensional list of integers, lst. For example, count_ints([1,[2,3,[4,5,6]],[7,8,[9,10]]]) would return 10. Precondition: lst is a list of ints """ count = 0 for item in lst: if type(item) == int: count += 1 else: count += count_ints(item) return count Recursion Review 39

40. count_ints alternative solution def count_ints(lst): """Returns: The number of integers in a multi-dimensional list of integers, lst. For example, count_ints([1,[2,3,[4,5,6]],[7,8,[9,10]]]) would return 10. Precondition: lst is a list of ints """ if lst == []: return 0 if type(lst[0]) == int: return 1 + count_ints(lst[1:]) else: return count_ints(lst[0]) + counts_int(lst[1:]) Recursion Review 40

41. merge def merge(list1, list2): """Returns: The result of merging two sorted lists of ints, list1 and list2, in order. For example, merge([1,2,2,5], [2,3,3,3,4,5,6]) should return [1,2,2,2,3,3,3,4,5,5,6] """ if list1 == []: return list2 elif list2 == []: return list1 else: if list1[0] <= list2[0]: return [list1[0]] + merge(list1[1:], list2) else: return [list2[0]] + merge(list1, list2[1:]) Recursion Review 41

42. max_ancestor def max_ancestor(p): """ Returns: How many generations old the family tree can be traced. If p has no parents, the function would return 1 because only 1 generation can be traced. Preconditions: p is a Person """ me Example: The family tree to the left can be traced up to 4 generations. That is, me -> dad -> grandpa1 -> great grandma dad mom grandpa1 grandpa2 On the mom's side, it could be traced up to 3 generations, but we are looking for the maximum tracing, which is 4 generations on dad's side. great grandma Recursion Review 42

43. max_ancestor def max_value(p): """ Returns: How many generations old the family tree can be traced. If p has no parents, the function would return 1 because only 1 generation can be traced. Preconditions: p is a Person """ if (p.dad is None) and (p.mom is None): return 1 elif not (p.dad is None) and (p.mom is None): return 1 + max_ancestor(p.dad) if (p.dad is None) and not (p.mom is None): return 1 + max_ancestor(p.mom) else: return max(1 + max_ancestor(p.dad), 1 + max_ancestor(p.mom)) Recursion Review 43

44. max_ancestor alternate def max_value(p): """ Returns: How many generations old the family tree can be traced. If p has no parents, the function would return 1 because only 1 generation can be traced. Preconditions: p is a Person """ d = 0 m = 0 if not (p.dad is None): d = max_ancestor(p.dad) if not (p.mom is None): m = max_ancestor(p.mom) return max(1 + d, 1 + m) Recursion Review 44

45. max_value def max_value(t): """Returns: Max value of all values stored in the tree reachable from TreeNode t Precondition: t is a TreeNode """ if (t.left is None) and (t.right is None): return t.value elif (not (t.left is None)) and (t.right is None): return max(t.value, max_value(t.left)) elif (t.left is None) and (not (t.right is None)): return max(t.value, max_value(t.right)) else: return max(t.value, max_value(t.left), max_value(t.right)) Recursion Review 45

46. tree_flip def tree_flip(t): """Swaps the right and left attributes of t, and recursively does the same to all subtrees Note the this is a procedural function and does not return anything Precondition: t is a TreeNode""" if (t.right != None): Example 2: Example 1: tree_flip(t.right) 1 1 if (t.left != None): 2 3 4 2 3 4 5 6 7 tree_flip(t.left) temp = t.right would become would become t.right = t.left t.left = temp 1 1 3 2 3 2 7 6 5 4 4 Recursion Review 46