Блог

Я должен закодировать рекурсивный метод, который выполняет итерацию по связанному списку и возвращает количество положительных целых чисел. Вот вопрос:

countPos Приведенный ниже метод должен быть рекурсивным методом, который принимает Node заголовок в качестве аргумента, идет вниз по списку, возглавляемому head , и подсчитывает количество узлов, которые имеют положительное поле данных.

Однако код, который у меня есть, работает, я не понимаю, как он работает.

 public int countPos(Node head) {
    int count = 0; 
    if (head == null) { return count; }

    if (head.data > 0) {
        count  ; 
        return count   countPos(head.next);
    } else {
        return count   countPos(head.next);
    }
}
 

Проблема, с которой я сталкиваюсь, заключается в том, что я не понимаю, как count не возвращается к 0 при каждом вызове метода. По какой-то причине оператор int count = 0; игнорируется при следующем вызове метода. Это потому, что я тоже возвращаюсь count ? Любое объяснение будет с благодарностью.

Спасибо.

НЕ начинайте с отслеживания выполнения или отладки. Сила рекурсии в том, что она позволяет вам рассуждать о сложных программах с помощью простой логики.

Ваш код работает случайно. Это отражает то, что тот, кто это написал (вы?), Не понимает, как рекурсия решает проблемы. Это сложнее, чем необходимо.

Чтобы использовать рекурсию, возьмите проблему под рукой и:

1. Определите функциональный интерфейс.
2. Разделите проблему на части, по крайней мере одна из которых является уменьшенной версией той же проблемы.
3. Решите эту (или те) меньшую версию (версии), вызвав сам интерфейс функции.
4. Найдите «базовый вариант» или варианты, которые являются решениями для очень маленьких экземпляров одной и той же проблемы.

После всего этого псевдокод для большинства рекурсивных алгоритмов будет:

 function foo(args)

   if args describe a base case
     return the base case answer.

   solve the smaller problem or problems by calling foo with 
     args that describe the smaller problem!

   use the smaller problem solution(s) to get the answer for this set of args

   return that answer
end
 

Давайте применим это к вашему случаю:

ПРОБЛЕМА: подсчитайте количество положительных элементов в списке.

1. Определите интерфейс функции: int countPos(Node head) .
2. Разделите проблему на части: получите количество положительных значений в списке, оставшемся после заголовка, затем добавьте единицу, если заголовок положительный, и ничего, если заголовок равен нулю или отрицательный.
3. Уменьшенная версия проблемы заключается в нахождении количества положительных результатов в списке с удаленным заголовком : countPos(head.next) .
4. Найдите базовый вариант: пустой список имеет нулевые положительные значения.

Соедините все это вместе:

 int countPos(Node head) {

  // Take care of the base case first.
  if (head == null) return 0;

  // Solve the smaller problem.
  int positiveCountWithoutHead = countPos(head.next);

  // Now the logic in step 2. Return either the positive count or 1  the positive count:
  return head.data > 0 ? positiveCountWithoutHead   1 : positiveCountWithoutHead;
}
 

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

Давайте попробуем тот, который не совсем соответствует стандартному шаблону: рекурсивный двоичный поиск. У нас есть массив a целых чисел, и мы пытаемся найти индекс x , если он существует в массиве, и вернуть -1 , если нет.

ПРОБЛЕМА: поиск в массиве между позициями i0 и i1-1 .

(Приведенное выше является примером того, как вы должны иногда «специализировать» проблему, добавляя параметры, чтобы в рекурсивном вызове или вызовах можно было описать более мелкие подзадачи. Здесь мы добавляем новые параметры i0 и i1 , чтобы мы могли указать подмассив a . Знание того, как и когда это делать, является вопросом практики. Необходимые параметры могут варьироваться в зависимости от особенностей языка.)

1. Функциональный интерфейс: int search(int [] a, int x, int i0, int i1)
2. Разделите проблему на части: мы выберем «средний» индекс элемента : mid = (i0 i1) / 2 . Тогда подзадача заключается либо в поиске первой половины массива с точностью до исключения mid , либо во второй половине массива, начиная с середины и продолжая до конца.
3. Вызовами являются search(a, x, i0, mid) и search(a, x, mid 1, i1) .
4. Базовые случаи таковы: 1) если i0 >= i1 нет элементов для поиска, поэтому возвращайте -1 и 2) если у нас есть a[mid] == x , значит, мы нашли x и можем вернуть mid .

Собрать все это вместе

 int search(int [] a, int x, int i0, int i1) {

  // Take care of one base case.
  if (i0 >= i1) return -1;

  // Set up mid and take care of the other base case.
  int mid = (i0   i1) / 2;
  if (a[mid] == x) return mid;

  // Solve one or the other subproblems.  They're both smaller!
  return x < a[mid] ? search(a, x, i0, mid) : search(a, x, mid   1, i1);
}
 

И чтобы начать поиск:

 int search(int [] a, int x) { return search(a, x, 0, a.length); }
 

При каждом вызове countPos() запускается новая версия этой функции. Эта функция начинается с чистого листа, что означает, что все локальные переменные ( count ) являются ее собственными, и никакая другая «копия» countPos не может видеть или изменять ее локальные переменные.

Единственное состояние, которое передается между этими «копиями» или из countPos , — это переменные, которые передаются в качестве параметров ( Node head ).

Итак, вот примерный рабочий процесс, предполагающий список [1, -2, 3]

1. countPos запускается и сообщает, что количество положительных узлов равно 1, поскольку «1» является положительным. Общее количество положительных узлов равно 1 независимо от того, что возвращает следующая функция.
2. Следующая функция сообщает, что количество положительных узлов равно 0 независимо от того, что возвращает следующая функция.
3. Следующая функция говорит, что количество положительных узлов равно 1 независимо от того, что возвращает следующая функция
4. Следующая функция видит это head == null и поэтому возвращает 0.

Теперь каждая рекурсивная функция возвращает одну за другой к исходной функции, которая ее вызвала, при этом общее количество положительных узлов «растет как снежный ком» по мере возврата.

Общее число, возвращенное в итоге, будет равно 2.