i'm so lost. I need to find the second smallest integer in an array recursively. I've started to write the method but I know its wrong and don't know where to go from here.
public static int findSecondSmallest(int [] array)
{
int secSmall = array[0], min = array[0];
if(array.length >= 1)
{
findSecondSmallest(array);
if(secSmall > min)
secSmall = array[0+1];
}
return secSmall;
}
What you could do is to keep track of the smallest one and the second smallest one as you traverse the array from beginning to end. Update them both if you run into something smaller than the second smallest or something bigger than the smallest but less than the second smallest. Hope the following code makes sense:
public class Driver {
public static int MAX_VAL = 1000000;
public static void main(String[] args) {
int[] arr = {2,5,3,6,2,7,43,2,56,2,-1, 1, 5};
int[] smalls = new int[2];
int sm = find(arr, 0, smalls);
System.out.println(sm);
}
public static int find(int[] arr, int index, int [] smalls) {
if(index == 0) {
smalls[0] = arr[index];
smalls[1] = Integer.MAX_VALUE;
find(arr, index+1, smalls);
} else if(index < arr.length){
if(arr[index] < smalls[0]){
smalls[1] = smalls[0];
smalls[0] = arr[index];
} else if(smalls[1] > arr[index]) {
smalls[1] = arr[index];
}
find(arr,index + 1, smalls);
}
return smalls[1];
}
}
Here, index stands for the index of the last element in your 'partial array'. Every recursive step, you examine the first index + 1 elements of your array. Note: small[0] is the SMALLEST element of the partial array and small[1] is the second smallest of the partial array.
For a good treatment of recursion, I recommend you pick up Prolog. This language has no loops and you will rely heavily on recursion.
smalls is the same object between recursive calls makes this solution seem distinctly non-functional in style. I'm sorry to be splitting hairs, but I think the question must be looking for an example of good recursive style, which for me this isn't.This is very easy to do iteratively, so a recursive solution is already a bit contrived, and there are several ways to do it. For example you could write a function which recurses on two halves of the array and gives the second smallest of the four numbers returned. I'll assume you want to split off the first element and recurse on the rest of the array.
The recursive function will return both the smallest and the second smallest in an IntPair, the definition of which I omit, so you will need a wrapper function to extract the second smallest from this pair.
public static int findSecondSmallest(int[] array) {
return findSecondSmallestAndSmallest(0, array).getSecond();
}
private static IntPair recurseSecondSmallest(int index, int[] array) {
if (array.length - index == 2) {
if (array[index] < array[index+1])
return new IntPair(array[index], array[index+1]);
else return new IntPair(array[index+1], array[index]);
}
IntPair recursiveResult = recurseSecondSmallest(index+1, array);
if (array[index] < recursiveResult.getFirst())
return new IntPair(array[index], recursiveResult.getFirst());
else if (array[index] < recursiveResult.getSecond())
return new IntPair(recursiveResult.getSecond(), array[index]);
else return recursiveResult;
}
The trick is smarter pseudocode. This may not be the most efficient algorithm but its stupid smart. also in any case, recursive is not the way to go for such a problem.
secondsmallest(Array of size n)
if n == 2
if array[0] < array[1]
return array[1]
else return array[2]
if n not equal 2 then
remove largest element from the array
return secondsmallest(newArray of size n-1)
