Можно ли оптимизировать рекурсию?

Question

[MaMkO]

Здравствуйте, начинаю осваивать рекурсию, написал код для вывода многоуровневых категорий

class Category
{

  public array $tree = [];

  // Построение дерева
  public function createTree($data)
  {
    //Ищем элементы без родительских
    foreach ($data as $item) {
        if ($item['parent_id'] === null) {
          $this->tree[$item['id']] = $item;
          $this->createElemTree($data, $this->tree[$item['id']], $item['id']);
        }
    }

    return $this->tree;
  }

  // Добавление элементов как дочерних
  public function createElemTree($data, &$parentElem, $parentId = null)
  {
    foreach ($data as $key=>$item) {
        if ($item['parent_id'] === $parentId) {
          $parentElem['children'][$key] = $item;
          $this->createElemTree($data, $parentElem['children'][$key], $item['id']);
        }
    }
  }
}


$data = [
    ['id' => 0, 'name' => 'Электроника', 'parent_id' => null],
    ['id' => 1, 'name' => 'Косметика', 'parent_id' => null],
    ['id' => 2, 'name' => 'Инструменты', 'parent_id' => null],
    ['id' => 3, 'name' => 'Телефоны', 'parent_id' => 0],
    ['id' => 4, 'name' => 'Духи', 'parent_id' => 1],
    ['id' => 5, 'name' => 'Samsung', 'parent_id' => 3]
];

$category = new Category();
$tree = $category->createTree($data);

Интересует такой вопрос - можно ли как-то оптимизировать текущий код?

Comments

[чсмчсмчмсчмчсмчсм]

public static function tree($nodes, $parent_id = 0, $level = 0, $increment_id_name = "id", $parent = "parent_id")
    {

        $tree = array();
        $level++;
        foreach ($nodes as $node) {
            if ($node[$parent] == $parent_id) {
                $children = self::tree($nodes, $node[$increment_id_name],$level,$increment_id_name,$parent);
                if($children){
                    $node['children'] = $children;
                }
                $node['level'] = $level;
                $tree[] = $node;
            }
        }
        return sizeof($tree)?$tree:false;
    }

[MaMkO]

чсмчсмчмсчмчсмчсм, Спасибо, отличный вариант, гораздо меньше времени занимает

Answer 1

[Alexandroppolus]

Это тривиально делается за линейное время и без рекурсии.
Сначала составляем словарь dict (id => узел дерева), в твоем случае таким словарем может быть исходный массив, если id идут по порядку от нуля, и $data[id] всегда содержит элемент с таким id, а элементы массива станут узлами дерева.
Потом обходим массив снова и в чилдрены dict[$item['parent_id']] добавляем $item.

Comments

[MaMkO]

Тоже как вариант. Но у меня задача была именно познакомиться с рекурсией.
Как я понимаю данный вариант будет быстрее, чем вариант с рекурсией?

[Alexandroppolus]

MaMkO, да, быстрее. Оба представленных варианта с рекурсией выполняются за время O(N^2), а нерекурсивный - за O(N), если конечно предположить, что доступ к элементу словаря занимает O(1). Это очень существенная разница в асимптотике.
Более того, если дерево глубокое, то рекурсия свалится в переполнение стека. А дерево ведь неизвестно какое, там может оказаться, что 0 - парент для 1, 1 - парент для 2, и т.д., то есть по сути линейный связный список.
Рекурсию нет смысла применять, если легко обойтись без нее.