递归方法中的堆栈溢出

Question

我正在编写一个程序，允许用户将一组整数输入到数组中，输入零后将显示这些数字的特征。我有一个方法的问题：findMaxOfLessThanFirst。当然，其中，数组中的最大数量也小于输入的第一个数字。这里是完整的代码：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

public class Assignment9 { 
    public static void main(String[] args) throws IOException { 
     int index = 0; 
     int[] numbers; 
     numbers = new int[100]; 

     InputStreamReader inRead = new InputStreamReader(System.in); 
     BufferedReader buffRead = new BufferedReader(inRead); 
     String line = buffRead.readLine(); 

     try { 
      while (!line.equals("0") && index < 100) { 
       numbers[index] = Integer.parseInt(line); 
       index++; 
       line = buffRead.readLine(); 
      } 
     } catch (IOException exception) { 
      System.out.println("Array index out of bound"); 
     } 
     int min = findMin(numbers, 0); 
     int sumAtEven = computeSumAtEvenIndexes(numbers, 0, numbers.length - 1); 
     int divByThree = countDivisibleBy3(numbers, 0, numbers.length - 1); 
     int maxLessThanFirst = findMaxOfLessThanFirst(numbers, 1, numbers.length - 1, numbers[0]); 
     System.out.println("The minimum number is " + min); 
     System.out.println("The sum of numbers at even indexes is " + sumAtEven); 
     System.out.println("The count of numbers that are divisible by 3 is " + divByThree); 
     System.out.println(
       "The maximum number among numbers that are less than the first number is " + maxLessThanFirst); 
    } 

    public static int findMin(int[] numbers, int index) { 
     if (index == numbers.length - 1) { 
      return numbers[index]; 
     } else { 
      return Math.min(numbers[index], findMin(numbers, index + 1)); 
     } 
    } 

    public static int computeSumAtEvenIndexes(int[] numbers, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      if (startIndex % 2 == 0) { 
       return numbers[startIndex]; 
      } else 
       return 0; 
     } else { 
      if (endIndex % 2 == 0) { 
       return computeSumAtEvenIndexes(numbers, startIndex, endIndex - 1) + numbers[endIndex]; 
      } else { 
       return computeSumAtEvenIndexes(numbers, startIndex, endIndex - 1); 
      } 
     } 
    } 

    public static int countDivisibleBy3(int[] numbers, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      if (numbers[startIndex] % 3 == 0) { 
       return +2; 
      } else { 
       return 1; 
      } 
     } else { 
      if (numbers[endIndex] == 0) { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1); 
      } 
      if (numbers[endIndex] % 3 == 0) { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1) + 1; 
      } else { 
       return countDivisibleBy3(numbers, startIndex, endIndex - 1); 
      } 
     } 
    } 

    private static int findMaxOfLessThanFirst(int[] numbers, int startIndex, int endIndex, int firstNumber) { 
     if (startIndex == endIndex) { 
      if (numbers[endIndex] <= firstNumber) 
       return numbers[startIndex]; 
     } 
     int max = findMaxOfLessThanFirst(numbers, startIndex, endIndex - 1, firstNumber); 
     if (max >= numbers[endIndex] && max <= firstNumber) { 
      return max; 
     } 
     return numbers[endIndex]; 
    } 
} 

我相信我在这里错过了一些非常基本的东西。我刚开始学习递归的概念。所以，请温柔。

Answer 1

您只需要在第一个if内删除嵌套的if条件即可。这是多余的，因为startIndex和endIndex都是相同的。下面应该工作：

private static int findMaxOfLessThanFirst(int[] numbers, int startIndex, int endIndex, int firstNumber) { 
    if (startIndex == endIndex) { 
     return numbers[startIndex]; 
    } 
    int max = findMaxOfLessThanFirst(numbers, startIndex, endIndex - 1, firstNumber); 
    if (max >= numbers[endIndex] && max <= firstNumber) { 
     return max; 
    } 
    return numbers[endIndex]; 
} 

Answer 2

您正在运行到一个无限递归（这在通常情况下，当一个在递归程序得到StackOverflowError）。你试过这个代码停止递归：

if (startIndex == endIndex) { 
     if (numbers[endIndex] <= firstNumber) 
      return numbers[startIndex]; 
    } 

然而，当startIndex == endIndex（你唯一的机会），如果numbers[endIndex] > firstNumber，这并不能阻止递归，如此这般 - “只有”不是无限，直到你击中StackOverflowError。

Answer 3

您缺少else分支。如果您有if，那么必须有else，我将其用作编程规则。在某些情况下，else也许没用，在这种情况下，我把一些日志信息放在else。

private static int findMaxOfLessThanFirst(int[] numbers, int startIndex, int endIndex, int firstNumber) { 
    if (startIndex == endIndex) { 
     if (numbers[endIndex] <= firstNumber) 
      return numbers[startIndex];   
     else return Integer.MIN_VALUE; 
    } 
    int max = findMaxOfLessThanFirst(numbers, startIndex, endIndex - 1, firstNumber); 
    if (max >= numbers[endIndex] && max<=firstNumber) { 
     return max; 
    } 
    return numbers[endIndex]; 
}