(fill in your two names here)
Facilitator: (fill in name)
Spokesperson: (fill in name)
Process Analyst: (fill in name)
Quality Control: (fill in name)
If there are only three people in your group, have one person serve as both spokesperson and process analyst for the rest of this activity.
At the end of this Lesson, you will be asked to record how long each Model required for your team. The Facilitator should keep track of time for your team.
Recursion is an alternative method for writing code that repeats. Any recursive program can be written as a loop, but recursion is especially good when the problem can be solved by considering the solution to a smaller program (similar to the idea of nested Russian Matryoshka dolls that fit inside each other):
An example of a recursive application would be one where a program tries to find a solution by generating every possible combination (such as trying every number possible on a Sudoku puzzle).
When faced with a large problem to solve, we can seek to use a solution to a smaller, simpler problem. If we repeatedly decompose the original problem into smaller simpler expressions, eventually, we will identify the most simple or basic component that can’t be broken down any further. This is referred to as the base case.
1. Consider two different ways to show how to calculate $4!$ (the product of the numbers from 1 to 4).
1a. Type out all numbers that explicitly need to be multiplied.
4! =
1b. Now type the expression using $3!$.
4! =
2. Write an expression similar to question 1b showing how each factorial can be calculated in terms of a "simpler" factorial.
2a. 3! =
2b. 2! =
2c. 1! =
2d. 100! =
3. Generalize your group’s answer to question 2 in terms of $n$ to create an equation for factorial that would be true for all factorials except the base case.
n! =
4. What would your group propose to be the base case of a factorial function? Also include your group’s justification for this answer.
5. Assume someone else has already written a Python function factorial(n) that takes n as a parameter and returns n!
5a. Copy and paste your answer to question 2d, which should include how 100! can be calculated using a “simpler” factorial.
5b. Convert your expression in question 5a to "Python" code, making the appropriate method call to this hypothetical factorial() method and "hard coding" numbers as arguments. (note: still put this "Python" in a markdown cell since it won't run anyway)
5c. Now convert your answer for question 3 to "Python" code that would calculate n! This time, you should not "hard code" numbers as arguments.
6. Assume you incorporated your group’s answer to question 5c as part of the function definition for factorial(n). How would this function call differ from function calls you have used in previous programs/notebooks?
7. Is a loop necessary to calculate 3! based on your group’s answers above? Describe/Explain your group’s reasoning.
8. What type of programming structure (sequential, branching or looping) is required to differentiate the successive function calls from the base case?
When a function makes a call to itself, this is referred to as recursion. To define a recursive function in Python, you should write an if-statement that checks for the base case. When the operation is not the base case, you include a call to the function you are writing.
Here is an example of a recursive function (do NOT copy and run this yet):
def factorial(n):
"""calculates n factorial"""
print('n is ', n)
if n == 0: # base case
return 1
else:
print('need factorial of', n-1)
answer = factorial(n-1) # recursive call
print ('factorial of ', n-1, 'was', answer)
return answer * n
9. Examine but do not run the code for factorial() above.
9a. Predict how many distinct calls will be made to the factorial function to calculate the factorial of 3?
9b. Identify the value of the parameter n for each of these separate calls.
Now run the two code cells below
In [ ]:
def factorial(n):
"""calculates n factorial"""
print('n is ', n)
if n == 0:
return 1
else:
print('need factorial of', n-1)
answer = factorial(n-1)
print ('factorial of ', n-1, 'was', answer)
return answer * n
In [ ]:
factorial(3)
10. Examine the output from factorial(3) above.
10a. How many lines were printed when calculating the factorial of 3?
10b. For each printed line, identify which distinct factorial function call printed that line. In other words, which lines were printed by factorial(3), which lines were printed by factorial(2), and so on.
11a. What happens if you try to calculate the factorial of a negative number?
In [ ]:
# run factorial with a negative number
11b. Fix the bug in the function and test it below.
In [ ]:
# fixed factorial()
In [ ]:
# factorial(3) test case
In [ ]:
# factorial(-1) test case
Important questions to answer before writing a recursive function:
To avoid an infinite loop, you must be sure that each recursive call brings you closer to the base case!
12. Consider the factorial problem from the first two models.
12a. How was factorial defined in terms of a smaller similar problem?
12b. How was the problem size made smaller for a recursive call?
12c. What was the base case, and what did you do for the base case?
13. Now consider two different ways to show how to calculate the following sum:
$$\sum_{i=1}^{4}i$$
Look here if you're not familiar with the Sigma notation for summation.
13a. Type out all numbers that explicitly need to be summed:
$\displaystyle \sum_{i=1}^{4}i = $
13b. Write an expression showing how this sum can be calculated in terms of a “simpler” sum.
$\displaystyle \sum_{i=1}^{4}i = $
14. Now answer the same questions for summation:
14a. How could summation be defined in terms of a smaller similar problem?
14b. How can the problem size be made smaller for a recursive call?
14c. What will be your base case, and what did you do for the base case?
14d. How will you make sure each recursive call will bring you closer to the base case?
Not all recursive functions need to have both an if and else statement. Sometimes you only need the if-statement, while other times you might need multiple branches (if-elif-else).
For example, run the code in the cells below
In [ ]:
def count_down(n):
""" counts down to 1 """
if n >= 1:
print(n)
count_down(n-1)
In [ ]:
count_down(10)
15. What is the base case for the count_down function, which did not require an else branch?
16. Modify the count_down function so it counts up (i.e., printing 1 to 10) instead of counting down. You should NOT modify the boolean expression in the if-statement. Instead, you should move entire lines of code (i.e., cutting-and-pasting); wholesale rewriting of lines of code should not be necessary. Ask for help if you cannot figure this out within a few minutes:
In [ ]:
# your count_up function
In [ ]:
# testing count_up
17. Consider the modification changes required if this algorithm was written iteratively (with a loop). Identify and explain one advantage of using a recursive algorithm in contrast to an iterative algorithm.
18. Using the four questions about recursion from Model 3 as hints, explain whether each of the following would work for a recursive solution:
18a. Having two or more base cases:
18b. Having two or more recursive calls:
How much time did it require for your team to complete each Model?
Model 1:
Model 2:
Model 3: