Recursion this is a test
CS 1301 - Intro to Computing
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 in-
front of them. When the question reaches the person in the first row, they tell the person be-
hind 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)
This is the simplest solution to the recursive problem that you are trying to solve.
2. Recursive Call
The recursive call is when you call your function again with a modified parameter.
3. Recursive Step
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!
. Base Case: the person sitting in the first row of the movie theater is our base case
because they know exactly which row they are in.
. Recursive Call: the recursive call is when the people in the movie theater ask the same
question: “What row number are you in?”
. Recursive Step: 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 exam-
ples 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:
def isPalindrome(aString):
if len(aString) <= 1:
return True
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.
def isPalindrome(aString):
if len(aString) <= 1:
return True
else:
if aString[0] == aString[-1]:
# check the other letters
else:
return False
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.
def isPalindrome(aString):
if len(aString) <= 1:
return True
else:
if aString[0] == aString[-1]:
return isPalindrome(aString[1:-1])
else:
return False
Awesome! Weʼve finished writing our recursive function. For the word racecar, weʼre check-
ing the strings:
racecar
aceca
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 be-
fore the recursive call, you perform it immediately and then perform the function call. How-
ever, 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:
def stuff(string):
if len(string) == 0:
print("---")
else:
print(string[0])
stuff(string[1:])
print(string)
stuff('water')
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 dictio-
nary 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:
def count_char(string):
# base case
if len(string) == 0:
return {}
else:
# getting the dictionary from the shortened string
# allows you to have a dictionary to add to
aDict = count_char(string[1:])
# now we just add to the dictionary
if string[0] not in aDict:
aDict[string[0]] = 1
else:
aDict[string[0]] += 1
# lastly we return the dictionary
return aDict
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 aDict because we are calling the function on
count_char(string[1:]) , and then we can add to and return aDict.
