Understanding Recursion: A Fundamental Concept in Computer Science
Recursion is a fundamental concept in computer science that involves solving problems by breaking them down into smaller, similar subproblems. This content delves into the basics of recursion, highlighting key components such as the recursive case and base case. It also explores the concept of factorial computation using recursion, demonstrating how factorials of integers can be defined recursively. Through a series of examples and explanations, the content provides insights into how recursion functions and its significance in problem-solving approaches.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Recursion 2 Recursion 2 Recursion 2 Recursion 2 Recursion 2 Recursion 2 Recursion 2 Recursion 2 Recursion 2 CS 112 @ GMU
Recursion Basics Idea: keep doing the same thing, reducing the problem smaller subset of the problem one step closer to the answer Key components recursive case (when to keep going) base case (when to stop)
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 1! = 1 2! = 2 * 1 3! = 3 * 2 * 1 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 1 2! = 2 * 1 3! = 3 * 2 * 1 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 2! = 2 * (1!) 3! = 3 * 2 * 1 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 2 * (1!) 3! = 3 * 2 * 1 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 3! = 3 * (2!) 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 3 * (2!) 4! = 4 * 3 * 2 * 1 n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 4! = 4 * (3!) n! = ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 4! = 4 * (3!) n! = n * ????
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? 4! = 4 * (3!) n! = n * (n-1)!
Yelling, but with math! Factorial! of an integer is the product of that integer and all of the integers between it and 1. Is there a way to define this recursively? n! = n * (n-1)!
Fire up the cloning machine! You have been asked to calculate n! for some integer. You can create a clone. What do you ask them? When might you not even bother making a clone? What do you do then?
Unravel it! Keep cloning, until you reach the base case Which is what? n! = n * (n-1)!
Unravel it! Keep cloning, until you reach the base case Which is what? n! = n * (n-1)! = n * (n-1) * (n-2)!
Unravel it! Keep cloning, until you reach the base case Which is what? n! = n * (n-1)! = n * (n-1) * (n-2)! = n * (n-1) * (n-2) * (n-3)! Eventually, n-x will be equal to one!
Infinite Recursion! Like iteration, recursion can go infinite.
Infinite Recursion! Like iteration, recursion can go infinite. This happens when: You don t ever take on a simple version of the problem without making a clone/recursive call. In other words, there is no base case. You don t make the problem smaller at all, and you re stuck just cloning forever without making progress to a solution. In other words, your recursive call doesn t break down the problem.
Recursion Recipe To use recursion, you might want to follow this pattern: Task 1. Identify the base cases Thoughts "When do I not have to make a clone?" 2. Identify the recursive cases "Does this make the problem smaller?" "Do I get one step closer to a solution?" "Can a clone handle the rest?" 'escape' before any recursive calls 3. Place base case code first 4. Place recursive code after the bases cases Only keep going if you need to handle any error conditions like base cases. Choose how to exit (or what to return) meaningfully. No recursive call needed/wanted.
Helper Methods Not What We d Like def sum_list(seq, i): if i == len(seq): return 0 return seq[i] + sum_list(seq, i+1) Have to pass 0 to kick off the recursion ugly sum_list([1,2,3], 0)
Option 1: Helper Methods What we would like (no index needed) def sum_list(seq): return sum_list_r(seq, 0) def sum_list_r(seq, i): if i == len(seq): return 0 return seq[i] + sum_list(seq, i+1) sum_list([1,2,3])
Option 2: Defaults def sum_list(seq, i=0): if i == len(seq): return 0 return seq[i] + sum_list(seq, i+1) sum_list([1,2,3])
Common Errors Base Case Issues: Improper placement of base case Missing base case Recursive Case Issues: Not shrinking the problem not moving 1 step closer not reducing the problem size Space and/or time inefficiencies please continue to later CS courses!
What about loops? Recursion is just a type of repetition without loops. Easier to define as a human much easier to work out as a mathematician Note: Any repetition can be done with either recursion or iteration (loops): anything that can be done with loops can be done with recursion anything that can be done with recursion can be done with loops
Example: Iteration and Recursion def sum_values_it(start, end): int sum = 0 while (start < end) sum += start start += 1 return sum Changes each time When to stop def sum_values_rec(start, end): if(start == end): return end return start + sum_values_rec(start+1, end)
Recursion: Bad Stuff
Fibonacci Numbers Mathematical definition: fib(n) = 1, if n=0 or n=1 # base case = fib(n-2)+fib(n-1), otherwise # recursive case fibonacci def fib(n): if n<=1: return 1 return fib(n-2) + fib(n-1)
Iterative Fibonacci def fib(n): x,y = 1,1 for i in range(1,n-1): x,y = y,x+y return y Sometimes recursion produces an elegant looking solution, but it is not the most efficient with memory/time.
Challenge Problems Print a list backwards (one item at a time) option 1: start at the end, print, go backwards, stop if too far option 2: start at the beginning, print the end first, stop if no where else to go Count the number of As in a string check first spot, if A, add 1 to the number of As that come after it, if no more string, stop Count the number of chars in a string Similar to count As, but generalize it to any character
Problems def zigzag(grid, value, position): place a zig-zag pattern of values in the 2d grid starting from some position [a (row, col) tuple] example with a value of 'X' and a position of (0,0): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X X 0 0 0 X X 0 0 0 X X 0 0 0 X
Example: Print List Backwards def print_bw(seq, i=None): if i == None: i = len(seq)-1 if i < 0: return print(seq[i]) print_bw(seq, i-1) def print_bw(seq, i=0): if i == len(seq): return print_bw(seq, i+1) print(seq[i]) Trick with default again Can do things on the way back !
Example: Number of As def num_As(str, i=0): if i == len(str): return 0 if str[i] == "A": return 1 + num_As(str, i+1) else: return num_As(str, i+1) Can have multiple recursive cases Can track multiple things going forward def num_As(str, i=0, sum=0): if i == len(str): return sum if str[i] == "A": return num_As(str, i+1, sum+1) else: return num_As(str, i+1, sum)
