Recursion PDF

Preview

Summary

A recursion handout...

Description

Recursion By: Caitlin Yang ([email protected]) and Michael Oh-Yang (m  [email protected])

Introduction Imagine you are sitting in a very large movie theater in the n-th row and you need to tell your friends what row you are in. However, there aren’t any row numbers to indicate this. The movie theater is so large that it’s hard to stand up and count what row you’re in. The way that you decide to go about finding your row is to ask the person in front of you what row that they are in. You ask the person in front of you, “What row number are you in?”, and each person after that asks the person in front of them the same question. The only row of people that know what row number they are in are the people in the first row because there’s no one else infront of them. When the question reaches the person in the first row, they tell the person behind them “I’m in row 1”. Now the person who asked the question knows that they are in row 2 and so on and so forth until the person in front of you tells you what row that they are in. This “real life” example is very similar to what recursion is. Recursion is defined as a function that calls itself to solve smaller subproblems.

Three Conditions for Recursion 1. Base Case/Terminating Condition a. This is the simplest solution to the recursive problem that you are trying to solve. 2. Recursive Call a. The recursive call is when you call your function again with a modified parameter. 3. Recursive Step a. This is when you either increment or decrement your parameter within your recursive call in order to reach the base case. The recursive step is crucial to a recursive function because if we don’t ever reach our base case, the function will never terminate.

We can identify these three conditions with our real life example! 1. Base Case: a. The person sitting in the first row of the movie theater is our base case because they know exactly which row they are in. 2. Recursive Call: a. The recursive call is when the people in the movie theater ask the same question: “What row number are you in?” 3. Recursive Step: a. The recursive step is when the people in the theater ask the person in front of them what row they are in. The step is that for every question asked, the row number is getting smaller and is approaching the person sitting in the first row.

Simple Recursion Example Let’s write a recursion problem that checks whether a string is a palindrome or not. We want to return True if it is a palindrome and False if otherwise. A palindrome is when a word can be read the same forwards and backwards. Here are examples of palindromes: ● racecar ● kayak ● oo ● a The first and most important part when writing a recursive function is to ask yourself what the base case is. If we look at our list of examples, the smallest palindrome is a single letter and an empty string can even be considered a palindrome. We can write our base case here:

If the length of the string is a single letter (length == 1) or an empty string (length == 0), then we know that the string is a palindrome and we can return True.

So how do we check cases where the length of the string is greater than one? Let’s look at the word racecar. We know that racecar is a palindrome because the first and last letters are the same, the second and last letters are the same, etc. In our recursive function, what we want to do is check if the first and last letters are the same. If they are the same, we can check the other letters in the string, and if they aren’t, then we can immediately return False because the string is no longer a palindrome.

Here we are looking at the first index and the last index to see if the first and last letters are the same in the string: r is equal to r. Now we have to check the other letters in the string. Since we already looked at the first and last letters of racecar, we only need to look at the other letters: aceca. Therefore, we can call the function isPalidrome again on the string aceca to check if it is a valid palindrome. In order to do this, the recursive step that we are using is string splicing the string to get rid of the first and last letters of racecar.

Awesome! We’ve finished writing our recursive function. For the word racecar, we’re checking the strings: ● racecar ● acece ● cec ● e The reason why we stop at e is because in our base case, if the string is less than or equal to length one, then we know that we can return True. Therefore, through our recursive function, we see that racecar is a palindrome. Here are examples on how to trace the isPalindrome function:

This is the case when a string is not a palindrome. Once the recursion hits a point where our condition is not valid, False is passed all the way back up to the original function call.

Recursion and Printing Recursion and printing can be a little difficult to trace and understand at times, especially when the print statement comes after the recursive call. When a print statement comes before the recursive call, you perform it immediately and then perform the function call. However, when a print statement comes after the recursive call, you must wait until everything before the function calls have been executed, and then you can perform the print statements as you move back up the recursive stack. Here’s an example:

Tracing: As we move down to our base case and “chop off” the first character each time, we perform everything that occurs before the function call. In this case, it’s print(string[0]).

Now that we’ve reached our base case, we move back up the recursive calls and perform everything that occurs after the function call. In this case it’s print(string).

Here is the final tracing of the function. As you can see, everytime we move back up to reach our original call, we print(string) to the shell.

Recursion with Dictionaries Recursion can use dictionaries as well. With dictionaries, the process for creating a dictionary is the same. You should create your dictionary in your base case, and as you move up the recursive stack, that’s when you add to your dictionary. Here’s an example:

In this function, we want to count how many times a character appears in a string. Our base case is simple because when a string is empty, that means there are no characters and therefore we can return an empty dictionary. Next, what if the string isn’t empty? The first thing we have to do is get the dictionary from the previously shortened string. At first, this may be confusing, but here’s an example when the length of the string is equal to 1.

The same process goes for strings with lengths greater than 1. The previous dictionary for the shorter string becomes assigned to “aDic” because we are calling the function on count_char(string[1:]), and then we can add to and return aDic.

Recursive Example Guide Question: Make a program that finds the factorial of any positive integers def find_factorial(n): if n == 1: return 1 else: return (n * find_factorial(n-1)) print(find_factorial(4))

So what’s happening in this code? Let’s take a look: find_factorial(4) # 1st call with 4 4 * find_factorial(3) # 2nd call with 3 4 * 3 * find_factorial(2) # 3rd call with 2 4 * 3 * 2 * find_factorial(1) # 4th call with 1 4*3*2*1 # return from 4th call as 4*3*2 # return from 3rd call 4*6 # return from 2nd call 24 # return from 1st call

 umber = 1 ← base case n

So the factorial of 4 is 24. We see that this is true because 4*3*2*1 is equal to 24 by the definition of factorials.

Recursive Tracing def mystery(num): if num == 0: return 1 else: print(num) return mystery(num - 1) mystery(5) Answer:

def gcd(n, m): if m == 0: return n else: return gcd(m, n%m) print(gcd(120, 15)) Answer: def mult(n): if n == 5: return 3 else: return mult(n-1) + 3 for i in range(1,10): print(mult(i)) Answer: def halloween(houses): if len(houses) == 1: house = houses[0] print(“I’m delivering Halloween candies to” + house) else: mid = len(houses) // 2 first _half = houses[:mid] second_half = houses[mid:] halloween(first_half) halloween(second_half) halloween([Will’s house, Jasmine’s house, Michael’s house, Caitlin’s house]) Answer:

Tracing Answer: 1) 5 4 3 2 1 2) 15 3) 3 6 9 12 15 4) I’m delivering Halloween candies to Will’s house I’m delivering Halloween candies to Jasmine’s house I’m delivering Halloween candies to Michael’s house I’m delivering Halloween candies to Caitlin’s house...