Как рекурсивно построить список замен элементов при наличии нескольких заменителей

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

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

У меня вопрос, если кто-нибудь знает, как написать рекурсивный метод для ситуации, которую я описал выше? Ниже я расскажу, как структурированы данные, чтобы лучше понять проблему:

$lineItems = array(
'XXX-0',
'XXX-1',
'XXX-3'
);

$substitutionsLookup = array(
0 => array('No_' => 'XXX-1', 'Substitute No_' => 'XXX-2'),
1 => array('No_' => 'XXX-3', 'Substitute No_' => 'XXX-4'),
2 => array('No_' => 'XXX-3', 'Substitute No_' => 'XXX-5'),
3 => array('No_' => 'XXX-5', 'Substitute No_' => 'XXX-6')
);

// Resulting product code substitutions for XXX-0
$result1 = array();

// Resulting product code substitutions for XXX-1
$result2 = array('XXX-2');

// Resulting product code substitutions for XXX-3
$result3 = array('XXX-4', 'XXX-6');

Edit (добавлена ​​моя попытка решить рекурсивным методом):

protected function getSubstitutions($haystack, $needle, &$results = array())
{
if (count($haystack) == 0)
{
return false;
}

$matches = array();
foreach ($haystack as $index => $check)
{
if ($check['No_'] === $needle)
{
$newHaystack = $haystack;
unset($newHaystack[$index]);

$moreMatches = $this->getSubstitutions($newHaystack, $check['Substitute No_'], $results);

if ($moreMatches === false)
{
$matches[] = $check['Substitute No_'];
}
}
}

if (count($matches))
{
foreach($matches as $match)
{
$results[] = $match;
}
}

return $results;
}

Редактировать (используется окончательный код, полученный из принятого ответа):

class ItemSubstitutionService implements ServiceLocatorAwareInterface
{
public function getSubstitutions($itemNo, $noInventoryFilter = true, $recursive = true)
{
$substitutions = array();
$directSubs = $this->itemSubstitutionTable->getSubstitutionsByNo($itemNo);

if ($recursive)
{
foreach($directSubs as $sub)
{
$this->getSubstitutionsRecursive($sub, $substitutions);
}
} else {
$substitutions = $directSubs;
}

foreach($substitutions as $index => $sub)
{
$inventory = $this->itemLedgerEntryTable->getQuantityOnHand($sub->getSubstituteNo());
$sub->setInventory($inventory);

if ($noInventoryFilter)
{
if ($inventory == 0)
{
unset($substitutions[$index]);
}
}
}

return $substitutions;
}

private function getSubstitutionsRecursive(ItemSubstitution $sub, &$subs)
{
$directSubs = $this->itemSubstitutionTable->getSubstitutionsByNo($sub->getSubstituteNo());
if (empty($directSubs))
{
$subs[$sub->getSubstituteNo()] = $sub;
}

foreach($directSubs as $curSub)
{
$this->getSubstitutionsRecursive($curSub, $subs);
}
}
}