Previous Lecture  Lec16  Next Lecture 
Lec16, Wed 02/26
Recursion is Recursion
Reading
 Chapter 10 in the Perkovic book
 Read the chapter up until “Fractals” (page 338)
 Read from “Linear Recursion” (page 345) up until Section 10.4 “Searching”
 Work through the sample problems and the exercises in the book
Recursion
 Recrusive functions call themselves to execute the same operations over and over
 Often, a recursive function can be written iteratively (with a loop), but they might behave differently and can be harder to write

A simple base case (or cases): does not use recursion to produce an answer
 Example: How could you find out how many people are in line if each person can only see the person directly in front of them?
 Each person asks the person in front of them “How many people are in front of you?”
 Since each person does not know the total, they will ask the person in front of them.
 Once the question reaches the first person in line, that person can confidently answer “There is no one in front of me.”
 Then, the person before them (the second person in line) can take the answer they got (0 people), add 1 to it, and answer with confidence that “There is one person in front of me.”
 The 3rd person in line now adds 1 to it, and responds “There are two people in front of me.”
 This can go on and on until the last person in line knows how many people are in line.
The simplest case is called the Base case: There is nothing to do.
Example: Doing dishes
 Simplest case (base case): There are no dishes. You’re done!
 Next simplest case: There is one dish. You wash it and remove it from the sink.
 Now, you are back to the base case – there are no dishes. You’re done!
 Next simplest case: There are two dishes.
 You wash one and remove it from the sink.
 Now, we are back to the previous simplest case when there is one dish. You wash it.
 Now, you are back to the base case – there are no dishes. You’re done!
 Next simplest case: There are 3 dishes. You wash one. Now there are 2 dishes. You wash one. Now there is one dish. You wash it. Now there are no dishes. You’re done!
 etc.
Each recursive case should get you closer to the base case.
def doDishes(numDishes):
if numDishes == 0:
# return "You're done!"
else:
# wash one dish
# remove it from the sink
# return doDishes(numDishes  1)
(* Assume numDishes
is a nonnegative integer)
See slides for additional examples of recursion (e.g., Droste Effect, Sierpinski triangle).
Solving recursion
 A simple base case (or cases): does not use recursion to produce an answer
 typically returns a fixed value
 the simplest possible case
 A recursive case, when the function calls itself on the next simplest input
 Usually has to include a
return
statement (unless we only need to print)  Always has to call the function itself …
 … with the input to the recursive function that gets you closer to the base case
 Usually has to include a
 Note: the structure would usually involve having
if / else
statement(s) to decide which case to run  Goal: find a set of rules that reduce all other cases toward the base case.
When designing a recursive solution, we need to answer the following questions:
 What’s our base case (or cases)?
 What action should be taken in the case case? What is
print
ed orreturn
ed?  What’s the first recursive case (next simplest input)?
 What action do we need to take to get from the first recursive case to the base case?
A skeleton of the recursive function
# Note, this is just a pseudocode skeleton structure
def recF(input):
if input ...
print/return # base case / cases
else / elif
print/return recF( input => base case )
# => stands for "that gets you closer to"
# so, the recursive case is supposed to use
# the input that gets you closer to the base case
The classic examples: Fibonacci and Factorials
Factorial
Factorial represents the number of permutations (combinations) of arranging a set of n
items.
n n! Resulting combinations of n items
1 1 {1}
2 2 {1,2}, {2,1}
3 6 {1,2,3}, {1,3,2},
{2,1,3}, {2,3,1},
{3,1,2}, {3,2,1}
In other words…
• 0! = 1 # An empty set can only be ordered one way, so 0! = 1
• 1! = 1
• 2! = 2∙1=2
• 3! = 3∙2∙1=6
• 4! = 4∙3∙2∙1 = 24
Looks like we have a formula:
n! = n∙(n – 1)!
So, for any given n
, to compute the factorial of n
, we need to find the product of the successive numbers between 1 and n
.
Let’s try expressing this in Python.
But first, we need to answer:
 What’s our base case (or cases)?
 What’s
print
ed orreturn
ed?
 What’s
 What’s the next simplest input (first recursive case)?
 What action do we need to take to get from the first recursive case to the base case?
If we correctly answer these questions, we would have the pseudocode / algorithm for the solution:
 What’s our base case (or cases)?
0! or 1!
* What’sprint
ed orreturn
ed? * We need toreturn 1
 What’s the next simplest input (first recursive case)? That would be
2!
. What action do we need to take to get from the first recursive case to the base case?
 We need to
return
the2
multiplied by the previous factorial, which is1!
 To get the “previous factorial” from the step above using our current input
2
, we need to use(21)! = 1!
 We need to
 What action do we need to take to get from the first recursive case to the base case?
Let’s check if the above logic works for the next recursive case, which is 3!
.
 Next recursive case: input
3
(i.e., compute3!
) What action do we need to take to get from this input to the case that’s closer to the base case?
 We need to
return
the3
multiplied by the previous factorial, which is2!
 To get the “previous factorial” from the step above using our current input
3
, we need to use(31)! = 2!
 Note that this correctly gets us back to the first recursive case, which is
