The goal of this assignment is to learn the following:
- Recursion and how it's used
- How to identify reusable components from existing code
Computer Science Principles Curriculum
- Big Idea: Algorithms: EK 4.1.1A, EK 4.1.1B, EK 4.1.1C, EK 4.1.1D, EK 4.1.1E, EK 4.1.1F, EK 4.1.1G, EK 4.1.1H, EK 4.2.1A, EK 4.2.1B
- Big Idea: Programming: EK 5.1.2A, EK 5.1.2B, EK 5.2.1A, EK 5.2.1B, EK 5.2.1C, EK 5.2.1D, EK 5.2.1E, EK 5.5.1A, EK 5.5.1D
Common Core Standards
- English Language Arts Standards » Science & Technical Subjects: CCSS.ELA-Literacy.RST.9-10.3, CCSS.ELA-Literacy.RST.9-10.4, CCSS.ELA-Literacy.RST.9-10.5, CCSS.ELA-Literacy.RST.9-10.7, CCSS.ELA-Literacy.RST.9-10.10, CCSS.ELA-Literacy.RST.11-12.2, CCSS.ELA-Literacy.RST.11-12.3, CCSS.ELA-Literacy.RST.11-12.4, CCSS.ELA-Literacy.RST.11-12.5, CCSS.ELA-Literacy.RST.11-12.10
- Mathematics Content: High School Functions » Building Functions: CCSS.Math.Content.HSF.BF.1A
- Standards For Mathmatical Practice: CCSS.Math.Practice.MP1, CCSS.Math.Practice.MP2, CCSS.Math.Practice.MP4, CCSS.Math.Practice.MP5, CCSS.Math.Practice.MP6, CCSS.Math.Practice.MP7, CCSS.Math.Practice.MP8
In this assignment you will be modifying Assignment 5.1, where you had to create a radio which played a user-determined station for a user-determined length of time. It also had you create two separate files for your source code, and taught you how to save the Station class to an existing package.
You will be changing the play action in the Station class to use recursion instead of a repeat statement. Recursion is when a function calls itself, and each time it calls itself it moves closer and closer to meeting its end condition. An end condition is a condition that, when met, the recursive action stops calling itself. An example of this is having an end condition be when some integer variable is 0. This end condition is technically termed the base case.
The code below calculates the factorial of a given number using recursion. The factorial of a number is the multiplication of that number with all integers smaller than it, but greater than or equal to 1. For example, in Quorum, one might hard code the factorial of 5 as:
integer FactorialOfFive = 5 * 4 * 3 * 2 * 1
which is the integer value 120.
action Main integer a = Factorial(5) output "a is equal to" + a end action Factorial (integer num) returns integer // This is the "base case" condition. You want to stop multiplying integers when you reach one. Otherwise, you will compute the wrong answer, particularly if you mistakenly multiply by 0! if num <= 1 return 1 else // This is the recursive step. return Factorial(num-1) * num end end
"a is equal to 120"
What's happening in this example is that the end condition, also called a base case is:
if num <= 1 then return 1
This is the condition that will stop the recursive calls when it's met. The original call to that action, 5 in this case, got passed into the factorial function and started the recursive chain. After it ran through the function the first time it got to:
return Factorial(num-1) * num
Thus calling itself, the Factorial action, with num -1. Num is now one step closer to the base case, which is equal to or less than one. Consider what would happen if you used an addition operator in place of the subtraction operator. Would the program ever end? What about if num wasn't changed in the function?
An important take-away from this is that recursive actions have to have parameters to communicate with themselves. Without parameters there is no way for a recursive action to call itself while working towards a base case. What would happen if the recursive action was instead:
action Factorial() returns integer if num <= 1 then return 1 end else then num-1 return Factorial() * num end end
In that code example there is no way for the recursive action to pass the information that num got decremented by 1 to the next action call. It would go into an infinite loop and crash the program.
- Open your project from 5.1
- In your Station.quorum file delete the contents of the Play action, keeping the action declaration and end statement. Leaving you with:
private action Play(integer time, integer note) returns integer end
- Inside this action use a Music object to play a series of notes, up to 10. For example:
music:Play(note, .1) music:Play(note+3, .1) ...
- Establish a base case that one of your parameters will meet
- Complete the recursive function by appropriately calling the Play action
Entering an invalid time
"Please select your station (1-4):" "3" "How long do you want to play? (1-20):" "0" "Incorrect input. Please try again." "How long do you want to play? (1-20):"" "6"
Entering an invalid station
"Please select your station (1-4):" "5" "Incorrect input. Please try again." output] "Please select your station (1-4):" "4" "How long do you want to play? (1-20):" "10"
Entering valid information
"Please select your station (1-4):" "2" "How long do you want to play? (1-20):" "19"
In the next tutorial, we will discuss Assignment 5.3, which describes a practice session on using arrays to store student grades.