Unity: Всё, что вы не знали о разработке: “Рекурсивный метод можно представить в виде цикла. Допустим, у нас есть…”

Рекурсивный метод можно представить в виде цикла.

Допустим, у нас есть простой метод для перебора чего-либо:


class Node {
  public int value;
  public Node[] children;
}

Node FindRecursively(Node root, int value) {
  if (root.value == value) return root;
  for (int i = 0; i < root.children.Length; ++i) {
    var node = FindRecursively(root.children[i], value);
    if (node != null) return node;
  }
  return null;
}

Мы видим, что если на вход передать ноду графа и значение, то мы в итоге найдем нужную ноду, либо вернем null.

Чем плох такой вариант? Дело в том, что каждый вход в метод FindRecursively будет создавать стек под этот метод, т.е. чем больше мы используем в методе всяких переменных, тем быстрее закончится место в нашем стеке, если представить, что граф у нас довольно большой.

Что же делать?
Давайте избавимся от рекурсивного вызова метода. Самый простой вариант это сделать - использовать Stack или Queue:


Node Find(Node root, int value) {
  var queue = new Queue<Node>();
  queue.Enqueue(root);
  while (queue.Count > 0) {
    var node = queue.Dequeue();
    if (node.value == value) return node;
    for (int i = 0; i < node.children.Length; ++i) {
      queue.Enqueue(node.children[i]);
    }
  }
  return null;
}

Из минусов - придется объявить коллекцию, куда мы будем складывать элементы. из плюсов - можно обойти граф любой глубины.

#recursion #code #algorithms