2!
, and from there, we know that2!
goes to the base case.  Woohoo! Recursion works.
 We need to
 What action do we need to take to get from this input to the case that’s closer to the base case?
And now in Python:
def factorial(n):
if (n == 0):
return 1
else:
return n*factorial(n1)
Now, the call of factorial(3)
results in the following call stack (similar to the steps we traced above):
factorial(3)
3 * factorial(31)
2 * factorial(21)
1 * factorial(11)
1
Note: if we forget to include the return
inside the recursive case, then the function will return nothing, which means the return value will be None
.
Checking for invalid input
 What if
n
is set to be"two"
?
>>> factorial("two")
...
return n * factorial(n1)
TypeError: unsupported operand type(s) for : 'str' and 'int'
The TypeError
points at the fact that we cannot use a subtraction between str' and 'int'
.
 What if
n
is2.1
?
>>> factorial(2.1)
...
return n * factorial(n1)
[Previous line repeated 1021 more times]
File "/....py", line 2, in factorial
if n==0:
RecursionError: maximum recursion depth exceeded in comparison
2.1  (1 * any integer)
will never equal 0. The base case will never be reached, so there will be an infinite recursion.
Python cannot handle an infinite recursion, so it will produce an error: RecursionError: maximum recursion depth exceeded in comparison
.
This is the error that you’ll see if your function never reaches the base case.
Writing helper functions
However, we should not check if we got the correct input within the recursive function, because the code of the recursive function runs every time that function is called. Instead, we want to check the input once, to decide if it is safe call the recursive function. In this case, the recursive function will be the helper function.
Let’s create a new function getFactorial(n)
that calls factorial(n)
if and only if the user inputs a valid value of the valid type.
Below is one potential version with a very generic error.
# One potential version
def getFactorial(n):
'''
Check that n is >= 0
and is an integer.
If it is not, print an Error,
Otherwise, return the value n!
'''
if type(n) == int and n >= 0:
return factorial(n)
else:
print("Error")
Here’s another potential version with the two check separated using if / elif
:
def getFactorial(n):
'''
check that n is an integer>=0
return n!
Otherwise, print an error
'''
if type(n) != int:
print("Error: incorrect type")
elif n < 0:
print("Error: incorrect value", n)
else:
return factorial(n)
 Question: Could you do the same for type checking using only
if
statements andreturn
statements (instead ifif
andelif
)? Answer: Yes, you can: as long as you include the
return
that stops the function. Otherwise, you need anelif
, so that you do not proceed with the rest of the function, since you do not want to callfactorial(n)
with an invalidn
.
Here is an example of how you can write this function using only
if
statements andreturn
statements:  Answer: Yes, you can: as long as you include the
def getFactorial(n):
'''
check that n is an integer>=0
return n!
Otherwise, print an error
'''
if type(n) != int:
print("Error: incorrect type")
return
if n < 0:
print("Error: incorrect value", n)
return
else:
return factorial(n)
Note: if we forget to include the return
inside the recursive case, then the function will return nothing, which means the return value will be None
.
>>> getFactorial(2)
>>> num = getFactorial(2)
>>> print(num)
None
Once we add the return
, we can correctly check if the function correctly handles it if the user inputs 2.1
.
>>> getFactorial(2)
2
>>> getFactorial(4)
24
>>> getFactorial(2.1)
Error: incorrect type
>>> getFactorial(2)
Error: incorrect value 2
>>> getFactorial("two")
Error: incorrect type
We can also get very descriptive and output the incorrect type and the value of the provided input.
# new function
def getFactorial(n):
'''
check that n is an integer>=0
return n!
Otherwise, print an error
'''
if type(n) != int
print ("Error: incorrect input type", type(m))
return
if n < 0:
print("Error: incorrect input value", n)
#return # see what happens if there's no return
else: # n is a valid input
return factorial(n)
Fibonacci numbers
A Fibonacci number is a number in a sequence of numbers (the Fibonacci sequence), such that each number is the sum of the two preceding ones. The Wikipedia article has a lot of fascinating information about the Fibonacci numbers (did you know that they are related to the golden ratio?). Sometimes, you see the Fibonacci sequence starting from 0 and 1. In lecture, we started them at 1 and 1.
1 1 2 3 5 8 13 ...
Fibonacci numbers (values)1 2 3 4 5 6 7 ...
the indexn
of each number (e.g., 1st, 2nd, 3rd Fibonacci number)
def fibonacci(n):
'''
returns the nth fibonacci term
'''
if n == 1:
return 1
if n == 2:
return 1
if n == 3:
return fibonacci(1) + fibonacci(2)
if n == 4:
return fibonacci(2) + fibonacci(3)
if n == 5:
return fibonacci(3) + fibonacci(4)
...
# How do we generalize this?
We can generalize this like so:
def fibonacci(n):
'''
returns the nth fibonacci term
'''
if n == 1:
return 1
if n == 2:
return 1
else:
return fibonacci(n  2) + fibonacci(n  1)
Recursion in CS 16 and beyond
If you continue taking CS classes, you’ll see recursion again in CS 16 and beyond:
 Recursion on the linked lists
 Binary search
 Traversing networks
 Webbased operations