Как преобразовать эту рекурсивную функцию в итеративную?

Question

F = function(node){ 
    return typeof(node)!="object" ? 
       node 
      : transformable([F(node[0]),F(node[1])]) ? 
       F(transform(F(node[0]),F(node[1]))) 
      : node; 
}; 

Эта функция получает двоичное дерево, такое как [1,[[2,3],[4,5]]], и рекурсивно применяет серию преобразований. Есть ли способ преобразовать эту функцию так, чтобы

1. он получает вместо этого сплющенное двоичное дерево, такое как [N,1,N,N,2,3,N,4,5];
2. не используется рекурсия?

Answer 1

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

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