Week 9 - Methods, Algorithms & Recursion

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!

Iterative vs. Recursive Algorithms -- Linear Search vs. Binary Search

There are some standard algorithms in Computing that can be solved recursively.

Iterative Linear Search

   public static int iterativeLinearSearch (int[] arr, int key) {
          for (int index = 0; index < arr.length; index++) {
                 if (key == arr[index]) {
                        return index;
                 }
          }
          return -1;
   }

Binary Search

- Iterative: This Iterative Version of a Binary Search expects a sorted array, and uses a while loop.

   public static int iterativeBinarySearch(int[] arr, int key) {
          int left = 0; 
          int right = arr.length-1;
          while (left <= right) {
                 int middle = (left + right) / 2;
                 if  (arr[middle] == key) {
                        return middle;
                 } else if (key < arr[middle]) {
                        right = mid-1;
                 } else {
                        left = mid + 1;
                 }
          }
          // key doesn't exist in array: arr
          return -1;
   }

- Recursive: This Recursive Version of a Binary Search expects a sorted array, and uses recursive calls.

     public static int recursiveBinarySearch(int[] arr, int low, int high, int key) {
              if (high >= low) {
                  int mid = low + (high - low) / 2;
                  if (arr[mid] == key) {
                      return mid;
                  } else if (arr[mid] > key) {
                      return recursiveBinarySearch(arr, low, mid - 1, key);
                  } else {
                      return recursiveBinarySearch(arr, mid + 1, high, key);
                  }         
              }
              return -1;
          }

Collections.binarySearch()

The Collections Class in Java provides a .binarySearch() method that can be used to perform binary search on a sorted list. The syntax to use Collections.binarySearch() method is as follows:

  int binarySearch(List<? extends Comparable<? super T>> list, T key)

where list is the sorted list to be searched and key is the value to be searched for. Or:

 int binarySearch(List<? extends T> list, T key, Comparator<? super T> comparator)

where list is the sorted list to be searched and key is the value to be searched for, and comparator is the custom comparator used to compare the elements in the list.

              In both cases, the .binarySearch() method returns:
                   1. the index of the first occurrence of the search key in the list, 
                   2. a negative number if the key is not found.   
                             Specifically, it returns `- (insertionPoint + 1)` if the key is not found in the list, where
                             insertionPoint is the index at which the key would be inserted to maintain the sorted order of the list.

Example Java Code Using Collections.binarySearch(list, key)

    import java.util.Arrays;
    import java.util.Collections;
    import java.util.List;

    public class ExampleUsingCollectionsBinarySearch {
              public static void main(String[] args) {
                    List<Integer> list = Arrays.asList(1, 4, 5, 9, 14, 23, 37, 60, 97, 157);
                    int number = 60;
                    int index = Collections.binarySearch(list, number);
                    if (index >= 0) {
                          System.out.println(number + " found at index: " + index);
                    } else {
                          System.out.println(number + " not found in the list.");
                    }
                }
            }

Recursion: Benefits & Possible Issues

Remember, recursion is a programming technique that allows a function to call itself. It's 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. This can be a powerful tool for solving complex problems that can be broken down into simpler sub-problems. One important concept to understand in recursion is the base case. The base case is the condition that stops the recursion from continuing. Without a base case the recursion would continue indefinitely; this will eventually lead to a fatal error, like a stack overflow error, which can crash the program or possibly the computer.

- Benefits of Recursion:

• Simplifies complex problems: Breaking down complex problems into smaller more manageable pieces.
• Code clarity: More readable and understandable code.
• Efficiency: Recursion can be more efficient than iterative solutions.

- Possible Issues with Recursion:

• Stack Overflow: One of the main issues with recursion is the risk of stack overflow which occurs when the call stack becomes too big and runs out of memory. A recursive function adds to the stack with each recursive call, and keeps all of that information there until the last call finishes, using a Last-In-First-Out (or LIFO) Structure, just like the Stack data structure. This occurs when the base case is never reached, or it takes a long time to reach the base case.
• Performance: Recursive solutions can be less efficient due to the overhead of function calls and stack manipulation.
• Difficulty in understanding: Recursion can be difficult to understand, especially for beginners. If the recursion is not well designed, it can be hard to understand and even harder to debug.
• Limitations of programming language: Some programming languages have limitations on the maximum depth of recursion or the amount of stack memory available. This can limit effectiveness of such a solution.

