Introduction to Programming in Python - Recursion PDF

Introduction to Programming in Python Recursion Walter Binder  Recursion Recursion Function call itself to solve a smaller problem instance Divide and conquer ○ Break problem into simpler part...

Introduction to Programming in Python Recursion Walter Binder  Recursion Recursion Function call itself to solve a smaller problem instance Divide and conquer ○ Break problem into simpler parts Real-life ○ Nested parallel → Russian smaller versionsdoll ○ Finite depth Main components ○ Base case: condition that stops recursion ○ Recursive case: function calling itself on a smaller problem 2  Factorial Factorial Denoted as n!, where n is a positive integer number Product of all positive integers ≤ n E.g., ○ 0! = 1 (there are no positive integers less than 1, so empty product is 1 ) ○ 1! = 1 ○ 2! = 2 × 1 = 2 ○ 3! = 3 × 2 × 1 = 6 3 ○ 4! = 4 × 3 × 2 × 1 = 24  Example: Recursive Factorial Example: Implement a recursive function that compute the factorial of a number 4  Programming is a Process Analysis (revisited) Problem analysis and specification Design Break down into simpler sub-problems and formulate algorithms Coding Implement solutions in code Testing Test code functionality Debugging Identify and fix bugs 5  Example: Recursive Factorial 1. Analysis Make sure you understand factorial mathematical definition ○ Factorial is only defined for non-negative integers Determine requirements: ○ What input data is required? - A positive whole number → an integer ○ What would the output be? - The factorial → an integer 6  Example: Recursive Factorial 2. Design What would be the name of the function? ○ factorial Which will be the parameters and return value, if any? ○ Sketch the docstring ''' Computes the factorial of a number (i.e., n!). Parameters: n (int): the number for which factorial is computed. Returns: (int): the factorial of the number. ''' 7  Example: Recursive Factorial 2. Design Which is the base case? ○ 0! = 1 ○ 1! = 1 Which is the recursive case? ○ 2! = 2 × 1 = 2 ○ 3! = 3 × 2 × 1 = 6 ○ 4! = 4 × 3 × 2 × 1 = 24 ○ 5! = 5 × 4 × 3 × 2 × 1 = 120 ○ n multiplied by the factorial of n − 1 8  Example: Recursive Factorial 3. Coding Define the function signature ○ def factorial(n): 9  Example: Recursive Factorial 3. Coding Implement the base case ○ if n == 0 or n == 1: ○ return 1 10  Example: Recursive Factorial 3. Coding Implement the recursive case (wrong approach): ○ elif n == 2: This approach will be ○ return 2 * 1 impractical for large ○ elif n == 3: numbers ○ return 3 * 2 * 1 ○ elif n == 4: Do you see a repetitive ○ return 4 * 3 * 2 * 1 Factorial of n − 1 pattern? ○ elif n == 5: ○ return 5 * 4 * 3 * 2 * 1 ○ # And so on... 11  Recursion Is it possible for a function to call itself? 12  Example: Recursive Factorial 3. Coding Implement the recursive case (wrong approach): This approach will be ○ elif n == 2: still impractical for ○ return 2 * factorial(2 - 1) large numbers ○ elif n == 3: ○ return 3 * factorial(3 - 1) Do you see a ○ elif n == 4: repetitive pattern? ○ return 4 * factorial(4 - 1) ○ elif n == 5: n multiplied by ○ return 5 * factorial(5 - 1) the factorial of n ○ # And so on… −1 13  Example: Recursive Factorial 3. Coding Implement the recursive case (correct approach): ○ else: ○ return n * factorial(n - 1) 14  Example: Recursive Factorial 3. Coding Let’s put everything together: ○ def factorial(n): ○ # Base case: ○ if n == 0 or n == 1: ○ return 1 ○ # Recursive case: ○ else: ○ return n * factorial(n - 1) What about polishing a bit the code? 15  Example: Recursive Factorial 3. Coding The same function a bit polished: ○ def factorial(n): ○ # Recursive case: ○ if n > 1: ○ return n * factorial(n - 1) ○ # Base case: ○ else: ○ return 1 16  Example: Recursive Factorial 4. Testing Let’s add doctests to the docstring: ''' Computes the factorial of a number (i.e., n!). Parameters: n (int): the number for which factorial is computed. Returns: (int): the factorial of the number. >>> factorial(0) 1 >>> factorial(1) 1 >>> factorial(5) 120 17 '''  Example: Recursive Factorial Trying: 4. Testing factorial(0) Let’s test the function using Expecting: 1 doctest: ok import doctest Trying: def factorial(n): factorial(1) ''' Expecting: Computes the factorial of a number (i.e., n!). 1 Parameters: ok n (int): the number for which factorial is computed. Trying: factorial(5) Returns: (int): the factorial of the number. Expecting: 120 >>> factorial(0) ok 1 1 items had no tests: >>> factorial(1) 1 __main__ >>> factorial(5) 1 items passed all tests: 120 3 tests in __main__.factorial ''' 3 tests in 2 items. if n > 1: return n * factorial(n - 1) 3 passed and 0 failed. 18 else: Test passed.  Exercise 14.1: Python Tutor Exercise: Use Python Tutor to visualize the execution of factorial(...) 19  Exercise 14.1: Python Tutor Exercise: Use Python Tutor to visualize the execution of factorial(...) def factorial(n): if n > 1: return n * factorial(n - 1) else: return 1 factorial(5) 20  Exercise 14.1: Python Tutor Exercise: Observe how Python keep track of recursive function calls 21  Fibonacci It’s time to create your own recursive function! 22  Exercise 14.2: Recursive Fibonacci Fibonacci Sequence where each number is the sum of the two preceding ones E.g., ○ F(0) = 0 ○ F(1) = 1 ○ F(2) = F(1) + F(0) = 1 + 0 = 1 ○ F(3) = F(2) + F(1) = 1 + 1 = 2 ○ F(4) = F(3) + F(2) = 2 + 1 = 3 23 Let’s implement it using recursion!  Extract and Count Let’s understand other recursive patterns! 34  Exercise 14.3: Counting Hashtags def count_hashtags(strings): ''' Recursively counts hashtags (i.e., starts with `#`) in a list of strings. Parameters: strings (list[str]): a list of strings to search for hashtags. Returns: (int): the number of strings in the list that are hashtags. ''' if not strings: return 0 if strings.startswith('#'): return 1 + count_hashtags(strings[1:]) else: return count_hashtags(strings[1:]) print(count_hashtags(['hello#', '#awesome', 'world', '#python'])) 35  Exercise 14.3: Counting Hashtags def count_hashtags(strings): (polished) ''' Recursively counts hashtags (i.e., starts with `#`) in a list of strings. Parameters: strings (list[str]): a list of strings to search for hashtags. Returns: (int): the number of strings in the list that are hashtags. ''' if not strings: return 0 fst_element_counter = 1 if strings.startswith('#') else 0 return fst_element_counter + count_hashtags(strings[1:]) print(count_hashtags(['hello#', '#awesome', 'world', '#python'])) 36  Exercise 14.3: Counting Hashtags def count_hashtags(strings): (polished) ''' Recursively counts hashtags (i.e., starts with `#`) in a list of strings. Parameters: strings (list[str]): a list of strings to search for hashtags. Returns: (int): the number of strings in the list that are hashtags. ''' if not strings: return 0 tail_counter = count_hashtags(strings[1:]) return 1 + tail_counter if strings.startswith('#') else tail_counter print(count_hashtags(['hello#', '#awesome', 'world', '#python'])) 37  Exercise 14.3: Counting Hashtags def count_hashtags(strings): (hack) ''' Recursively counts hashtags (i.e., starts with `#`) in a list of strings. Parameters: strings (list[str]): a list of strings to search for hashtags. Returns: (int): the number of strings in the list that are hashtags. ''' if not strings: return 0 return strings.startswith('#') + count_hashtags(strings[1:]) print(count_hashtags(['hello#', '#awesome', 'world', '#python'])) 38  Exercise 14.3: Counting Hashtags Exercise: Use a debugger (Thonny or Python Tutor) to inspect step-by-step execution Checklist: ▢ Understand the docstring ▢ Identify and understand the base case ⧠ How to check if a list is empty? And what to do in such a case? ▢ Identify and understand the recursive case ⧠ If the first item is a hashtag ○ How to count it (incrementing count by 1)? ○ How to process the remaining of the list (recursion and list slicing)? ⧠ If the first item is not a hashtag ○ How to exclude it (keeping count unchanged)? 39  Exercise 14.4: Extracting def extract_hashtags(strings): Hashtags ''' Recursively extracts hashtags (i.e., starts with `#`) from a list of strings. Parameters: strings (list[str]): a list of strings to search for hashtags. Returns: (list[str]): a list containing only the strings from the list that are hashtags. ''' if not strings: return [] tail_lists = extract_hashtags(strings[1:]) if strings.startswith('#'): return [strings] + tail_lists else: return tail_lists 40 print(extract_hashtags(['hello#', '#awesome', 'world', '#python']))  Exercise 14.4: Extracting Exercise: Hashtags Use a debugger (Thonny or Python Tutor) to inspect step-by-step execution Checklist: ▢ Understand the docstring ▢ Identify and understand the base case ⧠ How to check if a list is empty? And what to do in such a case? ▢ Identify and understand the recursive case ⧠ If the first item is a hashtag ○ How to include it in the resulting list (list concatenation)? ○ How to process the remaining of the list (recursion and list slicing)? ⧠ If the first item is not a hashtag ○ How to exclude it from the resulting list? 41  Exercise 14.5: Fibonacci Spiral Exercise: We will create a spiral visual representation of the Fibonacci sequence using tiles Download the code template (fibonacci_spiral.py) Simplified version of https://pytamaro.si.usi.ch/activities/luce/fibonacci/en/v2 42  Exercise 14.5: Fibonacci Spiral Tile: The spiral consist of square tiles Each tile has a circular sector forming a quarter circle and a line illusion Complete the TODOs in the tile(...) function Check your implementation by showing a sample tile: ○ show_graphic(tile(150, white, 5)) 43  Exercise 14.5: Fibonacci Spiral Tile orientation: Tiles rotate as they are added ○ No rotation (0°), 90°, 180°, 270°, then back to no rotation, and so on Read carefully the orient(...) function Make sure you understand how % is used to produce the different rotations Check the function by showing a sample rotated tile: ○ n = 0 # Change to get different rotations ○ show_graphic(orient(tile(150, white, 5), n)) 44  Exercise 14.5: Fibonacci Spiral Fibonacci spiral: Function fib_spiral(...) build the spiral using tiles Read carefully the fib_spiral(...) function ○ Understand the base case ○ Understand how the color of a tile is produced - Read the documentation of hsv_color(...) ○ Understand how the size of a new tile is computed Complete the TODOs in the fib_spiral(...) function Check your implementation by showing a sample spiral: ○ show_graphic(fib_spiral(0)) See next slides to check expected outputs for different depths 45  Exercise 14.5: Fibonacci Spiral 0 1 2 3 46 Exercise 14.5: Fibonacci Spiral 4 5 6 47 Exercise 14.5: Fibonacci Spiral 7 8 48 Exercise 14.5: Fibonacci Spiral 9 10 49  Best Practices about Recursion Infinite loops: Ensure proper base case for recursion to properly end Avoid deep recursion: Recursion depth is limited in Python ○ Going beyond may raise a RecursionError 50  Best Practices about Recursion Fibonacci Recursive implementation is inefficient for large numbers ○ Many computations will be repeated For large numbers, use techniques like memoization Lists Recursive implementations for extracting or counting specific items are inefficient for large lists 51 Recursion 52  Quiz 14 Ready to test your knowledge? 53