Naeel Maqsudov » 09 июл 2013, 15:13
Если с одинарной понятно, то какие проблемы? Когда произойдёт возврат из первого d(n-1), то только тогда та же самая канитель повторится еще раз.
Т.е. если при одинарном рекурсивном вызове d(n-1) у нас получается вырожденное в список дерево. Такую рекурсию можно смело заменить на цикл. (Что, к слову, компиляторы некоторых языком делают самостоятельно).
А если вызывать 2 раза, то получится классический обход сбалансированного бинарного дерева
d(2),d(1),d(0),d(0),d(1),d(0),d(0),d(2),d(1),d(0),d(0),d(1),d(0),d(0)
Если с одинарной понятно, то какие проблемы? Когда произойдёт возврат из первого d(n-1), то только тогда та же самая канитель повторится еще раз. :)
Т.е. если при одинарном рекурсивном вызове d(n-1) у нас получается вырожденное в список дерево. Такую рекурсию можно смело заменить на цикл. (Что, к слову, компиляторы некоторых языком делают самостоятельно).
А если вызывать 2 раза, то получится классический обход сбалансированного бинарного дерева
d(2),d(1),d(0),d(0),d(1),d(0),d(0),d(2),d(1),d(0),d(0),d(1),d(0),d(0)