1

For something I am working on I need to have an integer array, and get two indices from the user. One being a starting point in the array, and the other being an ending point. With these two points I have to find the max value within the array, recursively. The code I currently have works, but I feel like there are things that could make it more fluent, and maybe even I could do somethings different to get rid of some useless code. I will post my code below. 

import java.util.Scanner;

public class RecursiveProblem {

    public static void main(String args[]) {
        int start, end, size, max;
        Scanner scan = new Scanner(System.in);

        System.out.println("How many numbers would you like to enter in total?");
        size = scan.nextInt();
        int[] myArray = new int[size];

        System.out.println("Please enter the specified starting index.");
        start = scan.nextInt() - 1;

        System.out.println("Please enter the specified ending index.");
        end = scan.nextInt() - 1;

        System.out.println("Please enter " + size + " integers seperated by a space, or press "
                + "enter after each number: ");
        for(int i = 0; i < myArray.length; i++) {
            myArray[i] = scan.nextInt();
        }
        scan.close();

        max = myArray[start];

        max = findMax(myArray, start, end, max);

        System.out.println("The max of your array between the indices of " + (start + 1) +
                "-" + (end + 1) + " is..." + max);

    }

    public static int findMax(int[] myArray, int start, int end, int max) {
        if(start < end) {
            if(myArray[start + 1] > max) {
                start++;
                max = myArray[start];
                return findMax(myArray, start, end, max);
            }
            else {
                start++;
                return findMax(myArray, start, end, max);
            }
        }
        return max;
    }
}

One thing I am mainly confused about, but not the only question I have--is whenever I opt to put the start++ command inside the function call for findMax(myArray, start++, end, max) <--(like so), it will end up in infinite recursion. I am confused as to why this causes infinite recursion, but the way I did it does not. Thank you in advance for the assistance on cleaning up the code, and helping me out with my question!

Improve this question
2
  • 2
    Using ++start instead of start++ would make sure the start variable is increased by one before invoking the method and thereby avoiding the infinite loop. Commented Apr 19, 2020 at 21:40
  • 1
    Okay, I will look into the other answers as I'm working on another problem at the moment. Although, the end param actually is necessary because the user can choose what starting and ending indices they would like to find the max of. So it does not necessarily have to be the array length! Commented Apr 19, 2020 at 22:15

3 Answers 3

Reset to default
1

Your code is okay overall but if you want something concise you can use the code below:

//Before calling this particular method, you'll have to set the max to 
//Integer.MINIMUM_VALUE so it's guaranteed to be changed later OR call it
//with start + 1 instead of start
public static int findMax(int[] myArray, int start, int end, int max) {
  return (start < end) ? 
    findMax(myArray, 
            start + 1, 
            end, 
            (myArray[start] > max) ? myArray[start] : max))
    : max;
}

The reason that you recur infinitely is because of how the post-increment operator works.

When you say start++, it push the value of start onto the stack and then increments it in the background. So it's fine as a standalone statement but when you write it as findMax(myArray, start++, end, max), it's really the same thing as calling findMax(myArray, start, end, max), because the argument start is really unchanged.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you very much, the symbols you used to make the code more concise are ternary operators, correct? I have not had much exposure to them besides in class. Would you suggest becoming more familiar with them? Obviously I do not have exposure with writing or reviewing code written for companies, so I am not sure how often these are used. Thank you for the assistance though!
Ternary operators aren't used all that often, but I like them because they're nice and concise. I suppose you don't really have to become familiar with them, and I suspect that some people might even find that code above disgusting, even if some people think it's okay.The outer conditional operator may be a bit much, but I feel the inner one simplifies code. It's really a matter of opinion.
Okay thank you very much! I will look into them just for the purpose of making the code shorter, and more simple like you stated.
1

You're on the right track but your solution can be simplified.

The key observation is that the maximum element of an array is either:

  1. The first element, or

  2. The maximum of the rest of the array after the first element 

    // requires start <= end (not checked, left as exercise for reader)  
public static int findMax(int[] myArray, int start, int end) {  
    if (start < end) {  
        int maxOfRest = findMax(myArray, start+1, end);  
        return myArray[start] > maxOfRest ? myArray[start] : maxOfRest;  
    }  
    else { // start == end  
        return myArray[start];  
    }  
}

Note my solution does not need to carry the 'max so far' into each recursive activation of findMax -- I think that makes it cleaner.

Footnote: the ?: operator is properly called the conditional operator. It is sometimes referred to as 'the ternary operator', but all that means is 'the operator with three operands', unlike the various binary operators (two operands) and unary operators (one operand), so it's not particularly informative.

Improve this answer

Comments

1

All you need to pass is the array and the value 0

  • Start by initializing m to the ultimate minimum value.
  • then keep calling max until i == the array length - 1
  • then simply compare the values of m as they are returned from the call stack to the value in the array pointed to by i
int [] a = {1,3,20,2,55,32,4,9,44,10,29};
int m = max(a,0);
System.out.println(m);


public int max(int[] a, int i) {
   int m = Integer.MIN_VALUE;
   if (i < a.length-1) {
       m = max(a,i+1);
   }
   return m > a[i] ? m : a[i];
}

Prints

55
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.