Блог

Итак, у меня есть этот программный проект, в котором мне нужно создать программу, которая определяет, является ли число идеальным квадратом, и если да, то записать его в документ .txt. Это очень легко и эффективно сделать с помощью цикла for, однако в инструкциях к назначению говорится, что программа должна выполнить это с помощью рекурсии. Это итеративный оператор, который я придумал:

 double division;
        for (int i = 0; i < inputs.size(); i  ) {
            division = (Math.sqrt(inputs.get(i)));
            if (division == (int)division) {
                pw.println(inputs.get(i));
                 }
            }
  

Где inputs — список массивов, который создается путем чтения входных данных пользователя.
Это решает проблему, но, как я уже сказал, это должен быть рекурсивный оператор. Я знаю, что для рекурсии мне нужен базовый вариант, который в конечном итоге заставит метод перестать вызывать себя, но я не могу понять, каким будет базовый вариант. Кроме того, я видел несколько примеров преобразования из итерации в рекурсию, но во всех этих примерах используется одна int переменная, и в моем случае мне нужно сделать это с помощью ArrayList .
Любая помощь была бы высоко оценена

Для рекурсивной функции вы можете использовать алгоритм бинарного поиска:

  int checkPerfectSquare(long N,  
                              long start, 
                              long last) 
{ 
    // Find the mid value 
    // from start and last 
    long mid = (start   last) / 2; 
  
    if (start > last) 
    { 
        return -1; 
    } 
  
    // Check if we got the number which 
    // is square root of the perfect 
    // square number N 
    if (mid * mid == N) 
    { 
        return (int)mid; 
    } 
  
    // If the square(mid) is greater than N 
    // it means only lower values then mid 
    // will be possibly the square root of N 
    else if (mid * mid > N) 
    { 
        return checkPerfectSquare(N, start,  
                                  mid - 1); 
    } 
  
    // If the square(mid) is less than N 
    // it means only higher values then mid 
    // will be possibly the square root of N 
    else 
    { 
        return checkPerfectSquare(N, mid   1,  
                                  last); 
    } 
} 
  

Вы могли бы использовать тот факт, что квадратное число является суммой нечетных целых чисел. Например.

1 3 = 4 = 2^2

1 3 5 = 9 = 3^2

1 3 5 7 = 16 = 4^2, и т. д

 public static void main(String[] args) {
    for (int i = 1; i < 1000; i  ) {
      if (isSquare(i)) System.out.println(i);     
    }
  }
  public static boolean isSquare(int n) {
    if (n==0 || n==1) return true;
    return isSquare(n,1,1);
  }

  private static boolean isSquare(int n, int sum, int odd) {
    if (n==sum) return true;
    if (n < sum) return false;
    odd  = 2;
    sum  = odd;
    return isSquare(n, sum, odd);
  }
  

вывод:

 1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
676
729
784
841
900
961
  

Вы могли бы рекурсивно проверить, равен ли квадрат любого меньшего значения int вашим входным данным.

 public static boolean isSquare(int n) {
  if (n==0 || n==1) return true;
  return isSquare(n, 1);
}

private static boolean isSquare(int n, int i) {
  if (i*i == n) return true;
  if (i*i > n) return false;
  return isSquare(n,i 1);
}