How to recursively build a list of Item Substitutions when multiple substitutes exist

Question

In Microsoft Dynamics Nav 2013, there is a feature for specifying Item Substitutions for an item (product); However, you can specify more than one substitution for a single product and technically a substitution can itself have one or more substitutions.

I am trying to build a recursive solution in PHP that allows me to take a known product code, and recursively search for item substitutions to generate a one dimensional array of items. If this were a one to one relationship (parent,child) this would be a trivial task for me, but the fact that there can be multiple childs on any given iteration is kind of blowing my mind.

My question is if anyone knows how to write a recursive method for the situation I've described above? Below I will layout the way the data is structured to give a better understanding of the problem:

$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 (added my attempt to solve using recursive method):

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;
}

Edit (Final code used, derived from accepted answer):

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);
        }
    }
}

Answer 1

This code could serve as a solution for your example. I just presume that you fetch the list of 'direct' items substitutes from your database, so you could replace GetDirectSubstitutes with the code that fetches the substitutes list for the given item (I used you example array as a data source).

Just be careful - this simple implementation doesn't check for cyclical references. If your initial data contains loops, this code will stuck.

function GetDirectSubstitutes($itemNo)
{
    global $substitutionsLookup;
    $items = array();
    foreach ($substitutionsLookup as $itemPair) {
        if ($itemPair['No'] == $itemNo) {
            array_push($items, $itemPair['SubstNo']);
        }
    }

    return $items;
}

function GetSubstitutesTree($itemNo, &$substitutes)
{
    $directSubst = GetDirectSubstitutes($itemNo);
    if (!empty($directSubst)) {
        $substitutes = array_merge($substitutes, $directSubst);
        foreach ($directSubst as $item) {
            GetSubstitutesTree($item, $substitutes);
        }
    }
}