In Java, recursion has limits that depend on the hardware and software architecture being used. The limits are determined by the amount of memory available for the Java Virtual Machine (JVM) to execute the program. The System Stack limit is around 1MB for each stack in most modern operating systems and architectures (64-bit).

Choosing Between an Iterative Solution and a Recursive Solution:

Iterative and recursive solutions are two approaches used in programming to solve problems. Both approaches have advantages and disadvantages, and the choice of which approach to use depends on the problem being solved and the available resources. Above, we have discussed the Advantages and the Disadvantages of iterative solutions and recursive solutions.

Iterative solutions are preferred for problems that require a large amount of memory or processing power, while recursive solutions are preferred for problems that are naturally recursive in nature or that require a more elegant and intuitive solution.

However, there are often trade-offs between the two approaches, and it is important to carefully analyze the problem and choose the most appropriate approach based on the specific requirements and constraints of the problem.

Numeric Tasks with Recursive Solutions

Finding the Factorial of a number

Let's consider an example task or programming problem that can be solved using recursion. Suppose we want to find the factorial of a number. The factorial of a number is the product of all positive integers up to and including that number. For example, the factorial of 4 is 4 x 3 x 2 x 1 = 24.

We can solve this problem iteratively, by using a loop:

    int result = 1;
    for (int index = 1; index <= number; index++) {
             result = result * index;
     }

We can solve this problem using recursion: Defining a function that calls itself with a smaller argument until it reaches the base case of 1.
Here's an example implementation of a factorial function using recursion in Java:

     public static int factorial(int n) {
         // Base case
         if (n == 1) {
             return 1;
         }
         // Recursive case
         else {
             return n * factorial(n-1);
         }
     }

In this implementation, the base case is when n is equal to 1, at which point the function simply returns 1. The recursive case is when n is greater than 1, in which case the function calls itself with n-1 as the argument and multiplies the result by n. It's important to note that recursion can be a bit tricky to understand at first, and it's not always the best solution for every problem. However, when used correctly, recursion can be a powerful tool for solving certain types of problems in an elegant and efficient way.

Calculating the Fibonacci Series

 THREE WAYS to Calculate the Fibonacci Series:
     (1) Print them out Iteratively

     (2) Put them in a Linked List, and Print them Out

     (3) Recursively Calculate the answer and print it

Java Implementation of the Iterative Solutions (1) & (2)

    import java.util.LinkedList;
    import java.util.List;

    public class PrintFibonacciSeries {

       public static void main(String[] args) {

            // (1) Print the first 10 numbers in the Fibonacci Series
            //             0, 1, 1, 2, 3, 5, 8, 13, 21, 34
            int last = 0;
            int current = 1;
            int placeHolder = 0;
            System.out.print(last + " ");
            for (int index = 1; index <= 9 ; index++) {                
                    System.out.print(current + " ");
                    placeHolder = current;
                    current = last + current;
                    last = placeHolder;    
            }
            System.out.println();

            // (2)  Additionally, put the numbers into a linked list, and then print them.
            List<Integer> fibSeries = new LinkedList<>();
            last = 0; 
            current = 1;
            placeHolder = 0;
            fibSeries.add(last);
            for (int index = 1; index < 10; index++) {
                    fibSeries.add(current);
                    placeHolder = current;
                    current = last + current;
                    last = placeHolder;    
            }
           //         Print out linked list:
            for (int num : fibSeries) {
                    System.out.print(num + " ");
            }
            System.out.println();

       }
 }               

Additional Algorithms That Can Be Solved Recursively

    Sorting
           - Binary Sort
           - Quick Sort
           - Merge Sort
           - Insertion Sort
    Soduku
    Topographical Search

And many more…