Прямая кинематика

[dimarik]

Сообщение от Zebestov

Лишь первый раз мы рекурсивно пройдемся от child1 к root

Если каждый раз у нового объекта дергать метод, то думаю, что это не рекурсия. Рекурсия дернет свой же метод (этого же объекта). Короче, при рекурсии в коллстеке периодически появляется один и тот же объект.

[Zebestov]

Если строго говорить, то ты прав конечно.
Интересно, как такие вызовы называются?

[dimarik]

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

some nodes must be deferred – stored in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).

Т.о. само понятие "поиска" в, например, дереве, в глубину, подразумевает сохранение уже обойденных нодов. Чтобы потом воспользоваться ими как отправной точкой для перебора их детей. Но вот где будет храниться эта нода: в глобальном Array или на уровне стека вызовов AVM, в котором сохраняется вновь посещенный объект — это без разницы. Если рекурсия — это сохранение ноды в таких объектах, то я не прав. Если рекурсия — это вызов метода у того же самого объекта, то я прав. Отдельно стоит использование глобального Array. Его использование вообще не попадает под определение рекурсии.

Можно строго подойти к рекурсии: не делай лишних объектов в коллстеке и мы не будем называть твой алгоритм рекурсивным. Не знаю, в общем. Я тоже раньше рекурсию, так же как ты, ассоциировал с вызовами "одинаковых" методов у разных объектов. Но вот задумался немного и пришел в замешательство.

Ах, да. Немного пруфов не повредит:

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно
 (простая рекурсия) или через другие функции (сложная или косвенная рекурсия)

[Zebestov]

Вот. Обход дерева, да.

[dimarik]

Обход дерева может быть рекурсивным или нерекурсивным.
Там еще из типов обходов в глубину есть. Так же простой обход по парентам (не обход всего дерева, если что). А можно навернуть обход по уровням нод (breadth-first, обход всего дерева).
Ну и ладно. Пусть все будут здорОвы! =)