Java: Recursively Finding the minimum element in a

Question

I will preface this by saying it is homework. I am just looking for some pointers. I have been racking my brain with this one, and for the life of me i am just not getting it. We are asked to find the minimum element in a list. I know i need a sublist in here, but after that i am not sure. any pointers would be great. thanks.

/** Find the minimum element in a list.
 * 
 * @param t a list of integers
 * 
 * @return the minimum element in the list
 */ 
  public static int min(List<Integer> t) { 
  if (t.size() == 1){ 
  return t.get(0); 
  } 
  else{ 
      List<Integer> u = t.subList(1, t.size());

Answer 1

In the most general sense, recursion is a concept based on breaking down work, and then delegating the smaller chunk of work to a copy of yourself. For recursion to work, you need three main things:

1. The breakdown of work. How are you going to make each step "simpler"?
2. The recursive call. At some point your function must call itself, but with less "work".
3. The base case. What is a (usually trivial) end case that will stop the recursion process?

In your case, you're trying to create a function min that operates on a list. You're correct in thinking that you could somehow reduce (breakdown) your work by making the list one smaller each time (sublist out the first element). As others have mentioned, the idea would be to check the first element (which you just pulled off) against the "rest of the list". Well here's where the leap of faith comes in. At this point, you can "assume" that your min function will work on the sublist, and just make a function call on the sublist (the recursive call). Now you have to make sure all your calls will return (i.e. make sure it will not recurse forever). That's where your base case comes in. If your list is of size 1, the only element is the smallest of the list. No need to call min again, just return (that part you already have in your original post).

Answer 2

The point of a recursive algorithm is that everything that must be computed is done through return values or additional parameters. You shouldn't have anything outside the local call of the recursive step.

Since you have to find the minimum element you should take some considerations:

• the min element of a list composed by one element is that element
• the min element of a generic list is the minimum between the first element and the minimum of the remaining list

By taking these into consideration it should be easy to implement. Especially because recursive algorithms have the convenience of being really similar to their algorithmic description.

Answer 3

/**
 * The function computes the minimum item of m (-1 if m is empty). 
 * @param m: The MyList we want to compute its minimum item.
 * @return: The minimum item of MyList    
 */ 
public int minimum(MyList<Integer> m){

    int res = 0;
    int e0 = 0;
    int e1 = 0;

    // Scenarios Identification
    int scenario = 0;

    // Type 1. MyLyst is empty
    if(m.length() == 0) {
        scenario = 1;
    }else {
    // Type 2. MyLyst is not empty
        scenario = 2;
    }

    // Scenario Implementation
    switch(scenario) {

    // If MyLyst is empty
    case 1:
        res = -1;
        break;
        // If there is 1 or more elements   
    case 2:
        //1. Get and store first element of array
        e0 = m.getElement(0);
        //2. We remove the first element from MyList we just checked
        m.removeElement(0);
        //3. We recursively solve the smaller problem
        e1 = minimum(m); 
        //4. Compare and store results
        if(e0 < e1) {
            res = e0;
        }
        else {
            res = e1;
        }
        //5. Return removed element back to the array
        m.addElement(0, e0);
        break;
    }
    //6. Return result 
    return res;
}

Answer 4

You need to find the relationship between the function min applied to a list and the function min applied to a sublist.

min([a b c d e ...]) = f(a, min([b c d e ...]))

Now you just need to find the function f. Once you have the relationship, then to implement it is easy. Good luck.

Answer 5

There you go, Try this out in the method:

    public static Integer minimum(List<Integer> t) {
        int minInt;
       if (t.size() == 1) {
        return t.get(0);
       } else {
            int first = t.get(0);
            List<Integer> u = t.subList(1, t.size());
            minInt = Math.min(first, u.get(0));
            minInt = IntegerList.minimum(u);
          }
         return minInt;
      }

Hopefully this solves your issue.