Week 9: Methods, Algorithms & Recursion
Methods & Algorithms
Vocabulary Terms:
Methods: Remember that a method is a block of code that performs a specific set of actions that are included in that block. Usually that method has a name, and is called by using that name.
Method Declaration: A method is comprised of the following parts:
access-modifier return-type method-name (parameter-list)
{
body-of-the-method
}
Method Signature: A class can not have two methods with the same method signature, therefore it is important to realize that this needs to be unique at the class level. The signature is unique based on the method-name and the parameter-types. The rest is not included.
method-name (parameter-types)
Algorithm: An algorithm is a precise set of instructions that tells us how to accomplish a task. In computer programming, an algorithm is a language independent set of steps that describe how to accomplish a task or solve a problem.
Algorithm Review
In Week 3, we covered algorithms, and explained that the term algorithm can be applied to daily life. Remember, you have tasks in your life that you know how to accomplish, and the set of steps that you do to accomplish a task is a real-world algorithm.
Here in Week 9, we will take this concept of algorithms a bit further. When searching on the internet for the term algorithm, you might see a number of examples that are deemed Classic Computer Programming Algorithms, like QuickSort, BinarySort, MergeSort, and many more. The term algorithm has come to mean the standard ways to solve certain computing tasks or problems. This may be intimidating, because these may all be new to you. As a reminder, these algorithms are also simply a set of steps used to solve a problem, or to complete a task. Just because they have fancy names, does not mean that they are complex! Keep in mind, as we have previously covered, we use algorithms in daily life, and the transition to computer programming is simply applying the concepts that we know and understand to a technical question or problem.
Algorithm Guidelines
Here are listed some guidelines to keep in mind when creating an algorithm to solve a programming problem.
1. Algorithms should be unambiguous and clear.
2. Algorithms should have zero (0) or more well-defined INPUTS.
3. Algorithms should produce one(1) or more well-defined OUTPUTS that reach or supply the desired result.
4. Algorithms must end after a finite number of steps. Each algorithm needs to have an end or a termination condition.
5. Algorithms should have step by step instructions included.
6. Algorithms should be computer programming language independent.
A Real Life Example of an Algorithm
How do you calculate how much money is in a pile of quarters? Problem: A pile of quarters exists - how do you count them? Even for this simple task, there are many ways to approach the problem. Here we are going to show four simple but distinct algorithms for counting a pile of quarters, and code these algorithms in Java as an example of the many ways to solve a problem, or complete a task, even something as simple as this.
There are a number of ways to accomplish this task: Let's walk through 4 different algorithmic solutions to solving this very simple problem.
The First Algorithmic Solution: Every time you count a quarter, add 25 to a total. When you've gone through all of the quarters, divide by 100 to get the dollar amount, since 100 cents is equal to a dollar.
public static void main(String[] args) {
int numberOfQuarters = 85; //(85 quarters is equal to $21.25)
double totalCents = 0; // Use the double datatype to prevent rounding
double money = 0.0;
for (int index = 0; index < numberOfQuarters; index++) {
totalCents = totalCents + 25;
}
money = totalCents/100;
System.out.println("Solution 1: " + numberOfQuarters + " quarters is equal to $" + money);
}
A Second Algorithmic Solution: Every time you get to 4 quarters, add a dollar to your total. When you're done, add the remainder.
This is very similar to how people count quarters. They make piles of 4 quarters, and then count the number of piles.
public static void main(String[] args) {
int numberOfQuarters = 85; //(85 quarters is equal to $21.25)
double money = 0.0;
// Go through all of the quarters
for (int index = 1; index <= numberOfQuarters; index++) {
if (index%4 == 0) {
money += 1.00;
} else if (index == numberOfQuarters) { // if we are on the last iteration of this loop
money += ((index%4)*0.25); // Add the remainder of the total
}
}
System.out.println("Solution 2: " + numberOfQuarters + " quarters is equal to $" + money);
}
A Third Algorithmic Solution: As we go through the quarters add 0.25 to a total. A quarter is 1/4 of a dollar, so by doing so, at the end, you'll have the correct number of dollars and cents.
public static void main(String[] args) {
int numberOfQuarters = 85; //(85 quarters is equal to $21.25)
double money = 0.0;
for (int index = 0; index < numberOfQuarters; index++) {
money = money + 0.25;
}
System.out.println("Solution 3: " + numberOfQuarters + " quarters is equal to $" + money);
}
A Fourth Algorithmic Solution: Write a method to do this calculation.
public static void main(String[] args) {
int numberOfQuarters = 85; //(85 quarters is equal to $21.25)
System.out.println("Solution 4: " + numberOfQuarters + " quarters is equal to $" + addQuarters(numberOfQuarters));
}
public static double addQuarters(int quantity) {
double quarterValue = 0.25;
double money = 0.0;
for (int index = 0; index < quantity; index++) {
money += quarterValue;
}
return money;
}
Conclusion to "A Real Life Example of an Algorithm"
It is important to reiterate that any given task can be solved in a variety of ways, and thus a variety of algorithms exist for any given task or problem! When solving a task or coding a solution to a problem, the best solution is the one that the programmer understands. Code using the constructs that you know and understand. Additionally, practice makes perfect!
Iterative Solutions: Benefits & Possible Issues
An iterative solution in Java is a programming technique whereby a loop or iteration is used to solve a problem. Loops that are available in Java are: for
loops, while
loops, and do while
loops. This type of solution is obtained when a set of instructions is executed until a certain condition is met.
In an iterative solution, the program repeatedly performs a set of instructions, and evaluates the condition in each iteration.
If the condition is not met, the loop continues to execute until the condition is met.
-Benefits of Iterative Solutions
- Iterative solutions often are more efficient with the space that they use, referred to as space-efficient, because iterative solutions do not require the use of the call stack.
- Iterative solutions can be faster in some cases because they do not require the overhead of creating and managing function calls.
- Iterative solutions can be easier to understand and debug because they use a loop that iteratively computes the solution.
-Possible Issues with Iterative Solutions
- Iterative solutions can be quite complex for certain types of problems.
- Iterative solutions can be less elegant and less intuitive than other solutions, especially for problems that are naturally recursive in nature.
The best solution to a problem, or the best algorithm is the one that the programmer understands and can effectively implement. As a programmer, it is beneficial to first implement a solution iteratively to better understand the problem, the boundaries, and a correct solution. Once an iterative solution is complete, other types of solutions may be explored. This could include a more elegant solution, and a more efficient solution, or maybe even a recursive solution, if the problem lends itself to that type of solution.
Recursion
Recursion is a programming technique that requires a function to call itself. It is like a loop, but instead of repeating a block of code until a condition is met, a recursive function calls itself repeatedly until a certain condition is met. Recursion can be a powerful tool for solving complex problems. The problems solved with recursion are problems that can be broken down into simpler sub-problems.
Recursive Algorithm: A technique or method to solve a problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves these types of problems by writing a function which will call itself within its own code.
There are three important Laws of Recursion:
- A recursive algorithm must have a base case.
- A recursive algorithm must change its state and move toward the base case.
- A recursive algorithms must call itself, recursively.
It is important to realize that the base case is the condition that stops the recursion from continuing, or as mentioned above, is the end or termination condition. As was discussed previously in Week 3, infinite loops occur when the condition that terminates the loop is never reached. Without a base case, the recursion would continue indefinitely, eventually leading to a stack overflow error, which could crash the program, or cause worse issues.
When programming, it is important to evaluate solutions and choices of algorithms, to ensure that a program is as efficient as possible with regard to time and memory or resource use. This is referred to as Big O Notation. Though elegant in form, and concise in code, many recursive solutions and algorithms are discarded because they are too costly, hard to debug, and can overflow the stack quickly. It is important to note that a recursive algorithm can also be coded iteratively, without recursion. The next example is the reverse of that. We are taking the previously discussed Iterative Algorithm, and transforming it into a recursive algorithm.
A Real Life Example of a Recursive Algorithm
Does this look familiar? We wrote 4 algorithmic solutions above to solve the question: How do you calculate how much money is in a pile of quarters? Here is one such solution:
(1) Place the quarters in piles of 4
(2) Each of those piles contains one dollar
(3) Count those piles to get the number of dollars you have.
Let's create a recursive version of this algorithm. To do so, we will write a method that solves this problem, and this method will follow the above Laws of Recursion. To do so, our recursive method countQuarters()
needs to (1) have a base case, (2) change state, and move towards that base case and (3) call itself within the method.
Recursive Algorithm to count quarters: Split the pile, call the function twice, add the results, and so on and so forth.
public static void main(String[] args) {
int numberOfQuarters = 85; //(85 quarters is equal to $21.25)
System.out.println("Solution 5: " + numberOfQuarters + " quarters is equal to $"
+ String.format("%.2f",countQuarters(numberOfQuarters)));
}
public static double countQuarters(int amount) {
if (amount <=4) {
return amount*0.25;
} else {
int half = amount/2;
int secondHalf = amount - half;
return countQuarters(half) + countQuarters(secondHalf);
}
}
Conclusion to "A Real Life Example of a Recursive Algorithm"
It is important to reiterate that any given task can be solved in a variety of ways, we have shown that a recursive solution is possible for something as simple as counting quarters. Remember that a variety of algorithms exist for any given task or problem!