06 Recursive Functions and Divide-and-Conquer.pptx

Recursive Functions and Divide- and-Conquer Recursive Functions Recursive Functions: Definition and Components Definition of Recursive Components of Recursive Function Function A function that calls itself Base Case Similar to...

Recursive Functions and Divide- and-Conquer Recursive Functions Recursive Functions: Definition and Components Definition of Recursive Components of Recursive Function Function A function that calls itself Base Case Similar to loops in functionality Smallest input with an easily Preferable in some cases over loops verifiable solution Stops the function from calling itself indefinitely Recursive Step All cases where a recursive call is made Factorial Example Factorial of an integer n is the Definition of product of all positive integers up to Factorial n Recursive Base case: f(1) = 1 Definition Recursive step: f(n) = n × f(n-1) Factorial of 5: 5 × 4 × 3 × 2 × 1 = Example 120 Fibonacci Numbers Origin of Fibonacci Numbers ◦ Initially developed to model rabbit population growth Significance in Nature ◦ Found in various naturally occurring phenomena Recursive Formula ◦ Generated using a specific recursive formula ◦ Contains two recursive calls ◦ Includes two base cases Comparison of Iterative and Recursive Methods Iterative Recursive Consideration Functions Generally faster than Functions Useful for problems with s Ensure recursive calls recursive functions naturally recursive reach the base case to Preferred when convenient structure avoid infinite recursion for better performance More compact code In Python, large outputs compared to iterative can cause 'maximum functions recursion depth exceeded' Added running time as a error trade-off for compactness Divide-and- Conquer Techniques Divide-and-Conquer Divide-and-Conquer Classical Examples Strategy Tower of Hanoi Problem Useful for solving difficult Quicksort Algorithm problems Breaks problems into manageable parts Tower of Hanoi Three vertical rods and N disks ◦ Disks have different sizes ◦ Disks have a hole in the center Original configuration ◦ Disks stacked on one rod ◦ Descending size order Goal ◦ Move all disks to a different rod ◦ Comply with three rules Rules ◦ Only one disk moved at a time ◦ Only top disk may be moved  Objective Illustration of ◦ Transport all disks from pole 1 to pole 3 Steps ◦ Move disks one at a time Tower of Hanoi ◦ Only move the disk at the top of the current stack ◦ Place smaller disks on top of larger disks Number of Steps ◦ Eight steps to complete the puzzle Quicksort Quicksort Quicksort Overviewapproach Divide-and-conquer Process Starts with a comparison to a pivot Fast algorithm for sorting with a single Divides list into three parts: smaller, processor equal, and larger than the pivot Recursive calls on subproblems: smaller and larger elements Subproblems become trivial when list size is 1 or 0  Base Case If list length is 1 or less, it is already sorted Pivot Selection First element of the list is chosen as pivot Quicksort Function Partitioning Code Elements greater than pivot go to 'bigger' list Elements smaller than pivot go to 'smaller' list Elements equal to pivot go to 'same' list Recursive Sorting Recursively sort 'smaller' and 'bigger' lists Concatenate 'smaller', 'same', and 'bigger' lists  Summary Recursive Function Utility of Recursive Divide-and-Conquer Functions Strategy A function that calls itself Useful for problems with Powerful strategy for solving hierarchical structure difficult problems Problems and Exercises Problem 1: Sum Function Function Definition ◦ Function name: my_sum ◦ Parameter: lst (list of elements) Function Objective ◦ Calculate the sum of all elements in the list ◦ Do not use Python’s sum function Implementation ◦ Use recursion or iteration to solve the problem ◦ Return the sum of elements Example ◦ Input: [1, 2, 3] ◦ Output: 6  Chebyshev Polynomials ◦ Defined recursively ◦ Separated into first and second kinds First Kind: Tn(x) ◦ Recurrence relation: Tn(x) = 2xTn−1(x) Problem 2: − Tn−2(x) ◦ Base cases: T0(x) = 1, T1(x) = x Chebyshev Second Kind: Un(x) Polynomials ◦ Recurrence relation: Un(x) = 2xUn−1(x) − Un−2(x) ◦ Base cases: U0(x) = 1, U1(x) = 2x Function my_chebyshev_poly1(n,x) ◦ Evaluates nth Chebyshev polynomial of the first kind at x ◦ Handles list inputs for x Problem 3: Ackermann Function Definition of Ackermann Function ◦ Defined by recursive relationship ◦ Quickly growing in popularity Function my_ackermann(m,n) ◦ Computes Ackermann function for given m and n ◦ Example: my_ackermann(4,4) is extremely large Practical Uses ◦ Inverse Ackermann function used in robotic motion planning Example Outputs ◦ my_ackermann(1,1) = 3 ◦ my_ackermann(1,2) = 4 ◦ my_ackermann(2,3) = 9  Function C(n, k) ◦ Computes the number of ways to choose k objects from n without repetition ◦ Commonly used in statistics applications Examples ◦ Choosing three ice cream flavors from 10: C(10, 3) Problem 4: Special Cases n Choose k ◦ If n = k, then C(n, k) = 1 ◦ If k = 1, then C(n, k) = n General Case ◦ C(n, k) = C(n − 1, k) + C(n − 1, k − 1) Function Implementation ◦ Write a function my_n_choose_k(n, k) to compute the number of ways k objects can be chosen from n  Definition of Giving Change ◦ Returning money that was overpaid in cash transactions Recursive Relationship ◦ Using recursion to determine the bills and Problem 5: coins required Denominations of US Currency Giving ◦ 100, 50, 20, 10, 5, 1, 0.25, 0.10, 0.05, 0.01 dollars Change Function my_change ◦ Input: cost and paid ◦ Output: list of bills and coins to be returned Example ◦ my_change(27.57, 100) returns [50.0, 20.0, 1.0, 1.0, 0.25, 0.10, 0.05, 0.01, 0.01, 0.01] Problem 6: Golden Ratio Golden Ratio (φ) ◦ Limit of F(n+1) as n approaches infinity ◦ Approximately 1.62 Approximation of Golden Ratio (G(n)) ◦ G(n) = F(n+1) / F(n) ◦ G(1) = 1 Continued Fraction Representation ◦ Recursive relationship for φ Recursive Function ◦ Header: my_golden_ratio(n) ◦ Output: nth approximation of the golden ratio Aspect Ratio of Rectangles  Definition of Greatest Common Divisor (gcd) ◦Largest integer that divides two numbers without remainder Recursive computation of gcd Problem 7: ◦If b equals 0, a is the gcd Greatest ◦Otherwise, gcd(a,b) = gcd(b,a%b) Common Function my_gcd(a,b) ◦Computes gcd of a and b Divisor ◦Assumes a and b are integers Example outputs ◦my_gcd(10, 4) returns 2 ◦my_gcd(33, 121) returns 11 ◦my_gcd(18, 1) returns 1  Pascal's Triangle Definition ◦Arrangement of numbers ◦Each row equivalent to coefficients of binomial expansion Example of Pascal's Triangle Problem 8: ◦(x y)2 = 1x2 2xy 1y2 ◦Third row: 1 2 1 Pascal's Row Representation Triangle ◦Rm represents mth row ◦Rm(n) is nth element of the row Recursive Relationship ◦Rm(i) = Rm-1(i-1) Rm-1(i) for i = 2,...,m-1 Function my_pascal_row(m) 1 1 1 1 1 Problem 9: Spiral Matrix 1 0 0 0 0 Function Definition ◦ my_spiral_ones(n) generates an n x n matrix ◦ Matrix has ones forming a right spiral 1 0 1 1 0 Recursive Steps ◦ Ones go right, then down, then left, then up ◦ Pattern repeats until matrix is filled 1 0 0 1 0 Example Outputs ◦ my_spiral_ones(1) returns [] 1 1 1 1 0 ◦ my_spiral_ones(2) returns [[1, 1], [0, 1]] ◦ my_spiral_ones(3) returns [[1, 1, 1], [0, 0, 1], [1, 1, 1]] ◦ my_spiral_ones(4) returns [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 1, 1], [1, 0, 0, 1], [1, 1, 1, 1]]