遞歸方法中的堆棧溢出

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]; 
}