На этом шаге мы рассмотрим, что представляют из себя эти деревья, и как их можно использовать.
Наиболее простой и наглядный способ представления цепочки рекурсивных вызовов - дерево рекурсии (recursion tree). Его узлы соответствуют вызовам метода с определенными параметрами. Если какой-то метод вызывает другие подпрограммы, то его узел становится родителем узлов-вызовов соответствующих подпрограмм. Таким образом, листья дерева соответствуют начальным условиям, а внутренние узлы - рекурсивным условиям. Кроме того, дочерние узлы родителя следуют слева направо в том же порядке, в котором они вызываются. Таким образом, прямой (preorder) обход дерева рекурсии задаёт последовательность вызовов подпрограмм, тогда как обратный (postorder) обход - последовательность возвратов из рекурсивных подпрограмм.
Как правило, параметры вызова отображаются рядом с соответствующим узлом. На рисунке 1(a) приведено дерево рекурсии для вызова sum_first_naturals(4), где число в каждом узле - это значение n для данного рекурсивного вызова.
Рис.1. Деревья рекурсии для sum_first_naturals(4)
Хотя дерево является неориентированным, важно помнить, что процесс вычисления sum_first_naturals(4) сначала спускается вниз по дереву (рекурсивных вызовов) к начальному условию, а затем поднимается к корню вверх по дереву (рекурсивных возвратов). Поэтому дерево рекурсии можно снабдить стрелками, обозначающими вызовы и возвраты, как показано на рисунке 1(b). Наконец, по рисунку видно, что sum_first_naturals(4) возвращает своё значение методу, вызвавшему её (то есть на экран).
Деревья рекурсии можно дополнить значениями функций по завершении их вызовов. В частности, эти значения можно указать в узлах дерева активации (activation tree) вслед за параметрами метода, как показано на рисунке 2 для вызова sum_first_naturals(4).
Рис.2. Дерево активации для sum_first_naturals(4)
Деревья активации могут быть полезными для оценки и отладки методов, так как помогают отслеживать возвращаемые значения.
И линейно-рекурсивные методы, и методы с хвостовой рекурсией порождают деревья рекурсии линейной структуры, так как вызывают себя в рекурсивном условии лишь однажды. При этом если линейно-рекурсивная функция при каждом вызове возвращает разные значения, то функция с хвостовой рекурсией всегда возвращает одно и то же значение. Рассмотрим функцию gcd1() из примера для алгоритма Евклида (см. (5.6)). На рисунке 3 приведено дерево активации для вызова gcd1(20,24), из которого следует, что метод возвращает значение, полученное в начальном условии.
Рис.3. Дерево активации для gcd1(20,24)
Однако вычисление не заканчивается в начальном условии. Наоборот, каждый вызов обязан завершиться, причём с возвратом одного и того же значения (4). Аналогично, в приведённом выше примере (см. рисунок 1, 154 шаг) процедура с хвостовой рекурсией mystery_method_1() приходит к своему результату по достижении начального условия.
На следующем шаге мы закончим изучение этого вопроса.
