PHP中简单的递归对象层次结构，如何让祖先避免无限循环？

Question

Property parent returns the parent of the current item (or null). I need to avoid infinite recursion with an item that it's parent of itself.

// An item is considered without parent if parent is null or itself
$item1 = new Item();
$item1->setParent($item1);

$item2 = new Item();
$item2->setParent($item1);

$item3 = new Item();
$item3->setParent($item2);

$item1->getAncestors(); // Empty
$item2->getAncestors(); // Item 1
$item2->getAncestors(); // Item 1, Item 2

The following won't work because the first condition is true for "problematic" $item (thus the second isn't evaluated):

/**
 * Gets all ancestors of this item, sorted in a way that the farthest ancestor
 * comes first.
 *
 * @return \Doctrine\Common\Collections\ArrayCollection
 */
public function getAncestors()
{
    $parent = $this;
    $ancestors = array();

    while ($parent = $parent->parent && $this !== $parent) {
        $ancestors[] = $parent;
    }

    return new ArrayCollection(array_reverse($ancestors));
}

This won't work too because on loop 1 $this is $parent:

while ($this !== $parent && $parent = $parent->parent) {
    $ancestors[] = $parent;
}

I'm sure this is a common problem but I can't find a solution by myself.

Answer 1

As you are stating it, the structure you are traversing is not a tree. It's a directed graph with cycles. One way to avoid an infinite loop is to keep track of the visited vertices by passing an arraylist containing all visited vertices. As you visit each vertex, you first check if it is in the list and return if true, add it to the list otherwise and continue. You do not need recursion. A while loop will do.