Понимание раскручивания стека в рекурсии (обход дерева)

Ваш код не работает как есть, он будет бесконечно повторяться по узлу 39. Метод inOrderTraversal() действительно перейдет к левому узлу, но будет циклически проходить его вечно из-за времени. Каждый кадр стека имеет собственную копию переменных. При входе в метод переменная node получает копию ссылки на объект, переданной в качестве аргумента.

Один из способов представить рекурсию — это похоже на использование цикла while, но вместо while у вас есть if. Вот как должен выглядеть метод:

    public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.println(node.data);
        inOrderTraversal(node.right);
    }
}

Когда вы проходите по дереву, вы хотите сначала напечатать меньшее значение, которое хранится в самом левом узле, поэтому вы используете inOrderTraversal(node.left);, чтобы добраться до if. Когда вы достигаете нулевого узла, это означает, что его родителем является крайний левый узел, поэтому вы печатаете его. После этого вы переходите к нужному узлу и повторяете процесс. Это похоже на разбиение дерева на более мелкие поддеревья до тех пор, пока вы не сможете их больше разделить и вывести их значение.

Каждый раз, когда вы вызываете метод (рекурсивный или нет), выделяется новый фрейм стека (помещается в стек), и после завершения метода стек удаляется (извлекается), освобождая место для сборки мусора. Эти кадры стеков являются лишь временным пространством, в котором живут локальные переменные. Переменные-члены объекта находятся в другом месте, называемом кучей, срок жизни которого больше, чем у стека.

JVM обрабатывает выделение этих пространств, и сборщик мусора освобождает их в зависимости от срока службы объектов/переменных. В зависимости от того, сколько они живут, бывает несколько поколений (так их называют). Все начинают с поколения eden (молодых), и если сборщик мусора не освобождает пространство, поскольку они еще живы, они перемещаются в поколение выживших, после чего, если они все еще не собраны, они переходят к последнему. , штатное поколение. Чем дольше живут объекты, тем реже они проверяются GC. Это означает, что если объекты в эдеме собираются довольно быстро, то остальные поколения проверяются не так часто. Существует также другое пространство, называемое постоянным поколением (permgen), где раньше жили константы (например, строковые литералы) и где хранились классы.

Вы можете получить более четкое представление о рекурсии и стеке, подумав о классическом примере рекурсии, факториале.

int factorial(x) {
   int result;
   if(x==1) 
       result = 1;
   else
       result = x * factorial(x - 1);
   return result;
 }

(Я использовал переменную result, чтобы упростить отметку позиции при ручном выполнении кода)

Пройдите выполнение factorial(5) вручную, используя бумажки.

Начните с того, что напишите функцию на одном листе бумаги, заменив «x» на 5. Затем прочитайте ее, а когда дойдете до вызова функции, поставьте отметку карандашом в точке выполнения и получите новый лист бумаги для своего вызов новой функции.

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

Важно понимать, что это не относится к рекурсивным вызовам функций. Таким образом, все вызовы функций создают запись в стеке.

Выполнение программы не может просматривать стек. Доступен только верхний лист бумаги -- последний пришел, первый ушел (LIFO). Когда вы дойдете до factorial(1), он больше не вызывает себя, и вы дойдете до return. Когда это произойдет, выбросьте верхний лист бумаги, запишите возвращаемое значение в новый верхний слой, затем продолжите выполнение функции на верхнем слое с точки, где вы поставили отметку карандашом.

Продолжайте в том же духе, и в конце концов вы выбросите последний лист. Это означает, что ваша программа завершена, и у вас есть окончательный результат.

Между прочим, если с вашим кодом что-то не так, например, нет случая, когда функция не вызывает сама себя, у вас закончится бумага (или ваша стопка бумаги достигнет потолка) - это переполнение стека в честь которого назван этот сайт. Стек становится больше установленного максимума, и среда выполнения отказывается снова вызывать функцию (в Java, вызывая исключение). Вы, вероятно, столкнетесь с этим в своей карьере программиста - распространенными причинами являются плохо закодированное условие остановки или циклическое повторение структуры данных.

В приведенной выше реализации factorial(0), вероятно, вызовет переполнение стека. Вы видите, почему?

Так работают все обычные компьютерные программы. Вы помещаете один элемент в стек (в C и Java это main()). Каждый раз, когда выполняется вызов функции, стек увеличивается, и каждый раз, когда функция завершается, стек сжимается. Стек растет и сжимается до тех пор, пока в конечном итоге не сожмется до нуля, после чего программа будет завершена.

Для таких программ, как ваша, с двумя рекурсивными вызовами одной и той же функции ничего не меняется. Хорошим упражнением будет запустить небольшой поиск по бинарному дереву вручную с листами бумаги так же, как мы это делали с factorial(), чтобы увидеть, как это работает.

Также полезно приостановить код Java в отладчике, чтобы посмотреть состояние текущего стека, или, если вы не можете этого сделать (скорее научитесь пользоваться отладчиком!) выходы.

Во-первых, утверждение while в inOrderTraversal неверно. Ни один из операторов в цикле while не изменяет переменную node, поэтому, если она была null, она всегда будет, а если нет, то никогда. Измените его на if.

Имея это, способ взглянуть на рекурсию часто основан на индукции. Я утверждаю следующую индукционную гипотезу:

Учитывая дерево T с корнем node, inOrderTraversal(node) печатает упорядоченный обход T и возвращается.

Мы можем показать по индукции, что это действительно происходит. Простой случай, когда node == null. В этом случае inOrderTraversal ничего не печатает и возвращается напрямую, что соответствует гипотезе.

Теперь предположим, что мы передаем непустое дерево. По индукции inOrderTraversal(node.left) печатает левое поддерево и возвращается. Затем печатается node.data. Наконец, снова по индукции, inOrderTraversal(node.right) печатает правильное поддерево и возвращается. Обратите внимание, что до сих пор текущее дерево печаталось в обходе по порядку. Поскольку я изменил while на if, метод возвращается, тем самым удовлетворяя гипотезе индукции.

Отвечает ли это на ваш вопрос?