Рекурсивная функция в нерекурсивной функции?

Question

У меня есть следующий рекурсивная функция Grails:

private boolean isCyclic(TreeNode node) { 
    boolean cyclic = false 
    def myParents = this.parents 

    // if there are parents of this node 
    if (myParents.size() != 0) { 

     // if the new node is in the parents set of this node 
     if (myParents.contains(node)) { 
      cyclic = true 
      return cyclic 
     } 
     else { 
      // go into each parent of this node and test if new node is contained in their parents 
      myParents.each { parent -> 
       log.debug "go to parent: "+parent.name 
       if (cyclic) { 
        return cyclic 
       } 
       cyclic = parent.isCyclic(node) 
      } 
     } 
    } 

    return cyclic 
} 

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

Answer 1

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

Возможно, я не очень хорошо объяснил это, но каждая рекурсивная функция имеет итеративную функцию.

Answer 2

Tom Moertel написал решение этой проблемы в своем блоге.
Он ясно объяснил преобразование рекурсивной функции в итеративный (link).

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

Я надеюсь, что это поможет.

Answer 3

Я думаю ваш код выше, является contains метода, а не циклический ...

Однако вот быстрым пример как а содержит метод и циклическую проверку в итерационном стиле ... Пальцы скрещены они правы

def contains(TreeNode node) { 
    // if this node is the one we're looking for, return true 
    if(node == this) { 
     return true 
    } 
    // A queue of nodes to work on 
    def parentQueue = this.parents as Queue 

    // A set of nodes we've seen (to avoid loops) 
    def seen = [ this ] as Set 

    // While we have nodes to look for 
    while(parentQueue) { 
     // get the next node 
     def next = parentQueue.pop() 

     // Check if it's the one we're looking for 
     if(next == node) return true 

     // And if not, add it's parents to the queue 
     // assuming we've not seen it before 
     if(!seen.contains(next)) { 
      next.parents.each { parentQueue.offer(it) } 
     } 
    } 
    // Not found 
    return false 
} 

def isCyclic() { 
    // A queue of nodes to work on 
    def parentQueue = this.parents as Queue 

    // A set of nodes we've seen (to detect loops) 
    def seen = [ this ] as Set 

    // While we have nodes to look for 
    while(parentQueue) { 
     // Look at the next element in the queue 
     def next = parentQueue.pop() 

     // If we've seen it before, it's cyclic 
     if(seen.contains(next)) return true 

     // Otherwise, record we've seen this node 
     seen << next 

     // And add its parents tothe queue 
     next.parents.each { parentQueue.offer(it) } 
    } 
    // All done, not cyclic 
    return false 
}