Use recursion to accumulate rows without depending on class property variable

Question

Having this array :

[
    "id" => 5,
    "name" => "Item 5",
    "all_parents" => [
        "id" => 4,
        "name" => "Item 4",
        "all_parents" => [
            "id" => 3,
            "name" => "Item 3",
            "all_parents" => [
                "id" => 2,
                "name" => "Item 2",
                "all_parents" => [
                    "id" => 1,
                    "name" => "Item 1",
                    "all_parents" => null
                ]
            ]
        ]
    ]
]

I created a recursive php function that transform that array to this:

[
    ["id" => 1, "name" => "Item 1"],
    ["id" => 2, "name" => "Item 2"],
    ["id" => 3, "name" => "Item 3"],
    ["id" => 4, "name" => "Item 4"],
    ["id" => 5, "name" => "Item 5"],
]

The code is this:

private array $breadcrumb = [];
private function generateBreadcrumb($structure) : array
{
  if($structure) {
        $this->breadcrumb[] = array(
            "id" => $structure['id'],
            "name" => $structure['name'],
        );
        $this->generateBreadcrumb($structure['all_parents'] ?? []);
  }
  
  return array_reverse($this->breadcrumb);
}

How can I redesign this method without depending on class property $breadcrumb?

Perhaps look through https://stackoverflow.com/questions/1319903/how-to-flatten-a-multidimensional-array for alternatives. — Nigel Ren, Feb 26 '22 at 11:19

lukas.j · Answer 1 · 2022-02-26T12:08:16.957

Instead of implementing a recursive function there is the possibility of using the built-in array_walk_recursive function:

$arr = [
    'id'          => 5,
    'name'        => 'Item 5',
    'all_parents' => [
        'id'          => 4,
        'name'        => 'Item 4',
        'all_parents' => [
            'id'          => 3,
            'name'        => 'Item 3',
            'all_parents' => [
                'id'          => 2,
                'name'        => 'Item 2',
                'all_parents' => [
                    'id'          => 1,
                    'name'        => 'Item 1',
                    'all_parents' => null
                ]
            ]
        ]
    ]
];

function generateBreadcrumb($structure): array {
  $retval = [];
  array_walk_recursive($structure, function ($item, $key) use (&$retval) {
    if ($key === 'id') {
      $retval[] = [$key => $item];
    } elseif ($key === 'name') {
      $retval[array_key_last($retval)][$key] = $item;
    }
  });
  return array_reverse($retval);
}

$result = generateBreadcrumb($arr);

Note that array_walk_recursive only visits leafs, so with the exception of the innermost 'all_parents', the other ones are not visited.

A none-recursive version would be this:

function generateBreadcrumb(array $arr): array {
  $retval = [];
  $temp = &$arr;
  do {
    $retval[] = [ 'id' => $temp['id'], 'name' => $temp['name'] ];
    $temp = &$temp['all_parents'];
  } while ($temp !== null);
  return array_reverse($retval);
}

not in the bad way.... on the first view it seems complicated .... but make sense ;-) — calin24, Feb 26 '22 at 11:49

score 1 · Answer 2 · answered Feb 26 '22 at 12:01

By following your initial code, you could do:

function generateBreadcrumb($structure, &$output = []) : array
{
    if ($structure) {
        $output[] = array(
            "id" => $structure['id'],
            "name" => $structure['name'],
        );
        $this->generateBreadcrumb($structure['all_parents'] ?? [], $output);
    }

    return array_reverse($output);
}

However it could be improved, at least by avoiding to call array_reverse() each time, but only for the root call.

mickmackusa · Answer 3 · 2022-02-26T21:41:25.757

You can accumulate the indeterminate-depth data by merging as you recurse the tree. You do not need to introduce any new variables to carry the data while recursing nor do you need to array_reverse() the returned data.

The below technique will prioritize recursion while $structure['all_parents'] is truthy (not null) and cease recursion once it encounters the null all_parents value in the deepest subarray. From the bottom, the id and name elements will be accessed and merged into the empty or accumulated array of row data.

Code: (Demo)

class Recursing
{
    public function generateBreadcrumb(array $structure): array
    {
        return array_merge(
            $structure['all_parents']
                ? $this->generateBreadcrumb($structure['all_parents'])
                : [],
            [
                ['id' => $structure['id'], 'name' => $structure['name']]
            ]
        );
    }
}

$test = new Recursing;
var_export($test->generateBreadcrumb($arr));

Output:

array (
  0 => 
  array (
    'id' => 1,
    'name' => 'Item 1',
  ),
  1 => 
  array (
    'id' => 2,
    'name' => 'Item 2',
  ),
  2 => 
  array (
    'id' => 3,
    'name' => 'Item 3',
  ),
  3 => 
  array (
    'id' => 4,
    'name' => 'Item 4',
  ),
  4 => 
  array (
    'id' => 5,
    'name' => 'Item 5',
  ),
)

@calin can you help me to understand why the leanest, most direct answer with fewer recursions and fewer variables has a negative vote tally? In the absence of some logical reason, I must assume that my correct/best answer is merely being trolled. — mickmackusa, Feb 28 '22 at 04:46

Use recursion to accumulate rows without depending on class property variable

3 Answers3